Difference between revisions of "Euler's Totient Theorem"

(Introductory)
(2 intermediate revisions by the same user not shown)
Line 16: Line 16:
  
 
===Introductory===
 
===Introductory===
*(BorealBear) Find the last two digits of <math> 5^{81}-3^{81} </math>.  
+
*(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>.  
+
*(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>
 
*([[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>?  
 
What is the remainder when <math>a_1^3+a_2^3+\cdots+a_{2018}^3</math> is divided by <math>6</math>?  
Line 23: Line 23:
 
<cmath>\textbf{(A)}\ 0\qquad\textbf{(B)}\ 1\qquad\textbf{(C)}\ 2\qquad\textbf{(D)}\ 3\qquad\textbf{(E)}\ 4</cmath>
 
<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>.
 
*([[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