# How do we show that this modular function is one-to-one?

$$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.

-

## 2 Answers

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.

-
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

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.

-