Euler-Fermat extended

An often useful theorem in number theory is Euler's theorem (also known as the Fermat–Euler theorem or Euler's totient theorem), which says that:

If \(a\) and \(n\) are coprime positive integers, then

\( a^{\phi(n)}\equiv 1 (\text{mod }n) \)

where \(\phi(n)\) is Euler's totient function, counting how many of the integers \(1,2,\ldots,n\) are coprime with \(n\).

If, however, \(a\) and \(n\) are not coprime, we know for sure that the above does not hold. After all, if \(a\) and \(n\) share a common factor (greater than 1), any power of \(a\) will also share this factor and will not equal 1 modulo \(n\). However, if we formulate the equivalence as:

\( a^{\phi(n)+1}\equiv a (\text{mod }n) \)

(which, as it turns out, is equivalent to the original for \(a,n\) coprime), there are certain cases where this relation still holds even if \(a\) and \(n\) do share a common factor. A sufficient (though not necessary) condition is for \(n\) to be squarefree. Thus we obtain the following theorem:

Theorem. If \(a,n\) are positive integers where \(n\) is squarefree, then:

\( a^{\phi(n)+1}\equiv a (\text{mod }n) \)

where \(\phi(n)\) is Euler's totient function.

Proof.

Let \(n=p_1p_2\dots p_k\), where all the \(p_i\) are distinct primes. We can write \(a=bp_{c_1}p_{c_2}\dots p_{c_m}\), where the \(c_i\in\{1,2,\ldots,k\}\) are all distinct and \(b\) and \(n\) are coprime. Modulo \(p_{c_i}\) (for any \(i=1,2,\ldots, m\)) we have \( a^{\phi(n)+1}\equiv 0 \equiv a (\text{mod }p_{c_1}) \) since, of course, \(p_{c_1}\) divides \(a\). Analogously we know the same for all the other \(p_{c_i}\). Furthermore, we have:

\( a^{\phi(n)}\equiv 1 \left(\text{mod }\frac{n}{p_{c_1}\dots p_{c_m}}\right) \)

since \(a\) and \(\frac{n}{p_{c_1}\dots p_{c_m}}\) are coprime, and \(\phi\left(\frac{n}{p_{c_1}\dots p_{c_m}}\right)\) divides \(\phi(n)\). Hence we obtain the following system:

\( \begin{align*} a^{\phi(n)+1} &\equiv a (\text{mod }p_{c_1})\\ &\vdots\\ a^{\phi(n)+1} &\equiv a (\text{mod }p_{c_m})\\ a^{\phi(n)+1} &\equiv a \left(\text{mod }\frac{n}{p_{c_1}\dots p_{c_m}}\right). \end{align*} \)

Since all the modulo classes on the right are coprime, we can use the Chinese remainder theorem to see that there exists a unique solution for this system, namely

\( a^{\phi(n)+1} \equiv a \left(\text{mod }p_{c_1}\dots p_{c_m}\frac{n}{p_{c_1}\dots p_{c_m}}\right) \)

or, in other words:

\( a^{\phi(n)+1} \equiv a (\text{mod } n).\qquad\square \)

This shows us, for example, that \(a^5\equiv a (\text{mod }10)\) for any \(a\), since \(\phi(10)=4\) and \(10\) is squarefree. Hence the last digit of any number is equal to the last digit of its fifth power, a very useful fact in for example the problem which inspired this note.