Associated Topics || Dr. Math Home || Search Dr. Math

### Exploring Fermat's Little Theorem

Date: 02/08/2001 at 00:59:12
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.

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
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

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).

>where the proof is given for this. I'll use the symbols used there.

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
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.

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
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.

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
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/

Associated Topics:
College Number Theory

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search