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 and are coprime positive integers, then
where is Euler's totient function, counting how many of the integers are coprime with .
If, however, and are not coprime, we know for sure that the above does not hold. After all, if and share a common factor (greater than 1), any power of will also share this factor and will not equal 1 modulo . However, if we formulate the equivalence as:
(which, as it turns out, is equivalent to the original for coprime), there are certain cases where this relation still holds even if and do share a common factor. A sufficient (though not necessary) condition is for to be squarefree. Thus we obtain the following theorem:
Theorem. If are positive integers where is squarefree, then:
where is Euler's totient function.
Let , where all the are distinct primes. We can write , where the are all distinct and and are coprime. Modulo (for any ) we have since, of course, divides . Analogously we know the same for all the other . Furthermore, we have:
since and are coprime, and divides . Hence we obtain the following system:
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
or, in other words:
This shows us, for example, that for any , since and 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.