1
$\begingroup$

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.

  • 0
    Your function is 1-1 **on the integers mod $b$** if $b$ is odd, but not if $b$ is even.2012-10-29

2 Answers 2

1

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.

  • 0
    If it were $3x+3$, or $3x+17$, it would be $b$ not divisible by $3$.2012-10-29
0

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$

  • 0
    @Mathilda See the [Wikipedia page](http://en.wikipedia.org/wiki/Bézout's_identity) on the Bezout identity for the GCD.2012-10-29