Show that an Affine Cipher with a prime modulo $N$ fixes exactly one plaintext message $m$ in $\mathcal M$

Question

Let $N$ be a positive integer. Consider the affine cipher on the space of plaintext messages $\mathcal M=\mathbb Z/N\mathbb Z$ with encryption function $e(m)=am+b$ where $a,b\;\epsilon\; \mathbb Z/N\mathbb Z$ and $a\neq1\pmod{N}$. Also assume $N$ is prime. $$$$ I've been playing around for this for quite some time at this point and haven't gotten too far. I have found that for $m=-ba^{-1}$ we get $e(-ba^{-1})\equiv a(-ba^{-1})+b\equiv (aa^{-1})-b+b\equiv -b+b\equiv 0\pmod{N}$. I don't think that's very useful, however, I don't really know how else to attack this problem. If someone could just point me in the right direction I'd much appreciate it.

Answer 1

Suppose that $f: \mathbb{Z}_p \to \mathbb{Z}_p$ by $f(x) = ax+b$ is your affine map, where $a \neq 0,1$. (You should exclude $a =0$ or you don't have a bijection. If you for some reason allow $a=0$ the statement is still correct since $x=b$ will be the unique fixed point.) You are asking about fixed points $x$ from the message space $\mathbb{Z}_p$ so that $f(x)=x$. Well, just write it out: $$ f(x) = ax + b=x. $$ Now do the algebra: $$ ax-x=-b \Rightarrow (a-1)x=-b. $$ Since you've assumed $a \neq 1$, we know $a-1 \neq 0$, so we can invert $a-1$ since we are working mod $p$ and all non-zero elements are invertble: $$ x=-(a-1)^{-1}b. $$ Hence you can check that (a) this $x$ is indeed fixed by $f$ and (b) it's the only fixed point (use the same idea above).