affine cipher $ax+b \mod m$

Question

I have an affine chipher

$ax+b \mod m$

For what values $a,b$ is this an injective encryption function?

From what i understand thats the case when $a$ and $m$ are coprime, so $gcd(a,m)=1$ and the value of $b$ doenst really matter.

I'd like to understand why $gcd(a,m)=1$ is mandatory here. So what happens if there is a common divisior $>1$ and why does it mean the function is no longer injective?

Answer 1

"Not injective" means that there exist $x_1$ and $x_2$ ($x_1 \neq x_2$) such that $ax_1+b=ax_2+b \pmod m.$ The latter can be reconfigured as follows: $a(x_1-x_2)=0 \pmod m$ (here $x_1-x_2 \neq 0$ since $x_1 \neq x_2$). And that is possible if and only if $a$ is a divisor of $0$ in $\mathbb{Z}_m$, i.e. $\text{gcd}(a,m)>1$.

Answer 2

Let $g=\text{gcd}(a,m)$, and let $y=m/g$. Then $y$ is an integer, and if $g>1$ then $0< y<m$, so $y\not\equiv 0\pmod{m}$. If we set $f(x)=ax+b \pmod{m}$, then we have $f(0)\equiv b\equiv f(y)$, showing that $f$ is not injective.

Answer 3

If $\,a,m\,$ have a common divisor $\,\color{#0a0}{d > 1}$ then $\,{\rm mod}\ m\!:\ \color{#c00}{a(m/d)}\equiv (a/d)m\equiv\color{#c00} 0,\ $ but $\ \color{#0a0}{m/d\not\equiv 0}.\, $ Therefore if $\,x' = m/d+x\,$ then $\,f(x') \equiv ax'\!+b \equiv \color{#c00}{a(m/d)}+ax+b \equiv ax+b \equiv f(x)\,$ while $\,\color{#0a0}{x'\not\equiv x},\ $ hence we conclude that $\,f(x) = ax+b\,$ is not injective.

Remark $\ $ If you know some linear algebra then you may notice the analogy with

$$\begin{align} &x\,\mapsto Ax + b\ \text{ is injective}\\ \iff\ & x\,\mapsto Ax\ \text{ is injective}\\ \iff\ & x\,\mapsto Ax \ \text{ has kernel} = \{0\}\end{align}\qquad$$

What I proved above is (the contrapositive of) the arrow going from top to bottom, i.e. a nonzero element of the kernel immediately yields a counterexample to injectivity.

This is an example of a result that generalizes from vector spaces to $R$-modules, those linear structures that arise by generalizing vector spaces to permit coefficients from arbitrary (commutative) rings (vs. only fields), e.g. $\,R = \Bbb Z/m = $ integers mod $\,m\,$ in the OP.

Such linearity is quite ubiquitous, e.g. the well know decomposition of solutions spaces of inhomogeneous linear differential and difference equations (recurrences) into the sum of a particular solution plus any solution of the associated homogeneous equation (you may have met such affine spaces in your linear algebra course).