From: Michael T Thorpe (now at mike@pedantic.org)
Subject: Re: 42
> 42 | ( n^7 - n )
> 42 = phi(43) = phi(2 * 43)
Both these facts stem from Number Theory. For a good introduction to
Number
Theory, see "Elementary Number Theory and its Applications", Kenneth H.
Rosen,
Third Edition. (But note that the list of Merseinne primes is, of course,
a
bit out of date.)
The second fact incorporates Euler's phi function. phi(n) is basically
the
number of positive integers less than or equal to n which are relatively
prime to n. For instance:
n | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12
--------|---+---+---+---+---+---+---+---+---+----+----+----
phi(n) | 1 | 1 | 2 | 2 | 4 | 2 | 6 | 4 | 6 | 4 | 10 | 4
and so on. For a prime, p, and a nonnegative integer n, we see that:
phi( p^n ) = p^n - p^(n-1)
and for any two relatively prime nonnegative integers, m and n:
phi( m*n ) = phi(m)*phi(n)
This allows us to easily compute phi(n) for any n, once we have factored
n.
phi is a very useful function in Number Theory, and plays an important
role
in the RSA encryption "algorithm". (This "algorithm" is more of a
statement
of mathematical fact than a true encryption procedure.)
The first fact also rests on Number Theory, although it is a bit more
"intuitive" than the second. First, we see that:
n^7 - n = n * (n^6 - 1) = n * (n - 1) * (n^5 + n^4 + ... + 1)
Now either n or (n - 1) must be divisible by 2, so n^7 - n is divisible
by 2.
Although it can be shown that n^7 - n is also divisible by 3 and 7 (and
hence
by their product, 2*3*7=42) without Number Theory, it is much easier to
show
by using it. Using the phi function again, we see that:
a^(phi(n) - 1) = 1 mod n
where a is any integer. (mod means to take the remainder after dividing
each
side by n, and set them equal.) Thus, to show divisibility by 3, we must
show
n * (n^6 - 1) = 0 mod 3
but 1^6 and 2^6 are both equal to 1 mod 3, so whether n is 0, 1, or 2 mod
3,
the above holds. Hence, the expression is divisible by 3. For 7;
n * (n^6 - 1) = 0 mod 7
but since phi(7) = 6,
n^6 - 1 = 0 mod 7
and so the above holds. Since n^7 - n is divisible by 2, 3, and 7, it is
also
divisible by it's product, 42.
QED.
Michael Thorpe
uthorm01@mcl.ucsb.edu
P.S. - I can hardly do the subject justice via email. Please read Rosen
for
a far superior introduction to the subject.