Why is $gcd(e, m-1) = 1$ in exponential cipher?

Question

The exponential cipher is defined as $$c = | p^{e} |_m $$ where $m$ is modulo and $e$ is a key.

Why does $gcd(e, m-1)$ have to be $1$?

Answer 1

The condition $\gcd(e, m-1)$ is the necessary and sufficient condition for us to have a value $d$ such that $de \equiv 1 \pmod{m-1}$.

If you're unfamiliar with modular inverses, this is easy to illustrate by example. Suppose that $m=11$, so that $m-1=10$, and working modulo $m-1$ is equivalent to looking at the last digit. If we have $e = 1, 3, 7, 9$, then we can multiply by $d = 1, 7, 3, 9$ respectively to get $de = 1, 21, 21, 81$, which all end in $1$. But if $\gcd(e,10) > 1$, then either

• $e$ is even, and no multiple of $e$ ends in an odd digit like $1$, or
• $e$ is divisible by $5$, so multiples of $e$ only end in $0$ or $5$.

We want $de \equiv 1 \pmod{m-1}$ so that we can decrypt: taking powers modulo $m$ repeats every $m-1$ steps, so $p^{k} \equiv p^{k \bmod m-1} \pmod{m}$, and therefore $$c^d \equiv p^{de} \equiv p^{de \bmod m-1} \equiv p \pmod m.$$