Learning number theory with Gauß/Congruent numbers

Definition and elementary theorems

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

Proof 1:

We prove the corollary from theorem 1.2.

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

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

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

Proof 2:

We prove the corollary directly.

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

Symmetry: $a\equiv bmodn\iff n|(b-a)\iff n|(a-b)\iff b\equiv amodn$.

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

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

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. Template:Wikipedia

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,\dots ,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\ge 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\le r\le n-1$. Then $a\equiv rmodn$, where $r$ is in the range $0,\dots ,n-1$.

In summary, we obtain that each element $0,\dots ,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.$◻$

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,\dots ,n-1$ define pairwise different congruency classes, since if $b\in \{0,\dots ,n-1\}$, by corollary 1.7 there exists exactly one number among $0,\dots ,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,\dots ,n-1$. Hence, each congruence class is represented by an element in $\{0,\dots ,n-1\}$. Since these are exactly $n$ different elements, the theorem follows.

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,\dots ,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^{\prime }=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\le b+m^{\prime }n\le 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,\dots ,a+n-1\}$ are enclosed within the two; those are $n$ different numbers.

Assume two of the integers $\{a,a+1,\dots ,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,\dots ,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$).$◻$

Proof 2:

We prove the corollary using theorem 1.2 and fractions.

If $\frac{a-b}{n}$ is an integer, then $a\equiv bmodn$. 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,\dots ,a+n-1\}$. Since furthermore for all $l\in \{0,\dots ,n-1\}$

$k-1<\frac{a-b}{n}\le \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)$.$◻$

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,\dots ,a+n-1$ represent pairwise distinct congruence classes. Since there are exactly $n$ many of them, the elements $a,\dots ,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,\dots ,a+n-1$.$◻$

Residues

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),\dots ,-1,0\}$ and exactly one residue within $\{0,1,\dots ,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.$◻$

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.

Divisibility criteria

Proof:

Since $10\equiv 1mod9$ (and hence $10\equiv 1mod3$), we have

$\sum _{j=0}^n{a}_{j}10^j\equiv \sum _{j=0}^n{a}_{j}modk$, $k\in \{3,9\}$.$◻$

Exercises

• Exercise 1.?.1: