Questions about invertion of Euler's totient function

Question

in order, for an affine to work properly (so that you can uniquely decrypt from a ciphertext back to its corresponding plaintext), $a^{-1}$ must exist. For some $n$, some integers in $\{0, 1, …, n − 1\}$ do not have an inverse. For example, clearly $0$ is not invertible and, if $n= 26$, then all even numbers are not invertible. Euler's totient function, $\phi(n)$ enumerates the number of values in $\{0, 1, …, n − 1\}$ that are invertible. Look up how to compute Euler's totient function online and determine the number of integers in $\{0, 1, …, 25\}$ that are invertible.

I still have no idea how to deal with this question. Could anyone give me some idea?

Answer 1

The function $\phi(n)$ counts the number of integers in $\{0,\ldots,n-1\}$ which are invertible modulo $n$, i.e. numbers $m$ such that there is $a$ with $am \equiv 1 \bmod n$. These are precisely those that are relatively prime to $n$. This is the case because the GCD $(m,n)$ of two numbers $m$ and $n$ can always be written in the form $(m,n) = am + bn$ for some integers $a$ and $b$. If $(m,n) = 1$, then reducing mod $n$ gives $1 \equiv am \bmod n$, so that $a$ is an inverse for $m$ mod $n$.

You can determine whether two numbers are relatively prime by using the Euclidean algorithm to compute their GCD. Similarly, to compute the inverse of a residue class mod $n$, you can use the extended Euclidean algorithm.

In your case, you say you want to find all the invertible elements modulo $n$. To do this, you could factor $n$ and remove all the numbers from $\{0,\ldots,n-1\}$ which are divisible by any of the primes factors you get. In your case, $26 = 2 \cdot 13$. So the invertible elements mod 26 are the ones not divisible by either 2 or 13.

Answer 2

First of all, invertible elements here are invertible module $n$, i.e., $m$ is invertible if and only if there exists an integer $a$ such that $am\equiv 1\pmod n$.

Euler's totient function $\phi(n)$ is traditionally defined as the number of integers between $0$ and $n-1$ which are coprime to $n$. By this post, if $0\le m\le n-1$ is coprime with $n$, there exists integers $a, b$ such that $am+bn=1$. Here, $am\equiv 1-bn\equiv 1\pmod n,$ and hence is invertible. We have thus proved that all integers between $1$ and $n-1$ that are coprime to $n$ are invertible.

For the opposite direction, assume $0\le m\le n-1$ is invertible. If $m$ and $n$ are not coprime, they share some divisor $d>0.$ Since $m$ is invertible, there exists an integer $a$ such that $am\equiv 1\pmod n$, that is, for some integer $b,$ $am=1+bn.$ Herem $1=am-bn$, which is a contradiction since $am-bn$ is divisible by $d$, but $1$ is clearly not.

Thus, we have proved that the integers that are invertible modulo $n$ between $0$ and $n-1$ are precisely those that are coprime to $n$.

Going back to your question, by this formula, $\phi(26)=(1-\frac12)(1-\frac{1}{13})\cdot26=12.$