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.
Proof.
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.
Easy Math Editor
This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.
When posting on Brilliant:
*italics*
or_italics_
**bold**
or__bold__
paragraph 1
paragraph 2
[example link](https://brilliant.org)
> This is a quote
\(
...\)
or\[
...\]
to ensure proper formatting.2 \times 3
2^{34}
a_{i-1}
\frac{2}{3}
\sqrt{2}
\sum_{i=1}^3
\sin \theta
\boxed{123}
Comments
There are no comments in this discussion.