MHB What is the role of Euler's Totient function in Fermat's Little Theorem?

[Sudharaka]

Hi everyone, :)

I was reading a thesis recently and encounter the following problem. Hope you can clarify.

\[de\equiv 1\mbox{ mod }\psi (n)\]

where $\psi$ is Euler's Totient function.

\begin{eqnarray}

(x^e)^{d}\mbox{ mod }n & = & x^{ed} \mbox{ mod }n \\

&=& x^{ed\mbox{ mod }\psi(n)} \mbox{ mod }n ~~~~~~~~~~~\mbox{(by Fermat's little theorem)}

\end{eqnarray}

I don't understand how the second line is obtained. How can we just add that $\mbox{ mod }\psi(n)$ part to the exponent?

 

[evinda]

Hi everyone, :)

I was reading a thesis recently and encounter the following problem. Hope you can clarify.

\[de\equiv 1\mbox{ mod }\psi (n)\]

where $\psi$ is Euler's Totient function.

\begin{eqnarray}

(x^e)^{d}\mbox{ mod }n & = & x^{ed} \mbox{ mod }n \\

&=& x^{ed\mbox{ mod }\psi(n)} \mbox{ mod }n ~~~~~~~~~~~\mbox{(by Fermat's little theorem)}

\end{eqnarray}

I don't understand how the second line is obtained. How can we just add that $\mbox{ mod }\psi(n)$ part to the exponent?

Hello! (Wave)

It is true,because of the following:

$$ a^b \equiv a^{b mod \phi(n) }\pmod n, \text{ if }a,b,n \in \mathbb{N} \text{ and } gcd(a,n)=1 $$

We conclude to this relation,from this one: $\displaystyle a^{\varphi(n)}=1\mod n$.

 

[evinda]

We take the Euclidean division of $b$ and $\phi(n)$.

$b=k \cdot \phi(n)+r, 0 \leq r <\phi(n) \text{ and } k \in \mathbb{Z} $

$a^b \mod n \equiv a^{k \phi(n) +r} \mod n \equiv (a^{\phi(n)})^k \cdot a^r \mod n \equiv 1 \cdot a^r \mod n \equiv a^{b \mod \phi(n)} \mod n $

Have you understood it?

 

[Nono713]

This is actually known as Euler's Theorem (Fermat's Little Theorem applies only to prime $n$). If you accept FLT, which can be proved in a multitude of ways, then it's straightforward to go from there to Euler's Theorem simply by applying the CRT. A way to state the theorem is that $(\mathbb{Z}/n\mathbb{Z})^\times \cong \mathbb{Z}_{\psi(n)}$, in other words, the multiplicative group of integers modulo $n$ is isomorphic to the additive group of integers modulo $\psi(n)$.

The isomorphism (which obviously involves the exponentiation operation in some way) is a bit involved, being defined piecewise from generators of the multiplicative groups of the distinct prime factors of $n$ and of $\psi(n)$ as per the CRT, but it is there, and you can intuitively think of it as "lifting" the group $(\mathbb{Z}/n\mathbb{Z})^\times$ to the group $\mathbb{Z}_{\psi(n)}$ via the exponentiation operation, the inverse operation being the discrete logarithm.

From this result it is clear that given $a^b \mod{n}$ with $a$ coprime to $n$, the exponent $b$ can be taken modulo $\psi(n)$. Eventually people end up taking this for granted as a property of modular arithmetic, but it is worth investigating to find out exactly why it holds.

As an aside, you can apply this property recursively by nested exponentiation, taking care to restrict yourself to $b$ coprime with $\psi(n)$, until you reach the trivial group, which (when ran backwards) shows that the structure of all these isomorphisms is ultimately determined by the distribution of the primes, something I find intrinsically beautiful. But while this has applications, it's probably not too relevant here.​

 

[Deveno]

This is actually known as Euler's Theorem (Fermat's Little Theorem applies only to prime $n$). If you accept FLT, which can be proved in a multitude of ways, then it's straightforward to go from there to Euler's Theorem simply by applying the CRT. A way to state the theorem is that $(\mathbb{Z}/n\mathbb{Z})^\times \cong \mathbb{Z}_{\psi(n)}$, in other words, the multiplicative group of integers modulo $n$ is isomorphic to the additive group of integers modulo $\psi(n)$.

The isomorphism (which obviously involves the exponentiation operation in some way) is a bit involved, being defined piecewise from generators of the multiplicative groups of the distinct prime factors of $n$ and of $\psi(n)$ as per the CRT, but it is there, and you can intuitively think of it as "lifting" the group $(\mathbb{Z}/n\mathbb{Z})^\times$ to the group $\mathbb{Z}_{\psi(n)}$ via the exponentiation operation, the inverse operation being the discrete logarithm.

​

I want to point out here that this is ONLY (necessarily) true when $n$ is prime, for $n$ composite, it is often the case that $(\Bbb Z_n)^{\times}$ is not cyclic, for example: with $n = 15$, we have:

$(\Bbb Z_{15})^{\times} = \{1,2,4,7,8,11,13,14\}$ and (mod 15):

$2^4 = 1$
$4^2 = 1$
$7^4 = 1$
$8^4 = (-7)^4 = 7^4 = 1$
$11^2 = (-4)^2 = 4^2 = 1$
$13^4 = (-2)^4 = 2^4 = 1$
$14^2 = (-1)^2 = 1$

(In cases like these it's actually easier to note that we have more than just one element of order 2).

*******

Nevertheless, it IS true that if $\text{gcd}(a,n) = 1$, that $a^{\phi(n)} = 1$. Fermat's Little Theorem is a "special case" of this, and this (Euler's Theorem) is turn is a special case of the consequence of Lagrange's Theorem, that for any group $G$, for any element $g \in G$, that $g^{|G|} = e$. This is because $(\Bbb Z_n)^{\times}$ is precisely the group of units of the ring $\Bbb Z_n$, which turns out to be precisely $\{k \text{ (mod }n): k \in \Bbb Z, \text{gcd}(k,n) = 1\}$.

This nifty little trick of "reducing the exponent mod $\phi(n)$" is used to reduce computation time in applications of RSA-style encryption. Some additional practical concerns arise in that case: $e$ is usually chosen to be a small bit-length prime (typically 3 or 7), and $n = pq$ is chosen so that the primes $p,q$ are about the same bit-length ("lopsided" prime factors are easier to guess), with $e$ invertible mod $\phi(pq)$.

As Bacterius noted, explicitly finding the isomorphism between $(\Bbb Z_p)^{\times}$ and $\Bbb Z_{p-1}$ is something of a headache: it involves specifically finding a generator, or primitive root, and there is no "well-defined" algorithm for doing this. Since there are $\phi(p-1)$ generators, trial-and-error usually produces one within a few tries, but it is known that there are some primes for which the first few elements of $(\Bbb Z_p)^{\times}$ are NOT generators (for example, the smallest primitive root modulo 191 is 19). It is known that the size of the smallest primitive root is "bounded asymptotically" (like many results of a similar nature about prime numbers). In lay terms, "we know where to look, but we don't have the exact address".​

 

[Nono713]

Very good point Deveno, got a bit ahead of myself with that statement, for composite $n$ it should be understood as an isomorphism between direct products of the groups for each distinct prime factor, since $(\mathbb{Z}/n\mathbb{Z})^\times$ need not be cylic (and is not, except for $p^k$ or $2p^k$ with prime $p$ and some positive integer $k$).

Even more puzzling is that while finding a generator is "easy" in the sense that statistically, a randomly selected group element is quite likely to be a generator, it is difficult to verify that it actually is a generator. One way of checking involves factoring $p - 1$, but it is unknown whether it can be done more efficiently (it might seem like a non-issue since you could just go ahead and do whatever you were doing under the assumption that you do have a generator and reject invalid outcomes, but since it is not an if-and-only-if situation you open yourself to false positives in your algorithm). Number theory doesn't want to give up its secrets :p

 

[Sudharaka]

Thanks everyone for your replies. I understood a lot by reading them. I have to go through them again to get the complete idea. :)