1.4 Congruences

Let $m\in \mathbb{N}$. We say that integers $x$ and $y$ are congruent modulo $m$, and write $x\equiv y\mathrm{mod}m$ if $m$ divides $x-y$

Another way to think about this is that 2 numbers are congruent modulo $m$ if the leave the same remainder when divided by $m$. this is an equivalence relation on $\mathbb{Z}$, and so the integers can be partitioned into congruence classes $r+m\mathbb{Z}$, where $0\le r<m$. These congruence classes form the quotient ring $\mathbb{Z}/m\mathbb{Z}$.

Lemma 1.4.3 (Congruences respect addition and multiplication)

Let $m\in \mathbb{N}$. Let $a,b,\alpha ,\beta$ be integers such that
$a\equiv \alpha \mathrm{mod}m,b\equiv \beta \mathrm{mod}m$
Then
$a+b\equiv \alpha +\beta \mathrm{mod}m,ab\equiv \alpha \beta \mathrm{mod}m$
This, if $f(x,y)\in \mathbb{Z}[x,y]$, then
$f(a,b)\equiv f(\alpha ,\beta )\mathrm{mod}m$

Proof

todo

Lemma 1.4.4 (Cancellation with congruences)

Let $m\in \mathbb{N}$, and let $a,x,y\in \mathbb{N}$ with
$ax\equiv ay\mathrm{mod}m$
(a) If $a\mid m$ then
$x\equiv y\mathrm{mod}m/a$
(b) If $(a,m)=1$ then
$x\equiv y\mathrm{mod}m$

Proof

(a) We have $a(x-y)=cm$ for some $c\in \mathbb{Z}$, so $x-y=cm/a$, hence $x\equiv y\mathrm{mod}m/a$
(b) As $m$ divides $a(x-y)$ and $(a,m)=1$, the General Euclid Lemma tells us that $m$ divides $x-y$, so $x\equiv y\mathrm{mod}m$

Lemma 1.4.6

Squares are 0 or 1 modulo 4

Note

The proof can be simply derived from drawing a table

Lemma 1.4.8

Let $n$ be a positive integer of the form $n=4^{k}m$, where $k\ge 0$ and $m\equiv 7\mathrm{mod}8$. Then $n$ is not a sum of 3 squares.

Proof

By checking $\{0,1,...,7\}$, we find that squares are 0, 1 or 4 modulo 8. Thus, three squares cannot sum to 7 modulo 8, which solves the $k=0$ case.
We now induct on $k$. Let $k\ge 1$, and assume the result for smaller values of $k$. Suppose for a contradiction that
$x^2+y^2+z^2=4^{k}m$
for some $x,y,z\in \mathbb{Z}$. Then $x^2+y^2+z^2\equiv 0\mathrm{mod}4$. This is only possible for $x,y,z$ all being even, since $x^2$ = 0 mod 4 if $x$ is even and $i$ mod 4 if $x$ is odd. Therefore, the problem can be written as
$x=2u,y=2v,z=2w$
giving
$u^2+v^2+w^2=4^{k-1}m$
which contradicts our inductive hypothesis

The above proof is an example of infinite descent, where any triple $(x,y,z)$ with the properly of interest produces a smaller such triple.