# How do we simplify mod expressions?

I have a modulus function that looks like this $f(x) = 2x+3 \bmod b$, and i have to show that $x = y$ to prove that the function is $1-1.$

I know that mod functions can't be algebraically manipulated like regular function, so I was wondering if it was even possible or if I was just wasting my time scratching my head.

-
What's the domain? Knowing that is essential if we're to answer your question. – Cameron Buie Oct 29 '12 at 0:42
Your function is 1-1 on the integers mod $b$ if $b$ is odd, but not if $b$ is even. – Robert Israel Oct 29 '12 at 0:44

The number $b$ you are given must be odd.

We have $2x+3 \equiv 2y+3 \pmod {b}$ iff $(2x+3)-(2y+3)$ is divisible by $b$ iff $2(x-y)$ is divisible by $b$.

If $b$ is odd, this is true iff $x-y$ is divisible by $b$, that is, iff $x\equiv y \pmod{b}$.

Thus if $b$ is odd, our function is one to one. This need not be true if $x$ is even. For example. $(2)(1)+3 \equiv 2(5)+3\pmod {8}$ but $1\not\equiv 5\pmod{8}$.

Remark: Actually, what is remarkable is the degree to which mod expressions can be manipulated like regular functions.

-
i don't quite understand what was done here – hjggh Oct 29 '12 at 1:21
shouldn't it be (2x + 3) - (2y +3) is divisible by b? – hjggh Oct 29 '12 at 1:33
@MathildaPitt: Thanks. Fixed. – André Nicolas Oct 29 '12 at 1:37
would the answer be the same if the domain was (0,1,2,3...b-1)? – hjggh Oct 29 '12 at 1:42
If $b$ is odd, then the function is one to one if we use the domain you just mentioned, or equivalently if we work modulo $b$. – André Nicolas Oct 29 '12 at 2:14

It is much more insightful to consider the following generalization.

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

$(1)\rm\ \ \ gcd(c,m) = 1$
$(2)\rm\ \ \ c\:$ is invertible $\rm\,(mod\ m)$
$(3)\rm\ \ \ x\to cx+d\:$ is $\:1$-$1\:$ $\rm\,(mod\ m)$
$(4)\rm\ \ \ x\to cx+d\:$ is onto $\rm\,(mod\ m)$

Proof $\ \ (1\Rightarrow 2)\ \$ By Bezout, $\rm\: gcd(c,m) = 1\:\Rightarrow\: cd+km = 1\:$ for $\rm\:d,k\in\Bbb Z\:$ $\rm\Rightarrow\:cd\equiv 1\pmod m$
$(2\Rightarrow 3)\ \ \ \rm cx+d \equiv cy+d\:\Rightarrow\:c(x-y)\equiv 0\:\Rightarrow\:x-y\equiv 0\:$ by multiplying by $\rm\:c^{-1}$
$(3\Rightarrow 4)\ \$ Every $1$-$1$ function on a finite set is onto.
$(4\Rightarrow 1)\ \ \ \rm x\to cx\:$ is onto, so $\rm\:cd\equiv 1,\:$ some $\rm\,d,\:$ i.e. $\rm\: cd+km = 1,\:$ some $\rm\,k,\:$ so $\rm\:gcd(c,m)=1$

-
i am really confused, because i never heard about bezout – hjggh Oct 29 '12 at 1:49
@Mathilda See the Wikipedia page on the Bezout identity for the GCD. – Bill Dubuque Oct 29 '12 at 2:28