Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "Euler's Totient Theorem"

m (→‎Proof: fixed latex)
(→‎Credit)
Line 6: Line 6:
 
== Credit ==
 
== Credit ==
  
−
This theorem is credited to [[Leonhard Euler]].  It is a generalization of [[Fermat's Little Theorem]], which specifies that <math>{m}</math> is prime. For this reason it is also known as Euler's generalization or the Fermat-Euler theorem.
+
This theorem is credited to [[Leonhard Euler]].  It is a generalization of [[Fermat's Little Theorem]], which specifies it when <math>{m}</math> is prime. For this reason it is also known as Euler's generalization or the Fermat-Euler theorem.
  
 
==Proof==
 
==Proof==

Revision as of 09:56, 26 June 2020

Euler's Totient Theorem is a theorem closely related to his totient function.

Theorem

Let $\phi(n)$ be Euler's totient function. If $n$ is a positive integer, $\phi{(n)}$ is the number of integers in the range $\{1,2,3\cdots{,n}\}$ which are relatively prime to $n$. If ${a}$ is an integer and $m$ is a positive integer relatively prime to $a$,Then ${a}^{\phi (m)}\equiv 1 \pmod {m}$.

Credit

This theorem is credited to Leonhard Euler. It is a generalization of Fermat's Little Theorem, which specifies it when ${m}$ is prime. For this reason it is also known as Euler's generalization or the Fermat-Euler theorem.

Proof

Consider the set of numbers $A =${$n_1, n_2, ... n_{\phi(m)}$}$\pmod{m}$ such that the elements of the set are the numbers relatively prime to $m$. It will now be proved that this set is the same as the set $B =${$an_1, an_2, ... an_{\phi(m)}$}$\pmod{m}$ where $(a, m) = 1$. All elements of $B$ are relatively prime to $m$ so if all elements of $B$ are distinct, then $B$ has the same elements as $A$. In other words, each element of $B$ is congruent to one of $A$.This means that $n_1 n_2 ... n_{\phi(m)} \equiv an_1 \cdot an_2 ... an_{\phi(m)}$$\pmod{m}$ → $a^{\phi (m)} \cdot (n_1 n_2 ... n_{\phi(m)}) \equiv n_1 n_2 ... n_{\phi(m)}$$\pmod{m}$ → $a^{\phi (m)} \equiv 1$$\pmod{m}$ as desired. Note that dividing by $n_1 n_2 ... n_{\phi(m)}$ is allowed since it is relatively prime to $m$.

See also

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Euler%27s_Totient_Theorem&oldid=126566"