# Show the affine cipher $e(m)=am$ fixes at least two messages in $\mathcal M=\mathbb Z/N\mathbb Z$

Let $$N$$ be an even integer. Consider the affine cipher on the space of plaintext messages $$\mathcal M=\mathbb Z/N\mathbb Z$$ with encryption function $$e(m)=am$$ where $$a\;\epsilon\; \mathbb Z/N\mathbb Z$$ and $$a\neq1\pmod{N}$$. Assume $$a$$ is invertible modulo $$N$$.

I know that $$0$$ is going to be a fixed message as $$e(0)\equiv a(0)\equiv 0 \pmod{N}$$. Also I know that the other fixed message is going to be of the form $$e(m_1)\equiv am_1\equiv m_1\pmod{N}$$ $$m_1\equiv a^{-1}m_1 \pmod{N}$$ but I am not sure how to find this without assuming it exists first. I tried to solve the same equation by: $$am_1-m_1\equiv m_1(a-1)\equiv 0 \pmod{N}$$ but this is also using the same assumption, right?

• You should use the hypothesis that $N$ is even. In that case, is $a$ even or odd? How about $a-1$? – FredH Feb 25 at 18:46
• So then $a$ has to be odd because it is invertible.. so $a-1$ is even – joseph Feb 25 at 18:47
• I did think of going this route but I couldn't figure out how that would eventually help me get my same input without assuming it already exists – joseph Feb 25 at 18:48

Write $$N=2M$$. Since $$a$$ is invertible mod $$N$$, you have $$\gcd(a,N)=1$$. Hence, $$a$$ cannot be even since $$N$$ is even. Thus $$a$$ is odd and so $$a=1+2k$$ for some $$k$$. Then $$e(M)=aM=(1+2k)M=M + 2kM = M + kN = M \bmod N.$$ But clearly $$M$$ isn't the class of $$0$$ so this is your other fixed point.
• why did you start by writing $N=2M$? I know N must be even but why does it have to be two times $m$? Or I guess how did you know this ahead of time? – joseph Feb 25 at 19:00
• That's what an even number looks like. I used this to find out that $M$ was going to work. – Randall Feb 25 at 19:02
• IOW, I showed that $N/2$ will always be fixed. So is $0$, so QED – Randall Feb 25 at 19:03
• Yeah I know that an even number is given by $N=ex$ for some $x:\ \epsilon \mathbb Z$ I'm just wondering how you knew to write it as $a=M$? Did you just find that by playing with actual numbers ahead of time and then going back and using that from the beginning or was there some deeper intuition used? – joseph Feb 25 at 19:05
• How does it matter? Write $N=2\beta$ and then prove that $\beta$ is a fixed message. In short, yes, I just played with it. I didn't call it "$M$" for "message" because I knew that was going to work ahead of time. – Randall Feb 25 at 19:05