1

It is said that for the affine cipher to be injective the affine function $e(X)=ax+b(mod26)$ , just taking 26 for this case, the $GCD(a,26)=1$. Now, I understand why is this the case, but, what I don't understand is the way that it is proven in my book. This is how the proof is done:

First, suppose that GCD(a,26)=1, then for some $x_1$ and $x_2$: $$ ax_1\equiv ax_2(mod26)$$ $$ \implies a(x_1-x_2) \equiv 0(mod26) $$ $$ \implies 26|a(x_1-x_2)$$ $$\implies 26|x_1-x_2 $$ $$x_1 \equiv x_2(mod26) $$

The thing I don't understand is $ax_1 \equiv ax_2(mod26)$, because, this statement implies that: $$ax_1 \equiv ax_2(mod26)$$ $$ax_1=26q+ax_2$$ and I don't understand why should the remainder be a multiple of $a$,

  • what if the remainder is not a multiple of a? Can't the GCD(a,26)=1 without the remainder being a multiple of a?
  • I'm even confused in the above steps because, from step number 4, we can see that GCD(a,26)=26.
mathmaniage
  • 596
  • Proving that the cipher is injective means proving that whenever $x_1$ and $x_2$ get mapped to the same letter, then $x_1 = x_2$. Having $x_1$ and $x_2$ get mapped to the same letter means $ax_1 + b \equiv ax_2 +b \pmod{26}$, from which the first congruence follows. (If for some $x_1$ and $x_2$ we didn't have this congruence, then that $x_1$ and $x_2$ got mapped to different letters, so there'd be nothing to show.) – Gregory J. Puleo Feb 21 '19 at 04:27
  • @GregoryJ.Puleo, but $ax_1 \equiv ax_2(mod26)$ doesn't this mean the value of b must be $ax_1$? – mathmaniage Feb 21 '19 at 14:09
  • Why would that follow? The $b$ cancels from both sides of the congruence $ax_1 + b \equiv ax_2 + b$. – Gregory J. Puleo Feb 21 '19 at 16:24
  • @GregoryJ.Puleo , I mean in general $a \equiv b(mod26)$ for example means that when 26 divides a then the remainder MUST be b, and in our case, b is $ax_1$ – mathmaniage Feb 22 '19 at 14:06

0 Answers0