Euler’s Theorem

Euler’s Theorem states:

$$ a^{\phi(n)} \mod n = 1 $$

Where:

It is a generalisation of Fermat’s Theorem#.

Links to this page

TAC3121 Chapter 2: Finite Fields and Computational Number Theory

Euler’s Theorem
Rivest-Shamir-Adleman (RSA)

RSA works in both encryption and decryption due to the nature of the equation $de = 1 \mod \phi(n)$ which can be reformed into the equation $de = 1 + k \phi(n)$ (Modular Arithmetic#) and the fact that $M^{\phi(n)} \mod n = 1$ (Euler’s Theorem#). From decryption equation $C^d = M^{e \cdot d} = M^{1 + k \cdot \phi(n)} = M^1 \cdot (M^{\phi(n)})^k = M^1 \cdot 1^k = M^1 = M \mod n$, thus proved that RSA works.
Primitive Root

Considering $a^m \mod n = 1$, $GDC(a, n) = 1$, then there must exist for $m = \phi(n)$ (from Euler’s Theorem#) but may be smaller and once powers reach $m$, cycle will repeat. If the smallest is $m = \phi(n)$ then $a$ is called a Primitive Root.
Fermat’s Theorem

Fermat’s Theorem, aka Fermat’s Little Theorem, is a special case of #Euler’s Theorem which states:
Chosen Ciphertext Attack (CCA) on RSA

Note: $ed = 1$ due to $de = 1 + k \phi(n)$ (Modular Arithmetic#) and $M^{\phi(n)} \mod n = 1$ (Euler’s Theorem#). Full proof is shown in #Rivest-Shamir-Adleman (RSA).