1
$\begingroup$

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 ?

$\endgroup$
1
  • 3
    $\begingroup$ 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. $\endgroup$ May 6, 2019 at 17:12

1 Answer 1

1
$\begingroup$

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.

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .