Can phi(n) divide n - 1, if n is not a prime? If n contains a power of a prime, p (the power being bigger than or equal to 2), then there's a contradiction, because phi(n) is divisible by p, but n-1 is not divisible by p. Also, n is not even, because n-1 would be odd, which cannot be divisible by phi(n) [unless n = 2 exactly]. Claim: if r and s are odd, then (r-1)(s-1) > 1/2 * rs. Consider (r-1)(s-1) = rs - (r+s) + 1 > rs/2 iff rs/2 + 1 > (r+s) Let r < s, then r+s < 2s. But if r >= 5, then rs/2 > 2s. So it is enough to show it for r = 3 (and r<s). Then we must show that 2(s-1) > 3/2 s, where s >= 5, but this is clear. Now we can build up (p1-1)(p2-1)(p3-1) > (p1*p2/2)*(p3-1) > p1*p2*p3/2, etc. So, for phi(n) to divide n - 1, since n does not contain a non-trivial power of a prime, n is of the form p1*p2*...*pn, where all of the pi's are odd. But then phi(n) > 1/2 * n, so it cannot divide n - 1. So for your original question, yes, I think so. -----Original Message----- From: math-fun-bounces@mailman.xmission.com [mailto:math-fun-bounces@mailman.xmission.com] On Behalf Of David Wilson Sent: Friday, December 11, 2009 1:46 PM To: math-fun Subject: [math-fun] question x == 1 (mod phi(x)) ==> x prime? (x >= 2) _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun