Fermat's Little Theorem Help
Rafael Almeida
I've got a doubt in these Fermat-related proofs:
Let a be some integer. Prove that:
- a^21 = a (mod 15)
- a^7 = a (mod 42)
- if a and 35 are coprimes (gcd(a,35)=1), then a^12 = 1 (mod 35)
I seriously feel that the solution involves rewriting the congruences
so that the modulus is a prime number (because of the Little Theorem's
hypotesis), and I suspect this has something to do with the GCD of the
exponent and the current modulus. However, I don't know how to
progress from this point on.
Any help or tip for at least one of the proofs will be greatly
appreciated. Thanks in advance.
Helmut Richter
> Let a be some integer. Prove that:
> - a^21 = a (mod 15)
> I seriously feel that the solution involves rewriting the congruences
> so that the modulus is a prime number (because of the Little Theorem's
> hypotesis), and I suspect this has something to do with the GCD of the
> exponent and the current modulus. However, I don't know how to
> progress from this point on.
By the Chinese Remainder Theorem, x = a (mod 15) if and only if
x = a (mod 3) and x = a (mod 5). Use FLiT for both of them.
--
Helmut Richter
Arturo Magidin
Rafael Almeida <almeida...@gmail.com> wrote:
>I've got a doubt in these Fermat-related proofs:
>
>Let a be some integer. Prove that:
>- a^21 = a (mod 15)
>- a^7 = a (mod 42)
>- if a and 35 are coprimes (gcd(a,35)=1), then a^12 = 1 (mod 35)
>
>I seriously feel that the solution involves rewriting the congruences
>so that the modulus is a prime number (because of the Little Theorem's
>hypotesis), and I suspect this has something to do with the GCD of the
>exponent and the current modulus. However, I don't know how to
>progress from this point on.
You would also want to use the Chinese Remainder Theorem.
Note that x = a (mod 3) and x = a (mod 5) is a system of congruences
that has a unique solution modulo 3*5 = 15. Each of the congruences
is modulo a prime, so you can use Fermat's Little Theorem.
Likewise, since 42 = 2*3*7, a single congruence modulo 42 is
equivalent to a system of three congruences, one modulo 2, one modulo
3, and one modulo 7. Each of those is "subject" to Fermat's Little
Theorem.
And 35 = 7*5, so once again you can rewrite the problem as a system of
two congruences, each with a prime modulus.
--
======================================================================
"It's not denial. I'm just very selective about
what I accept as reality."
--- Calvin ("Calvin and Hobbes" by Bill Watterson)
======================================================================
Arturo Magidin
magidin-at-member-ams-org
Bill Dubuque
>Rafael Almeida <almeida...@gmail.com> wrote:
>>
>> I've got a doubt in these Fermat-related proofs:
>> Let a be some integer. Prove that:
>>
>> I seriously feel that the solution involves rewriting the congruences
>> so that the modulus is a prime number (because of the Little Theorem's
>> hypotesis), and I suspect this has something to do with the GCD of the
>> exponent and the current modulus. However, I don't know how to
>> progress from this point on.
>
> You would also want to use the Chinese Remainder Theorem.
>
> Note that x = a (mod 3) and x = a (mod 5) is a system of congruences
> that has a unique solution modulo 3*5 = 15. Each of the congruences
More generally see my prior posts on the Carmichael Lambda function
and the exponent of a group, via this link, e.g. my old post below
http://google.com/groups/search?q=group%3A*math*+dubuque+carmichael+lambda
db <dbree...@tx.net> wrote:
>kazu3...@yahoo.com (kazu)
>>
>> What is the greatest integer that divides p^4-1
>> for every prime number p greater than 5?
>> (A) 12 (B) 30 (C) 48 (D) 120 (E) 240
>
> I'd factor p^4-1 as (p^2-1)(p^2+1) = (p-1)(p+1)(p^2+1)
>
> Then you can see that all 3 factors are divisible by 2,
> plus one of (p-1) or (p+1) must be divisible by 4, so
> p^4-1 must be divisible by 16.
>
> Also, one of (p-1) or (p+1) must be divisible by 3.
>
> By letting p = 1,2,3,4 (mod 5) you can see that one of
> the 3 factors must be divisible by 5.
>
> I believe the answer is 16 * 3 * 5 = 240 which is (E).
More generally use the Carmichael lambda function (see below).
y(240) = y(2^4 3 5) = lcm(2^2,2,4) = 4
=> x^4 = 1 (mod 240) for x coprime to 2,3,5
---------------
Chris Nolen <cmno...@ualr.edu> wrote:
:
: In my number theory homework I showed that if n is an integer
: not divisible by 2 or 3 then n^2 + 23 must be divisible by 24.
: Is there a general theory that relates to this?
You showed that a^2 = 1 (mod 24) if (a,24) = 1. More generally,
k = y(m) -> a^k = 1 (mod m) if (a, m) = 1
where y(m) is the Carmichael lambda function, defined as is the
Euler phi function on odd p^n, but combined via lcm vs. times:
y(2^e) = 2^(e-2) if e>2; y(4) = 2, y(2) = y(1) = 1
y(p^e) = p^(e-1) (p-1) for odd prime p
y(p^i q^j..) = lcm(y(p^i), y(q^j),..), distinct primes p,q,...
In your case y(24) = y(2^3*3) = lcm(2,2) = 2, as you showed,
and it's easy to see that 24 is the largest m with y(m) = 2.
In group theoretic language one says the y(m) is the exponent
of the unit group U(Z/(m)), i.e. the least exponent e > 0
such that x^e = 1 for all elts x of the group.
= http://groups.google.com/groups?threadm=y8zhekq6s2d.fsf%40nestle.ai.mit.edu
--Bill Dubuque