# Why $gcd(\alpha,26)\neq 1$ means that $ax\equiv y \pmod{26}$ is not injective?

Let's consider the equivalence: $$ax\equiv y \pmod{26}$$

If $$gcd(\alpha,26)\equiv 1$$ I can multiply each member by $$a^{-1}$$ and i can obtain $$x$$ in function of $$y$$.

If $$gcd(\alpha,26)\neq 1$$ i can't find the modular inverse, however what assures us that the function is not injective in this situation ?

• Hint $\ z\not\equiv 0,\ az \equiv 0\,\Rightarrow\, a(x+z)\equiv y\equiv az$ so there are at least two solutions $\,x+z,\ x\$ See here for more. May 6, 2019 at 17:12

If $$\ 1< c\mid a,m\,$$ then $$\bmod m\!:\ a(\color{#c00}{m/c}) = (a/c)m\equiv 0\,$$ so $$\,ax\equiv 0\,$$ for both $$\,0\not\equiv \color{#c00}{m/c}$$

$$\ \$$ e.g. $$\,\ 2\mid 6,26\$$ thus $$\bmod 26\!:\ 6(\color{#c00}{13})\equiv 0\equiv 6(0)\,$$ so $$\,f(\color{#c00}{13})\equiv f(0)\,$$ for $$\,f(x) = 6x$$

Alternatively see $$\,(3)\Rightarrow(4)\Rightarrow(1)\,$$ below (the contrapositive of your claim)

Theorem $$\$$ The following are equivalent for integers $$\rm\:a, m.$$

$$(1)\rm\ \ \ gcd(a,m) = 1$$
$$(2)\rm\ \ \ a\:$$ is invertible $$\rm\ \ \ \ \: (mod\ m)$$
$$(3)\rm\ \ \ x\,\mapsto\, ax\:$$ is $$\:1$$-$$1\:$$ $$\rm\,(mod\ m)$$
$$(4)\rm\ \ \ x\,\mapsto\, ax\:$$ is onto $$\rm\,(mod\ m)$$

Proof $$\ (1\Rightarrow 2)\$$ By Bezout $$\rm\, gcd(a,m)\! =\! 1\Rightarrow ja\!+\!km =\! 1\,$$ for $$\rm\,j,k\in\Bbb Z\,$$ $$\rm\Rightarrow ja\equiv 1\!\pmod{\! m}$$
$$(2\Rightarrow 3)\ \ \ \rm ax \equiv ay\,\Rightarrow\,x\equiv y\,$$ by scaling by $$\rm\,a^{-1}$$
$$(3\Rightarrow 4)\ \$$ Every $$1$$-$$1$$ function on a finite set is onto (pigeonhole).
$$(4\Rightarrow 1)\ \ \ \rm x\to ax\,$$ onto $$\,\Rightarrow\rm \exists\,j\!:\, aj\equiv 1\,$$ $$\rm\Rightarrow\exists\,j,k\!:\ aj\!+\!mk = 1$$ $$\,\Rightarrow\,\rm\gcd(a,m)\!=\!1$$

See here for a conceptual proof of said Bezout identity for the gcd.

• What i don't understand is why gcd != 1 imply the non-injectivity May 6, 2019 at 17:16
• @AleQuercia That is by $(1)\iff (3)$ above. specifically the contrapositive of $(3)\Rightarrow(4)\Rightarrow (1)\ \$ May 6, 2019 at 17:17
• @AleQuercia I added another direct proof based on the hint in my comment on your question. May 6, 2019 at 17:36
• Thanks so much :) May 6, 2019 at 18:50
• @AleQuercia You're welcome. If anything remains unclear let me know and I'll be happy to elaborate. May 6, 2019 at 18:52