Difference between revisions of "Euler's Totient Theorem"

(Proof)
(Introductory)
(22 intermediate revisions by 11 users not shown)
Line 1: Line 1:
'''Euler's Totient Theorem''' is a theorem closely related to his [[totient function|function of the same name]].
+
'''Euler's Totient Theorem''' is a theorem closely related to his [[totient function]].
  
 
== Theorem ==
 
== Theorem ==
Let <math>\phi(n)</math> be [[Euler's totient function]]. If <math>{a}</math> is an integer and <math>m</math> is a positive integer [[relatively prime]] to <math>a</math>, then <math>{a}^{\phi (m)}\equiv 1 \pmod {m}</math>.
+
Let <math>\phi(n)</math> be [[Euler's totient function]]. If <math>n</math> is a positive integer, <math>\phi{(n)}</math> is the number of integers in the range <math>\{1,2,3\cdots{,n}\}</math> which are relatively prime to <math>n</math>. If <math>{a}</math> is an integer and <math>m</math> is a positive integer [[relatively prime]] to <math>a</math>,Then <math>{a}^{\phi (m)}\equiv 1 \pmod {m}</math>.
  
 
== 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 known as Euler's generalization and Fermat-Euler as well.
+
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==
  
Consider the set of numbers <math>A = </math>{<math>n_1, n_2, ... n_{\phi(m)} </math>} (mod m) such that the elements of the set are the numbers relatively prime to each other. It will now be proved that this set is the same as the set  <math>B = </math>{<math>an_1, an_2, ... an_{\phi(m)} </math>} (mod m) where <math> (a, m) = 1</math>. All elements of <math>B</math> are relatively prime to <math>m</math> so if all elements of <math>B</math> are distinct, then <math>B</math> has the same elements as <math>A</math>. This means that <math> n_1 n_2 ... n_{\phi(m)} \equiv an_1 \cdot an_2 ... an_{\phi(m)}</math>(mod m) => <math>a^{\phi (m)} \cdot (n_1 n_2 ... n_{\phi(m)}) \equiv n_1 n_2 ... n_{\phi(m)}</math> (mod m) => <math>a^{\phi (m)} \equiv 1</math> (mod m) as desired.
+
Consider the set of numbers <math>A = \{ n_1, n_2, ... n_{\phi(m)} \} \pmod{m}</math> such that the elements of the [[set]] are the numbers relatively [[prime]] to <math>m</math>.  
 +
It will now be proved that this set is the same as the set  <math>B = \{ an_1, an_2, ... an_{\phi(m)} \} \pmod{m}</math> where <math> (a, m) = 1</math>. All elements of <math>B</math> are relatively prime to <math>m</math> so if all elements of <math>B</math> are distinct, then <math>B</math> has the same elements as <math>A.</math> In other words, each element of <math>B</math> is congruent to one of <math>A</math>.This means that <math> n_1 n_2 ... n_{\phi(m)} \equiv an_1 \cdot an_2 ... an_{\phi(m)}</math><math>\pmod{m}</math> <math>a^{\phi (m)} \cdot (n_1 n_2 ... n_{\phi(m)}) \equiv n_1 n_2 ... n_{\phi(m)}</math><math>\pmod{m}</math> <math>a^{\phi (m)} \equiv 1</math><math>\pmod{m}</math> as desired. Note that dividing by <math> n_1 n_2 ... n_{\phi(m)}</math> is allowed since it is relatively prime to <math>m</math>.
 +
 
 +
==Problems==
 +
 
 +
===Introductory===
 +
*(BorealBear) Find the last two digits of <math> 7^{81}-3^{81} </math>. ([[Euler's Totient Theorem Problem 1 Solution|Solution]])
 +
*(BorealBear) Find the last two digits of <math> 3^{3^{3^{3}}} </math>. ([[Euler's Totient Theorem Problem 2 Solution|Solution]])
 +
*([[2018 AMC 10B Problems/Problem 16|2018 AMC 10B]]) Let <math>a_1,a_2,\dots,a_{2018}</math> be a strictly increasing sequence of positive integers such that <cmath>a_1+a_2+\cdots+a_{2018}=2018^{2018}.</cmath>
 +
What is the remainder when <math>a_1^3+a_2^3+\cdots+a_{2018}^3</math> is divided by <math>6</math>?
 +
 
 +
<cmath>\textbf{(A)}\ 0\qquad\textbf{(B)}\ 1\qquad\textbf{(C)}\ 2\qquad\textbf{(D)}\ 3\qquad\textbf{(E)}\ 4</cmath>
 +
*([[1983 AIME Problems/Problem 6|1983 AIME]]) Let <math>a_n=6^{n}+8^{n}</math>. Determine the remainder upon dividing <math>a_ {83}</math> by <math>49</math>.
  
 
== See also ==
 
== See also ==

Revision as of 14:12, 23 April 2021

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$.

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$.

See also