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 aa and nn are coprime positive integers, then

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

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

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

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

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

Theorem. If a,na,n are positive integers where nn is squarefree, then:

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

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

Proof.

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

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

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

aϕ(n)+1a(mod pc1)aϕ(n)+1a(mod pcm)aϕ(n)+1a(mod npc1pcm). \begin{aligned} 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{aligned}

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ϕ(n)+1a(mod pc1pcmnpc1pcm) 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ϕ(n)+1a(mod n). a^{\phi(n)+1} \equiv a (\text{mod } n).\qquad\square

This shows us, for example, that a5a(mod 10)a^5\equiv a (\text{mod }10) for any aa, since ϕ(10)=4\phi(10)=4 and 1010 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
4 years, 6 months ago

No vote yet
1 vote

  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:

  • Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
  • Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
  • Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
  • Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

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](https://brilliant.org)example 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×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 123 \boxed{123}

Comments

There are no comments in this discussion.

×

Problem Loading...

Note Loading...

Set Loading...