Proof of A^(de) = a mod n for All Integers a

[lttlbbygurl]

So I came across this problem in my textbook, but couldn't seem to solve it...

Let n be any squarefree integer (product of distinct primes). Let d
and e be positive integers such that de — 1 is divisible by p — 1 for every prime divisor p of n. (For example, this is the case if $$de \equiv 1 mod \phi(n)$$.) Prove that
$$a^{de} \equiv a mod n$$ for any integer a (whether or not it has a common factor with n).

 

[rasmhop]

I'm new here so hope it's ok to give a pretty much complete answer as this doesn't seem to be homework.

The fact that n is a squarefree integer strongly suggests that it would be simpler to show,
$$a^{de} \equiv a \textrm{ (mod p)}$$
For all prime factors p in n. We then use that all the prime factors are relatively prime to get the original congruence.

To establish such identities we normally require that gcd(p,a) = 1 so we can use Fermat's little theorem, but the problem explicitly states that we are not allowed to assume that so we need to consider the case p | a. However if this is the case clearly both sides of the congruences are congruent to 0 so we have established
$$a^{de} \equiv a \textrm{ (mod p)}$$
for primes p that divide a. Now we can assume gcd(p,a) = 1 in which case Fermat's Little theorem tells us
$$a^{p-1} \equiv 1 \textrm{ (mod p)}$$
Now we can raise both sides to the (de-1)/(p-1) power to get (this is integral since p-1 | de-1),
$$a^{de-1} \equiv 1 \textrm{ (mod p)}$$
From which the problem trivially follows when you multiply by a.