Let's consider the encoding function: $$y=ax \bmod 5$$ where $x$ is the number that corresponds to a certain letter in the alphabet. I'm trying to understand why for every number $n$, with $n>4$, I can find a number a such as $ax \equiv nx \bmod 5$.

First of all, I'm trying to understand why, given a certain $x$, if a ranges between $[0,\ldots,4]$ I cover all possible remainders (that is the remainders from $0$ to $4$). For example, if I take $x=3$, then:

$0=0*3 \rightarrow$ remainder is $0$

$3=1*3 \rightarrow$ remainder is $3$

$6=2*3 \rightarrow$ remainder is $1$

and so on...

But i don't know how to prove it... Can you help me?


1 Answer 1


As stated, your assertion is fals: if $x=5$ (or any multiple of $5$), then $ax\equiv 0\pmod 5$ regardless of what $a$ is.

But given $x$ not a multiple of $5$: if you want $ax\equiv r\pmod 5$ for some particular $r\in\{0,1,2,3,4\}$, then you can do so by choosing $a\equiv rx^{-1}\pmod 5$, where $x^{-1}$ is the modular inverse of $x$.

For a general modulus $q$ in place of $5$, this will be possiblie whenever $\gcd(r,q)=1$.

  • $\begingroup$ Why do we know at prior that, in this case, $x^{-1} \in \left \{ 0,1,2,3,4 \right \}$ ? $\endgroup$
    – AleWolf
    May 4, 2019 at 16:08

You must log in to answer this question.

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