Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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
add comment

2 Answers

up vote 1 down vote accepted

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.

share|improve this answer
    
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
show 2 more comments

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$

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.