From: Michael T Thorpe <uthorm01@mcl.ucsb.edu> (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.