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

Question

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

Answer 1

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.

Answer 2

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.