Re: How do I do this problem without a calculator?
- From: "Chip Eastham" <hardmath@xxxxxxxxx>
- Date: 5 Mar 2006 20:15:38 -0800
bell3774@xxxxxxxxx wrote:
I don't understand.
in response to what Chip Eastham wrote:
bell3774@xxxxxxxxx wrote:
6^19 mod 22
19 is prime, but Fermat's Little Theorem requires p+1 to work...
You might want Euler's generalization of Fermat's Little Thm.
It doesn't matter that 19 is prime. You need to consider the
modulus 22.
Fermat's Little Theorem says that if p is prime:
x^(p-1) = 1 mod p
for any x not divisible by p.
In your problem, calculating 6^19 mod 22 (presumably asking
to find the reduced nonnegative residue mod 22), the modulus
22 is not prime! And furthermore the base x = 6 that is being
raised to a power has a factor 2 in common with modulus 22.
One approach, not discussed by other notes in this thread so
far, would be to consider the computation modulo 2 and again
modulo 11. You can then piece together the answer modulo
22 from the separate answers for 2 and 11.
However I don't want you to get bogged down trying to follow
every different approach being suggested here. Pick one and
work it through!
Later you may have time to come back and verify that all
the suggested approaches lead to the same answer.
regards, chip
.
- Follow-Ups:
- Re: How do I do this problem without a calculator?
- From: Foster Bell
- Re: How do I do this problem without a calculator?
- References:
- How do I do this problem without a calculator?
- From: bell3774
- Re: How do I do this problem without a calculator?
- From: Chip Eastham
- Re: How do I do this problem without a calculator?
- From: bell3774
- How do I do this problem without a calculator?
- Prev by Date: Re: Limit without L'Hospital
- Next by Date: Reformulating and equation
- Previous by thread: Re: How do I do this problem without a calculator?
- Next by thread: Re: How do I do this problem without a calculator?
- Index(es):
Relevant Pages
|
