Exploring Fermat's Little Theorem

Date: 02/08/2001 at 00:59:12
From: G.Siva Prasad
Subject: Modular Arithmetic

For two integers, m and n, which are relatively prime, what is the 
least possible integer e such that this is true?

     (m^e) mod n = 1

It is true for e = (n-1), from Fermat's Theorem. What are the criteria 
for existence of another e < (n-1) for which the above equality holds?

Date: 02/08/2001 at 02:17:46
From: Doctor Schwa
Subject: Re: Modular Arithmetic

Hi,

First I'd like to point out that it's true for e = n-1 in the case 
where n is prime, but not necessarily otherwise. In fact checking 
whether some number to the n-1 = 1 (mod n) is a test sometimes used 
for primality; if it's not = 1 then you know n is not prime.

In answer to your main question, identifying the "primitive roots"
mod n (which is to say, the numbers which first return to equal 1 
after the maximum possible exponent) is not a simple question. In
fact I don't know of any algorithm that's easier than simply
exponentiating the number (with the usual shortcuts for 
exponentiating).

- Doctor Schwa, The Math Forum
  http://mathforum.org/dr.math/   

Date: 02/08/2001 at 05:07:53
From: Siva Prasad Gummadi [T]
Subject: Re: Modular Arithmetic

Hello,

Thank you for the suggestion. I understand that it is difficult to
find such an e. But I am still interested in exploring this more. The 
main thing which I'd like to point out in your reply is this:

     m^(n-1) = 1 mod n, for m and n relatively prime,
                        AND 'n' PRIME.

I feel that this extra condition on n is not required. Please refer 
to your Web document under 'Fermat's Little Theorem,' where the proof 
is given for this. I'll use the symbols used there.

     a^(p-1) = 1 mod p, for prime p, and for a relatively prime to p

Let us get into the proof, step by step, with a p which is not prime.
If we can show that the set {[a]mod p,[2a]mod p,...,[a(p-1)]mod p} is 
nothing but the permutation of the set {1,2,..(p-1)}, then the rest of
it follows automatically.

For this we choose two numbers m and n (as chosen in the proof) and
assume that they are congruent mod p. This implies that p|(m-n)a. 
Since a is relatively prime to p, 'all' of p  must divide (m-n). But 
since (m-n) < p, it's a contradiction. So the set is a permutation of 
the original.

In the final step, you can always cancel out (p-1)! mod p in the
equation

     (p-1)! mod p = a^(p-1)) mod p * (p-1)! mod p

Hence the result. Please let me know your comments on this. Thank you.

G.Siva Prasad, MIEL, Bangalore, India

Date: 02/08/2001 at 06:16:35
From: Doctor Schwa
Subject: Re: Modular Arithmetic

The primality condition on n is not REQUIRED, in the sense that there 
exist SOME n for which m^(n-1) = 1 mod n even though n is not prime.  
But it's certainly not true for all n.

For example, 3^9 = 3 (mod 10).

>Please refer to your web document under 'Fermat's Little Theorem,'
>where the proof is given for this. I'll use the symbols used there.

You'll need to read about "Euler's theorem", which says that in 
general if a and m are relatively prime, then a^(phi(m)) = 1 (mod m).
phi(m) is the number of numbers, 1...m, that are relatively prime
to m. So for instance, phi(10) = 4 because of 1, 3, 7, 9.

I think I agree with your proof up to this step:

>In the final step, you can always cancel out (p-1)! mod p in the
>equation
>
>     (p-1)! mod p = a^(p-1)) mod p * (p-1)! mod p

Here's the part I disagree with completely. If p = 10, then (p-1)! is 
divisible by 10, hence equal to 0 mod 10, so you can't divide by it.

The reason for Euler's generalization is that he uses just the set of 
things relatively prime to p. Then, the product of those things is 
not equal to zero mod p, because they all have inverses.

I hope that helps clear things up.

- Doctor Schwa, The Math Forum
  http://mathforum.org/dr.math/   

Date: 02/08/2001 at 07:13:27
From: Siva Prasad Gummadi [T]
Subject: Re: Modular Arithmetic

Hi,

Thank you for the clarification. In fact, I realized the mistake a 
few minutes after sending you the mail. Sorry for troubling you.

So, I'd like to sum up all by stating this:
------
If a and n are relatively prime, then for the statement

     a^(n-1) = 1 mod n

to be true, the following condition on n is 'sufficient':

     n is a prime, OR
     n = k^m, for some integers k and m.
------

I'll try to find the 'necessary' conditions on n in the above 
statement. I'll mail you in case I make any improvement, or for any 
other suggestions in my favorite number theory. Hope you don't mind.

G.Siva Prasad, MIEL, Bangalore

Date: 02/08/2001 at 12:29:10
From: Doctor Schwa
Subject: Re: Modular Arithmetic

>So, I'd like to sum up all by stating this:
>------
>If a and n are relatively prime, then for the statement
>
>     a^(n-1) = 1 mod n
>
>to be true, the following condition on n is 'sufficient':
>
>     n is a prime, OR
>     n = k^m, for some integers k and m.
>------

I still disagree with this statement. For example, 3^7 = 1 (mod 8) is 
not true.

>I'll try to find the 'necessary' conditions on n in the above 
>statement. I'll mail you in case I make any improvement, or for any 
>other suggestions in my favorite number theory. Hope you don't mind.

Of course I don't mind!  That's why we volunteer here.

- Doctor Schwa, The Math Forum
  http://mathforum.org/dr.math/   

Date: 02/09/2001 at 04:51:35
From: Siva Prasad Gummadi [T]
Subject: Re: Modular Arithmetic

Hello,

Thank you very much. That was a mistake. I should have verified it 
before mailing you. But I think this time I got some interesting 
points:

(1) For a^(p-1) = 1 mod p, it is necessary that a and p be relatively 
prime.

Proof: Assume that they are not relatively prime; the statement 
implies that

     a^(p-1) - (some integer)*p  = 1

So we can take out the common factor,
            
     (common factor) * (some integer) = 1,

which is obviously wrong. Hence the result.

(2) The statement that (p-1)! is not divisible by p is equivalent to 
saying that p is a prime OR p = 4.

Proof: It is obvious for a prime. Let p be other than prime. Let 
p = m*n. If p is not of the form k^m, then in the (p-1) terms of
(p-1)!, all the factors of p occur. So (p-1)! mod p = 0.
This narrows down the choice of p to numbers of the form k^m. Let us 
now assume that (k*m) < k^m. Then in (p-1)! we will have the 
following terms:

     (k*1),(k*2),(k*3),...,(k*m)

and thus (p-1)! is divisible by p or k^m. So, p must be of the form 
k^m, with k*m >= k^m. This implies that

     m >= k^(m-1)   or   log(m) >= (m-1)log(k)

Taking the log base 2, since k>=2,

     log m >= (m-1)   or   m >= 2^(m-1)

But this is true only for m=1 or m=2. We discard m=1, since it really 
does not suit the form k^m. So, m = 2. With this,

     m >= k^(m-1)   becomes   2 >= k

So, k=2. That means that p = k^m = 4, if it's not a prime.

You might already know these results. It's just out of curiosity that 
I am writing this. Can I say the following?

------
If a and p are relatively prime, then for the statement

     a^(p-1) = 1 mod p

to be true, the following condition on n is 'sufficient':

     p is a prime, OR
     p = 4.
------

Or, still better would be:

------
For the statement

     a^(p-1) = 1 mod p

to be true, the following is a necessary condition:

     a and p are relatively prime.

The following are sufficient conditions:

     p is a prime or p=4.
------

So, the necessary conditions are still unknown. Same with regard to 
the "least possible exponent" such that a^e = 1 mod p. I'll work on
these. Tell me if there are still any bugs in this.

G.Siva Prasad, MIEL, Bangalore

Date: 02/09/2001 at 19:31:24
From: Doctor Schwa
Subject: Re: Modular Arithmetic

>(1) For a^(p-1) = 1 mod p, it is necessary that a and p be 
relatively prime.

Indeed, and your proof is absolutely correct.

>(2) The statement that (p-1)! is not divisible by p is equivalent to 
>saying that p is a prime OR p = 4.

In number theory, it's customary to use "n" for a general integer, 
and reserve p for ones known to be prime. So I'd modify your notation
a bit,

     (n-1)! is not divisible by n iff n is prime or n = 4

but I'd certainly agree with the result.

>You might already know these results. It's just out of curiosity 
>that I am writing this. Can I say the following?

That's fine! The best way to do math is to discover it for yourself,
and then compare it with what other people have done, and then go on 
for yourself. I'm very impressed by your patience and by your 
interest in the subject.

>------
>If a and p are relatively prime, then for the statement
>
>     a^(p-1) = 1 mod p
>
>to be true, the following condition on n is 'sufficient':
>
>     p is a prime, OR
>     p = 4.
>------

I don't think so!

For instance, let's try p = 4, and a = 3. Your claim then is that 
3^3 = 1 (mod 4), but in fact it equals 3.

What went wrong? Even if (4-1)! is not divisible by 4, it's still 
true that you can't divide by it.

In other words, we know that 

     3^3 * (4-1)! = (4-1)! (mod 4)

and we want to conclude that 

     3^3 = 1 (mod 4)

but we can't conclude that because dividing by 2 is illegal (mod 4). 
The first statement says 3 * 2 = 2 (mod 4), which is true, and the 
second statement (after dividing by 2) would say 3 = 1 (mod 4), which 
is not true.

So it appears that only primes work, because the condition is not 
that (n-1)! not be divisible by n; the condition is that 
gcd((n-1)!,n) = 1.

I think the second statement has the same bugs: p must be prime (p=4 
doesn't work).

But I agree that there is still a lot that's unknown. Finding how 
MANY elements there are such that a^e = 1 (mod p) for any particular 
e is a problem with a known solution, but finding WHICH ONES have 
that e is unknown (at least to me).

There is a nice tricky bit of math involved in finding out whether
there are any elements not equal to 1 such that a^(n-1) = 1 (mod n) 
when n is not prime. I *think* I know enough to be able to answer 
this question definitively, but I haven't taken the time to write 
down and check my idea carefully.

My summary of what we have so far would be:

If n is prime, a^(n-1) = 1 (mod n) if and only if a is relatively 
prime to n.

If n is not prime, we don't know yet about a^(n-1), but there is a 
nice fact about a^(certain function of n) = 1 (mod n) for all a 
relatively prime to n. Do you know what that function is? It's named 
after Euler, and the answer can be found by searching the Dr. Math 
archives if you don't want to try to solve the problem yourself.

Thanks for the conversation!

- Doctor Schwa, The Math Forum
  http://mathforum.org/dr.math/