https://artofproblemsolving.com/wiki/api.php?action=feedcontributions&user=Summitwei&feedformat=atom AoPS Wiki - User contributions [en] 2021-07-27T17:11:57Z User contributions MediaWiki 1.31.1 https://artofproblemsolving.com/wiki/index.php?title=Euler%27s_Totient_Theorem&diff=67153 Euler's Totient Theorem 2015-02-01T22:31:04Z <p>Summitwei: changed &quot;relatively prime to to each other&quot; to &quot;relatively prime to m&quot;</p> <hr /> <div>'''Euler's Totient Theorem''' is a theorem closely related to his [[totient function]].<br /> <br /> == Theorem ==<br /> Let &lt;math&gt;\phi(n)&lt;/math&gt; be [[Euler's totient function]]. If &lt;math&gt;{a}&lt;/math&gt; is an integer and &lt;math&gt;m&lt;/math&gt; is a positive integer [[relatively prime]] to &lt;math&gt;a&lt;/math&gt;,in other words If &lt;math&gt;n&lt;/math&gt; is a positive integer, &lt;math&gt;\phi{(n)}&lt;/math&gt; is the number of integers in the range &lt;math&gt;\{1,2,3\cdots{,n}\}&lt;/math&gt; which are relatively prime to &lt;math&gt;n&lt;/math&gt;.Then &lt;math&gt;{a}^{\phi (m)}\equiv 1 \pmod {m}&lt;/math&gt;.<br /> <br /> == Credit ==<br /> <br /> This theorem is credited to [[Leonhard Euler]]. It is a generalization of [[Fermat's Little Theorem]], which specifies that &lt;math&gt;{m}&lt;/math&gt; is prime. For this reason it is also known as Euler's generalization or the Fermat-Euler theorem.<br /> <br /> ==Proof==<br /> <br /> Consider the set of numbers &lt;math&gt;A = &lt;/math&gt;{&lt;math&gt;n_1, n_2, ... n_{\phi(m)} &lt;/math&gt;} (mod m) such that the elements of the [[set]] are the numbers relatively [[prime]] to &lt;math&gt;m&lt;/math&gt;. <br /> It will now be proved that this set is the same as the set &lt;math&gt;B = &lt;/math&gt;{&lt;math&gt;an_1, an_2, ... an_{\phi(m)} &lt;/math&gt;} (mod m) where &lt;math&gt; (a, m) = 1&lt;/math&gt;. All elements of &lt;math&gt;B&lt;/math&gt; are relatively prime to &lt;math&gt;m&lt;/math&gt; so if all elements of &lt;math&gt;B&lt;/math&gt; are distinct, then &lt;math&gt;B&lt;/math&gt; has the same elements as &lt;math&gt;A&lt;/math&gt;. This means that &lt;math&gt; n_1 n_2 ... n_{\phi(m)} \equiv an_1 \cdot an_2 ... an_{\phi(m)}&lt;/math&gt;(mod m) → &lt;math&gt;a^{\phi (m)} \cdot (n_1 n_2 ... n_{\phi(m)}) \equiv n_1 n_2 ... n_{\phi(m)}&lt;/math&gt; (mod m) → &lt;math&gt;a^{\phi (m)} \equiv 1&lt;/math&gt; (mod m) as desired.<br /> <br /> == See also ==<br /> <br /> * [[Number theory]]<br /> * [[Modular arithmetic]]<br /> * [[Euler's totient function]]<br /> * [[Carmichael function]]<br /> <br /> [[Category:Number theory]]<br /> <br /> [[Category:Theorems]]</div> Summitwei