Justification for solving modular congruencies

Question

This might seem like a stupid question (and I think it is), but I have been unable to gain intuition on this, or a solid proof. So far while studying number theory, I have seen the general solution for solving modular congruencies like:

$$x^2 \equiv 3 \mod{5}$$

Or, $$5x \equiv 11 \mod{19}$$

Solved by checking all the values of $x$ from $\{0, 1, ....., m-1\}$. If no solution appears in that set, then the modular congruency has no solution, else it does.

Why is this necessarily true? I have a slight intuition that for any $x$ where $x \geq m$, the mod cycle just wraps around to some number $x_0 < m$, but I don't feel this is solid justification. I guess, extended, is it true that:

$$f(x) \equiv r \mod{m}$$

Only has a solution if where $x =\{0, 1, ..., m-1\}$ has solution?

Answer 1

Use the binomial theorem: if you replace one of those things, $r\in\{0,1,\ldots, m-1\}$ by $r+km$ then how does this affect a polynomial? Well monomials go like this

$$(r+km)^j = \sum_{n=0}^j {j\choose n} r^n(km)^{j-n}$$

so that since any multiple of $m$ is just $0$ mod $m$, we see that $(r+km)^j\equiv r^j\mod m$. Similarly for entire polynomials as with $p(x) = \displaystyle\sum_{n=0}^Na_nx^n$ then

$$p(r+km)=\sum_{n=0}^N a_n(r+km)^n\equiv \sum_{n=0}^N a_nr^n\equiv p(r)\mod m$$

so really all you have to do is check that set, since congruences are equivalence relations.

Answer 2

For any $z \in \mathbb Z $, for a given modulo $n $, there are unique integers $k, x $ so that $z=kn + x; 0\le x < n $.

In other words $z/n = k + x/n $ for a unique quotient $k $ and unique remainder $x $. I hope this clear and acceptable.

Claim: $M*z \equiv m \mod n $ if and only if $M*x \equiv m \mod n $.

Because of this claim, we only have to check $x=0...n-1$ because if it's true for any $z=kn+x $ it is true for $x $ and vice versa.

So why is the claim true?

$M*z\equiv m \mod n \iff $

$M*z - m = K*n $ for some $K, \iff $

$M*(kn+x)-m=K*n \iff $

$M*x - m=K*n-Mkn \iff $

$M*x-m = (K-Mk)*n $ for some $(K-Mk), \iff $

$M*x \equiv m \mod n $.

So that should explain why if $5x \equiv 7 \mod 18$ we only check 0...17. It is true for $x=5$ if and only if it is true for all $z=18*k + 5$

$x^p \equiv m \mod n $ is very similar. $(x + nk)^p = x^p + p*(nk)*x^{p-1} +......+{p \choose i}*(nk)^i*x^{p-i}+....+(nk)^p =x^p + Kkn$ where $K=p*x^{p-1}+..... +{p \choose i}*(nk)^{i-1}*x^{p-i}+....+(nk)^{p-1} $.

So $x^p\equiv x^p + Kkn = (x+nk)^p \mod n $.

Answer 3

If $x$ is any integer, we can divide it by $m$ to get $x=qm+r$ with $0\leq r <m.$ So if $f$ is a polynomial and $f(x) \equiv 0 \pmod{m}$, then $f(x) \equiv f(qm+r) \equiv f(0+r) \equiv f(r) \pmod{m}.$ So if there's a solution, there must be a solution between $0$ and $m-1.$