View source for Euler's Totient Theorem

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

== Theorem ==
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 ==

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.

==Direct Proof==

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

==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
<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==

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

===Intermediate===
* Suppose

<cmath>x \equiv 2^4 \cdot 3^4 \cdot 7^4+2^7 \cdot 3^7 \cdot 5^6 \pmod{7!}</cmath>

Find the remainder when <math>\min{x}</math> is divided by 1000. ([[Problems Collection|Source and solution]])

== See also ==

* [[Number theory]]
* [[Modular arithmetic]]
* [[Lagrange's Theorem]]
* [[Euler's totient function]]
* [[Carmichael function]]

[[Category:Number theory]]

[[Category:Theorems]]