Prove Euler's Theorem when the integers are not relatively prime [duplicate]

How can I prove Euler's Theorem:

$$x^{\phi(m)+1} \equiv x \pmod m$$

is still true when $x$ is not relatively prime to $m$?

Edit: when m=pq where p and q are distinct primes

Solution 1:

(Original answer before the question was amended to specify that $m$ is the product of distinct primes)

It isn't. For example, $2^{\phi(4)+1} \not\equiv 2 \pmod{4}$.

New answer. It does hold in the particular case that $m$ is square-free, though. In that case, consider the situation modulo each prime factor of $m$ in turn. Then either $p\mid x$, or $x$ is coprime to $p$. In the first case it is obvious that $x^{\mathit{whatever}}\equiv x\pmod p$.

Otherwise, since $\phi(m)=k\phi(p)$ for some $k$ we can then say $$ x \equiv x^{\phi(p)+1} = x^{\phi(p)}x \equiv x^{\phi(p)}x^{\phi(p)+1} = x^{2\phi(p)}x \equiv \cdots = x^{k\phi(x)}x = x^{\phi(m)+1} \pmod p$$ by repeated application of Euler's theorem for $p$.

Since the equivalence holds modulo every prime factor of $m$, it then also holds modulo $m$. (Namely, since each of the prime factors divides $x^{\phi(m)+1}-x$, their product does too).