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.

$$f(x) = {(x^2+5)}\bmod{9}$$ $${(x^2 + 5)} \bmod {9} = (x^2 + 5)\bmod 9$$ $$(x^2 + 5) = (x^2 + 5)$$ $$x^2 = x^2$$ $$x = x$$

Is this the correct way to do this?

I have no idea how to manipulate the terms.

share|improve this question
add comment

2 Answers 2

up vote 2 down vote accepted

The function is not one to one. To show this, you need to show that there exist $a$ and $b$ such that $a\not\equiv b\pmod{9}$ but $a^2+5\equiv b^2+5\pmod{9}$. It should not take long to find such a pair $(a,b)$: there are several.

Remark: You can operate partly by analogy. The reason the function $x^2+5$ is not one to one in this setting is related to the reason $x^2+5$ is not one to one on the reals.

share|improve this answer
    
how do we manipulate x mod b = x mod b, so we end up with x=x? –  Gladstone Asder Oct 28 '12 at 21:43
    
@amWhy: I don't mind, but the what I had typed was a $4$ instead of a dollar sign (sticky shift key), so I had to edit to remove the $4$. –  André Nicolas Oct 28 '12 at 21:44
    
what do you mean by operate partly by analogy? –  Gladstone Asder Oct 28 '12 at 21:50
    
@GladstoneAsder: The problem has nothing to do with manipulating until we get to $x=x$. –  André Nicolas Oct 28 '12 at 21:51
    
On the reals, the function $f(x)=x^2+5$ is not one to one, because for example $f(-17)=f(17)$. You will find that modulo $9$, $a^2+5\equiv b^2+5$ when $a=1$ and $b=9-1=8$. We also will have same kind of result with $a=2$ and $b=7$. Also with $a=0$ and $b=3$. Also several others. So very much not one to one. –  André Nicolas Oct 28 '12 at 21:55
add comment

Firstly, if you are doing what I think you are doing in the second line, you should really use two different variables. I think what you meant was $$x^2+5 \equiv y^2+5 \pmod{9}$$ $$x^2 \equiv y^2 \pmod{9}$$ $$x \equiv y \pmod{9}.$$

You are on the right track, in that you are allowed to subtract 5 from both sides, but you make a mistake in saying that because $x^2 \equiv y^2,$ $x$ must be congruent to $y$. That's not true mod 9, it's not true for reals, it's not even true for integers.

I think that more fundamentally you are asking what sorts of algebraic manipulations are valid in modular arithmetic:

  • You can always add or subtract a number from both sides of an equation without affecting the validity of the statement.

  • You can always replace one term of a sum or one term of a product with a congruent term. That is, you can replace $7 \cdot 5 \pmod{3}$ with $7 \cdot 2 \pmod{3}$ because 5 and 2 are the same thing. This rule only applies to sums and products, however. You can't do that with exponents, $x^5 \pmod{3}$ and $x^2 \pmod{3}$ are not the same.

  • And you can multiply both sides of the equation by a constant, only when that constant is relatively prime to the modulus. The caveat is very similar to the caveat with real numbers that you can't multiply by 0. The equation remains true, but it becomes trivial. For example, $2 \equiv 5 \pmod{6}$ is not true at all, but multiplying both sides by 2 we get $2 \cdot 2 \equiv 2 \cdot 5 \pmod{6}$ which is true.

There are of course other legal manipulations, but these are the most basic.

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