Euler's theorem

In number theory, Euler's theorem (also known as the Fermat–Euler theorem or Euler's totient theorem) states that, if n and a are coprime positive integers, then a φ ( n ) {\displaystyle a^{\varphi (n)}} is congruent to 1 {\displaystyle 1} modulo n, where φ {\displaystyle \varphi } denotes Euler's totient function; that is a φ ( n ) ≡ 1 ( mod n ) . {\displaystyle a^{\varphi (n)}\equiv 1{\pmod {n}}.} In 1736, Leonhard Euler published a proof of Fermat's little theorem (stated by Fermat without proof), which is the restriction of Euler's theorem to the case where n is a prime number. Subsequently, Euler presented other proofs of the theorem, culminating with his paper of 1763, in which he proved a generalization to the case where n is not prime. The converse of Euler's theorem is also true: if the above congruence is true, then a {\displaystyle a} and n {\displaystyle n} must be coprime. The theorem is further generalized by some of Carmichael's theorems. The theorem may be used to easily reduce large powers modulo n {\displaystyle n} . For example, consider finding the ones place decimal digit of 7 222 {\displaystyle 7^{222}} , i.e. 7 222 ( mod 10 ) {\displaystyle 7^{222}{\pmod {10}}} . The integers 7 and 10 are coprime, and φ ( 10 ) = 4 {\displaystyle \varphi (10)=4} . So Euler's theorem yields 7 4 ≡ 1 ( mod 10 ) {\displaystyle 7^{4}\equiv 1{\pmod {10}}} , and we get 7 222 ≡ 7 4 × 55 + 2 ≡ ( 7 4 ) 55 × 7 2 ≡ 1 55 × 7 2 ≡ 49 ≡ 9 ( mod 10 ) {\displaystyle 7^{222}\equiv 7^{4\times 55+2}\equiv (7^{4})^{55}\times 7^{2}\equiv 1^{55}\times 7^{2}\equiv 49\equiv 9{\pmod {10}}} . In general, when reducing a power of a {\displaystyle a} modulo n...