Euler's theorem MY POINT OF VIEW

THANKING YOU ALL MY GODS.

THANKING YOU LORD SHIVA FOR GIVING SUCH WONDERFULLIFE.

THANKING YOU MOM AND DAD.

                                                       OM JAI SHRI RAMA

This article is about Euler's theorem in number theory. For other uses, see List of topics named after Leonhard Euler.

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

${\displaystyle a^{\varphi (n)}\equiv 1{\pmod {n}}}$

where ${\displaystyle \varphi (n)}$ is Euler's totient function. (The notation is explained in the article modular arithmetic.) In 1736, Leonhard Euler published his proof of Fermat's little theorem,^[1] which Fermat had presented without proof. Subsequently, Euler presented other proofs of the theorem, culminating with "Euler's theorem" in his paper of 1763, in which he attempted to find the smallest exponent for which Fermat's little theorem was always true.^[2]

The converse of Euler's theorem is also true: if the above congruence is true, then ${\displaystyle a}$ and ${\displaystyle n}$ must be coprime.

The theorem is a generalization of Fermat's little theorem, and is further generalized by Carmichael's theorem.

The theorem may be used to easily reduce large powers modulo ${\displaystyle n}$. For example, consider finding the ones place decimal digit of ${\displaystyle 7^{222}}$, i.e. ${\displaystyle 7^{222}{\pmod {10}}}$. Note that 7 and 10 are coprime, and ${\displaystyle \varphi (10)=4}$. So Euler's theorem yields ${\displaystyle 7^{4}\equiv 1{\pmod {10}}}$, and we get ${\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 ${\displaystyle a}$ modulo ${\displaystyle n}$ (where ${\displaystyle a}$ and ${\displaystyle n}$ are coprime), one needs to work modulo ${\displaystyle \varphi (n)}$ in the exponent of ${\displaystyle a}$:

if ${\displaystyle x\equiv y{\pmod {\varphi (n)}}}$, then ${\displaystyle a^{x}\equiv a^{y}{\pmod {n}}}$.

Euler's theorem is sometimes cited as forming the basis of the RSA encryption system, however it is insufficient (and unnecessary) to use Euler's theorem to certify the validity of RSA encryption. In RSA, the net result of first encrypting a plaintext message, then later decrypting it, amounts to exponentiating a large input number by ${\displaystyle k\varphi (n)+1}$, for some positive integer ${\displaystyle k}$. In the case that the original number is relatively prime to ${\displaystyle n}$, Euler's theorem then guarantees that the decrypted output number is equal to the original input number, giving back the plaintext. However, because ${\displaystyle n}$ is a product of two distinct primes, ${\displaystyle p}$ and ${\displaystyle q}$, when the number encrypted is a multiple of ${\displaystyle p}$ or ${\displaystyle q}$, Euler's theorem does not apply and it is necessary to use the uniqueness provision of the Chinese Remainder Theorem. The Chinese Remainder Theorem also suffices in the case where the number is relatively prime to ${\displaystyle n}$, and so Euler's theorem is neither sufficient nor necessary.