Sorry if this is belated. I sent it a few days ago and it appears to
have not been received.
One of the main theorems of elementary number theory is the
following:
For all integers "a" and "m" such that gcd(a,m) = 1,
a^(phi(m)) = 1 (mod m)
If you are not familiar with congruence classes, then the last statement
is equivalent to: a^(phi(m)) - 1 is divisible by m.
(In fact, x=y (mod m) can be defined as meaning x-y is divisible by m)
phi(m) is Euler's Totient Function, which is defined as follows:
phi(m) = The number of integers between 1 and m that are relatively
prime to m. (an integer k is relatively prime to m if gcd(m,k) = 1)
As an exercise, prove the following:
phi(m) = m*Prod[(1 - 1/p)] where the product
is taken over all prime factors of m.
It is apparent that for all primes p, phi(p) = p-1,
and a=2 is relatively prime to all primes p greater than 2.
So it follows from the main theorem that 2^(p-1) - 1 is divisible by p
for all primes p>2.
Proof of the main theorem (without group theory):
Definition 1:
A reduced residue system mod m is a set of integers S such that:
1) gcd(x,m) = 1 for all x in S.
2) S has phi(m) elements
3) No two elements of S are congruent modulo m
(ie, x=y (mod m) implies x=y )
Lemma 1: Let S be a reduced residue system mod m, then
the following is also a reduced residue system mod m:
T = { a*x | x in S }
where a is any fixed element in S.
Lemma 1 proof:
To show T is a reduced residue system we need to show it satisfies
the three conditions in the definition.
Condition 1: Let u be any element of T, so that u=a*x for some
x in S. Since a and x are both elements of S, a reduced residue system,
we know that gcd(a,m) = 1 and gcd(x, m) = 1. It follows
that gcd(a*x, m) = 1, so gcd(u,m) = 1.
Condition 2: This is obvious. There will be no collapsing since
a is nonzero. a*x = a*y implies x=y.
Condition 3:
Consider any two elements u and v of T which are congruent,
By definition, u = a*x_1 and v = a*x_2
for some elements x_1 and x_2 of S. But
if a*x_1 = a*x_2 (mod m), then it follows that
x_1 = x_2 (mod m) since gcd(a,m) = 1.
So it must be that x_1 = x_2 (since S is a reduced residue system)
thus u=v.
QED.
Moving on:
Lemma 2: Let S, and T be any two reduced residue systems.
Then Prod[over x in T, x] = Prod[over x in S, x] (mod m)
Lemma 2 Proof:
Note that if a=b (mod m), then gcd(m,a) = gcd(m,b).
Thus, each congruence class is either relatively prime to m
or not. There are only phi(m) congruence classes whose elements
are relatively prime to m, and thus a reduced residue
system must be made up of one element from each of these
congruence classes. Thus, for every element of S,
there must exist one and only one element of T in the same
congruence class. Thus, the the lemma holds. QED.
So now, let S be any reduced residue system, and
T = { ax | x in S } for some a in S.
By Lemma 1 and 2, Prod[over x in T, x] = Prod[over x in S, x] (mod m)
But also:
Prod[over x in T, x] = Prod[over x in S, a*x] =
a^(phi(m)) * Prod[over x in S, x]
Thus,
a^(phi(m)) * Prod[over x in S, x] = Prod[over x in S, x] (mod m)
a^(phi(m)) = 1 (mod m)
(we are allowed to cancel since the product is relatively prime to m)
QED.
A second, more insightful way, is to generalize and show that the set of
congruence classes mod m relatively prime to m forms a group under
multiplication. Then, since the order of an element divides the order of
the group, and the order of the group is phi(m), we know that a^(phi(m))
= 1 (mod m)
As for your second theorem, it is also commonly known that:
x^(ab) - 1 = (x^a - 1)(x^(a(b-1)) + x^(a(b-2)) + ... + 1)
Which means x^n - 1 is composite if x>2 (let a=1,b=n) or if
n is composite.
If you want some better explanations of these concepts, you may
want to seek out some elementary number theory books, such as
"Elements of Number Theory" by Pettofrezzo and Byrkit.
PS. This was typed in a hurry, if anyone sees any mistakes, let me know.
Regards,
David T. Meyer ([EMAIL PROTECTED])
_________________________________________________________________________
Unsubscribe & list info -- http://www.ndatech.com/mersenne/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
