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.


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.

Note by Tijmen Veltman
3 years, 8 months ago

No vote yet
1 vote

  Easy Math Editor

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. list

  1. numbered
  2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1

paragraph 2

paragraph 1

paragraph 2

[example link]( link
> This is a quote
This is a quote
    # I indented these lines
    # 4 spaces, and now they show
    # up as a code block.

    print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.
2 \times 3 \( 2 \times 3 \)
2^{34} \( 2^{34} \)
a_{i-1} \( a_{i-1} \)
\frac{2}{3} \( \frac{2}{3} \)
\sqrt{2} \( \sqrt{2} \)
\sum_{i=1}^3 \( \sum_{i=1}^3 \)
\sin \theta \( \sin \theta \)
\boxed{123} \( \boxed{123} \)


There are no comments in this discussion.


Problem Loading...

Note Loading...

Set Loading...