Originally posted by Acolyte
Following on from a problem set a while ago which I answered using Fermat's Little Theorem:
Find n composite such that (a,n) = 1 => a^n-1 = 1 (mod n) for all a.
(I don't know the answer, and my supervisor couldn't do it in the supervision at the time, saying I'm not an algebraist and looking something up in a book.)
I thought about this all afternoon, and accomplished the following:
1.I proved that such an n exists, and that there are more than one of them, but I would not wager that they are infinite in number;
2.I found a couple of examples of such numbers.
Let F(n):N->N be the number of integers less than or equal to n and relatively prime to it (the Euler totient function). A generalisation of FLT says that if gcd(a,n) = 1 then a^F(n) = 1 (mod n).
Then it can be shown that:
(a^f(n))^k = a^kF(n) = 1 (mod n)
For integers k. So all we need is some composite n such that F(n)|(n-1). I found necessary but not sufficient conditions that can be imposed on n for the above to be true, namely that n is an odd integer that is the product of at least three distinct primes, and is not divisible by the square of any prime. The proof of this is as follows:
To prove that it must be non-square-factorable, we realize that F is multiplicative and prove that n cannot be a square. So say n = p^2 for some prime p. Then F(n) = p^2 - p. So:
(n-1)/F(n) = [(p+1)(p-1)]/p(p-1) = (p+1)/p which is never an integer. So n may not have a aquare factor. Now if n has only two distinct prime factors, n = pq, then:
(m-1)/F(n) = (pq-1)/((p-1)(q-1) = 1 + 1/(q-1) + 1/(p-1) which cannot be an integer provided p and q are distinct. Thus some n satisfying your problem do exist, and are products of at least three distinct odd primes. I then fooled around with triples of small odd primes, and ruled out ones that failed to satisfy the condition F(n)|(n-1). The smallest one should be n = 3*11*17 = 561. But I am not an algebraist.