Learning number theory with Gauß/Congruent numbers

Definition and elementary theorems

Definition 1.1:

Let $n\in \mathbb {N}$ and $a,b\in \mathbb {Z}$. $a$ and $b$ are said to be congruent to each other modulo $n$ if and only if $n|(b-a)$. In this case, we write

$a\equiv b\mod n$.

Theorem 1.2:

Let $n\in \mathbb {N}$ and $a\in \mathbb {Z}$. Then the numbers congruent to $a$ modulo $n$ are exactly the numbers

$a+m\cdot n,m\in \mathbb {Z}$.

Proof:

First we note that $n|(a+m\cdot n-a)$ for each $m\in \mathbb {Z}$. Then let $n|(b-a)$, i. e. $b-a=m\cdot n$ for an $m\in \mathbb {Z}$. Then $b=a+m\cdot n$.$\Box$

Corollary 1.3:

The relation $a\equiv b\mod n$ is an equivalence relation.

Proof 1:

We prove the corollary from theorem 1.2.

Reflexivity: Setting $m=0$, we note that $a\equiv a\mod n$.

Symmetry: Let $a\equiv b\mod n$, i.e. $b=a+mn$. Then $a=b+(-m)n$, where $-m\in \mathbb {Z}$.

Transitivity: Let $a\equiv b\mod n$ and $b\equiv c\mod n$, i.e. $b=a+mn$ and $c=b+ln$. Then $c=a+(m+l)n$.$\Box$

Proof 2:

We prove the corollary directly.

Reflexivity: $n|(a-a)$.

Symmetry: $a\equiv b\mod n\Leftrightarrow n|(b-a)\Leftrightarrow n|(a-b)\Leftrightarrow b\equiv a\mod n$.

Transitivity: $n|(b-a)$ and $n|(c-b)$ implies $b-a=sn$, $c-b=tn$ for some $s,t\in \mathbb {Z}$. Hence, $c-a=c-b+b-a=(s+t)n$.$\Box$

Definition 1.4:

Let $a\in \mathbb {Z}$, $n\in \mathbb {N}$. Then the equivalence class of $a$ with respect to the equivalence relation from the last theorem is called congruency class or residue class of $a$ modulo $n$.

Theorem 1.5 (Euclid; division with remainder):

Let $a\in \mathbb {Z}$, $n\in \mathbb {N}$. Then there exist $s\in \mathbb {Z}$ and $r\in \mathbb {N}$ such that $r<n$ and

$a=sn+r$.

Proof:

Consider the set

$S:=\mathbb {N} _{0}\cap \{a+tn|t\in \mathbb {Z} \}$.

Since this set by definition is contained in $\mathbb {N}$, it has a least element. Call this element $r$. By definition, we obtain the existence of $t\in \mathbb {Z}$ such that

$a=(-t)n+r$.

We define $s=-t$. Assume $r>n-1$. Then $r-n\in S$, contradicting the minimality of $r$.$\Box$

We note at this point that rings $R$ for which the above theorem holds with $R$ instead of $\mathbb {Z}$ and $\mathbb {N}$ (and a couple of more modifications, see the Wikipedia article) are called Euclidean rings.

Theorem 1.6:

There are exactly $n$ different congruency classes modulo $n$, where $n\in \mathbb {N}$.

Proof 1:

We prove the theorem from division with remainder.

We claim that $0,\ldots ,n-1$ define pairwise different congruency classes. Indeed, assume that two of those elements defined the same congruency class, call them $k$ and $j$. Then $n|(j-k)$, and hence in particular $j-k=0$ or $j-k\geq n$. The latter is a contradiction since we may make $j$ as large as possible and $k$ as small as possible.

Let now $a\in \mathbb {Z}$. By division with remainder, we obtain $a=sn+r,s\in \mathbb {Z} ,0\leq r\leq n-1$. Then $a\equiv r\mod n$, where $r$ is in the range $0,\ldots ,n-1$.

In summary, we obtain that each element $0,\ldots ,n-1$ represents a distinct congruency class, and further that each other number is contained in one of the congruency classes represented by these elements. Since they are $n$ many, the theorem follows.$\Box$

Proof 2:

We prove the theorem from Corollary 1.7 (this is not nonsensical because we give two proofs of this corollary which are not based upon this lemma).

First of all, we note that $0,\ldots ,n-1$ define pairwise different congruency classes, since if $b\in \{0,\ldots ,n-1\}$, by corollary 1.7 there exists exactly one number among $0,\ldots ,n-1$ congruent to $b$ ($b$ itself).

Then we note that each congruence class is represented by at least one $b\in \mathbb {Z}$, which in turn by corollary 1.7 is congruent to one of the elements $0,\ldots ,n-1$. Hence, each congruence class is represented by an element in $\{0,\ldots ,n-1\}$. Since these are exactly $n$ different elements, the theorem follows.

Corollary 1.7:

Let $n\in \mathbb {N}$, $a\in \mathbb {Z}$ and let $n$ successive integers $a,a+1,\ldots ,a+n-1$ be given. If $b\in \mathbb {Z}$ is any other integer, then exactly one of the integers $a,a+1,\ldots ,a+n-1$ is congruent to $b$ modulo $n$.

Proof 1:

We prove the corollary using theorem 1.2.

Indeed, by theorem 1.2 the integers congruent to $b$ modulo $n$ are given exactly by $b+m\cdot n,m\in \mathbb {Z}$. Assume none of those integers were contained within $\{a,a+1,\ldots ,a+n-1\}$. Define $m_{0}$ to be the largest integer such that $b+m_{0}n<a$ and $m_{1}$ to be the smallest integer such that $a+n-1<m_{1}$. By assumption $m_{1}=m_{0}+1$, since otherwise $m'=m_{0}+1$ would be larger than the largest integer $m_{0}$ such that $b+m_{0}n<a$ and smaller than the smallest integer $m_{1}$ such that $a+n-1<m_{1}$ and hence $a\leq b+m'n\leq a+n-1$ contrary to our assumption. But the difference between $b+m_{0}n$ and $b+m_{1}n=b+(m_{0}+1)n$ is exactly $n$, and in particular there are $n-1$ numbers enclosed between the two. This contradicts the assumption that the numbers $\{a,a+1,\ldots ,a+n-1\}$ are enclosed within the two; those are $n$ different numbers.

Assume two of the integers $\{a,a+1,\ldots ,a+n-1\}$ were congruent to $b$ modulo $n$. Call them $a+j$ and $a+l$. Then $a+j=b+sn$, $a+l=b+tn$ for some $s,t\in \mathbb {Z}$ by theorem 1.2. Hence, $j-l=(s-t)n$. In particular, the difference between $l$ and $j$ is either zero or greater or equal to $n$ in contradiction to the fact that the difference between any to numbers within $\{a,a+1,\ldots ,a+n-1\}$ is less or equal to $n-1$ (for, we may maximise the difference by moving the lower element to $a$ and the higher element to $a+n-1$).$\Box$

Proof 2:

We prove the corollary using theorem 1.2 and fractions.

If ${\frac {a-b}{n}}$ is an integer, then $a\equiv b\mod n$. Otherwise, ${\frac {a-b}{n}}$ is a fraction. Let $k$ be the next larger integer. Then

$a=b+{\frac {a-b}{n}}\cdot n<b+kn<b+{\frac {a-b+n}{n}}\cdot n=a+n$

and hence $b+k\cdot n$ is contained within $\{a,a+1,\ldots ,a+n-1\}$. Since furthermore for all $l\in \{0,\ldots ,n-1\}$

$k-1<{\frac {a-b}{n}}\leq {\frac {a+l-b}{n}}<{\frac {a+n-b}{n}}<k+1$,

only one of the fractions ${\frac {a+l-b}{n}}$ can be an integer, which is equivalent to $n|(a+l-b)$.$\Box$

Proof 3:

We prove the corollary from the notion of congruence classes and lemma 1.6.

Indeed, in complete analogy to lemma 1.6, we prove that $a,\ldots ,a+n-1$ represent pairwise distinct congruence classes. Since there are exactly $n$ many of them, the elements $a,\ldots ,a+n-1$ indeed represent all of the congruency classes. Since the equivalence classes of any equivalence relation form a partition, we conclude that each $b\in \mathbb {Z}$ is congruent to one of $a,\ldots ,a+n-1$.$\Box$

Residues

Definition 1.7:

Let $a\in \mathbb {Z}$ and $n\in \mathbb {N}$. $b\in \mathbb {Z}$ is called a residue of $a$ modulo $n$ if and only if $a\equiv b\mod n$.

From theorem 1.2 now directly follows that the residues modulo $n$ of $a\in \mathbb {Z}$ are exactly the numbers

$a+mn,m\in \mathbb {Z}$.

Lemma 1.8

Let $a\in \mathbb {Z}$ and $n\in \mathbb {N}$. Then $a$ has exactly one residue within $\{-(n-1),\ldots ,-1,0\}$ and exactly one residue within $\{0,1,\ldots ,n-1\}$. They coincide if and only if $n|a$.

Proof:

This follows from corollary 1.6 with $a=-(n-1)$ or $a=0$ respectively.$\Box$

Definition 1.9:

The two residues from lemma 1.8 are called negative least residue and positive least residue respectively.

Theorem 1.10:

Let $a\in \mathbb {Z}$, $n\in \mathbb {N}$, $l\in \{-(n-1),\ldots ,0\}$ be the negative least residue and $j\in \{0,\ldots ,n-1\}$ be the positive least residue. Then one of four cases occurs:

1. $|l|=|j|=n/2$
2. $|l|>n/2>|j|$
3. $|l|<n/2<|j|$
4. $|l|=|j|=0$

Proof:

We have $n|(a-j)$ and hence $n|(a+n-j)$, i.e. $n|(a-(j-n))$. We separate four cases:

1. $|j|=0$. Then since $j=|j|$, zero is the positive least residue and the negative least residue at once.

Theorem and definition 1.11:

Let $a\in \mathbb {Z}$ and $n\in \mathbb {N}$. There exists exactly one residue in the range ${\displaystyle }$

Divisibility criteria

Theorem 1.?:

Let $a\in \mathbb {Z}$ be given by the decimal expansion $a_{n}\cdots a_{1}a_{0}$, i. e.

$a=\sum _{j=0}^{n}a_{j}10^{j}$.

Then $a$ is divisible by three or nine if and only if $\sum _{j=0}^{n}a_{j}$ is.

Proof:

Since $10\equiv 1\mod 9$ (and hence $10\equiv 1\mod 3$), we have

$\sum _{j=0}^{n}a_{j}10^{j}\equiv \sum _{j=0}^{n}a_{j}\mod k$, $k\in \{3,9\}$.$\Box$

Exercises

• Exercise 1.?.1: