Difference between revisions of "Euler's Totient Theorem"

Revision as of 16:43, 21 March 2023

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.

Direct 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 $\gcd(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}$ $\implies$ $a^{\phi (m)} \cdot (n_1 n_2 ... n_{\phi(m)}) \equiv n_1 n_2 ... n_{\phi(m)} \pmod{m}$ $\implies$ $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$ . $\square$

Group Theoretic Proof

Define the set $(\mathbb{Z}/n\mathbb{Z})^{\times}=\{a\in\mathbb{N}\,|\,1\le a <n \wedge \gcd(a,n)=1\}$ . Trivially we have that $|(\mathbb{Z}/n\mathbb{Z})^{\times}|=\varphi(n)$ . From there, there exists a sufficient $k$ such that $a^{k}\equiv 1\pmod{n}$ , and by Lagrange's Theorem $bk|\varphi(n)$ which means $a^{\varphi(n)}\equiv a^{bk} \equiv (a^{k})^b\equiv 1^b\equiv 1\pmod{n}$ , completing the proof. $\square$

Problems

Introductory

(BorealBear) Find the last two digits of $7^{81}-3^{81}$ . (Solution)
(BorealBear) Find the last two digits of $3^{3^{3^{3}}}$ . (Solution)
(2018 AMC 10B) Let $a_1,a_2,\dots,a_{2018}$ be a strictly increasing sequence of positive integers such that $a_1+a_2+\cdots+a_{2018}=2018^{2018}.$

What is the remainder when $a_1^3+a_2^3+\cdots+a_{2018}^3$ is divided by $6$ ?

$\textbf{(A)}\ 0\qquad\textbf{(B)}\ 1\qquad\textbf{(C)}\ 2\qquad\textbf{(D)}\ 3\qquad\textbf{(E)}\ 4$

(1983 AIME) Let $a_n=6^{n}+8^{n}$ . Determine the remainder upon dividing $a_ {83}$ by $49$ .

@@ Line 14: / Line 14: @@
 ==Group Theoretic Proof==
-Define the set <math>(\mathbb{Z}/n\mathbb{Z})^{\times}=\{a\in\mathbb{N}\,|\,1\le a <n \wedge \gcd(a,n)=1\}</math>. Trivially we have that <math>|(\mathbb{Z}/n\mathbb{Z})^{\times}|=\varphi(n)</math>. From there, there exists a sufficient <math>k</math> such that <math>a^{k}\equiv 1\pmod{n}</math>, and by Lagrange's Theorem <math>bk|\varphi(n)</math> which means
+Define the set <math>(\mathbb{Z}/n\mathbb{Z})^{\times}=\{a\in\mathbb{N}\,|\,1\le a <n \wedge \gcd(a,n)=1\}</math>. Trivially we have that <math>|(\mathbb{Z}/n\mathbb{Z})^{\times}|=\varphi(n)</math>. From there, there exists a sufficient <math>k</math> such that <math>a^{k}\equiv 1\pmod{n}</math>, and by [[Lagrange's Theorem]] <math>bk|\varphi(n)</math> which means
-<math>a^{\varphi(n)}\equiv a^{bk} \equiv (a^{k})^b\equiv 1^b\equiv 1\pmod{n} </math>, completing the proof <math>\square</math>
+<math>a^{\varphi(n)}\equiv a^{bk} \equiv (a^{k})^b\equiv 1^b\equiv 1\pmod{n} </math>, completing the proof. <math>\square</math>
 ==Problems==

Page

Toolbox

Search