Jump to content

Learning number theory with Gauß/Congruent numbers

From Wikibooks, open books for an open world

Definition and elementary theorems

[edit | edit source]

Definition 1.1:

Let and . and are said to be congruent to each other modulo if and only if . In this case, we write

.

Theorem 1.2:

Let and . Then the numbers congruent to modulo are exactly the numbers

.

Proof:

First we note that for each . Then let , i. e. for an . Then .

Corollary 1.3:

The relation is an equivalence relation.

Proof 1:

We prove the corollary from theorem 1.2.

Reflexivity: Setting , we note that .

Symmetry: Let , i.e. . Then , where .

Transitivity: Let and , i.e. and . Then .

Proof 2:

We prove the corollary directly.

Reflexivity: .

Symmetry: .

Transitivity: and implies , for some . Hence, .

Definition 1.4:

Let , . Then the equivalence class of with respect to the equivalence relation from the last theorem is called congruency class or residue class of modulo .

Theorem 1.5 (Euclid; division with remainder):

Let , . Then there exist and such that and

.

Proof:

Consider the set

.

Since this set by definition is contained in , it has a least element. Call this element . By definition, we obtain the existence of such that

.

We define . Assume . Then , contradicting the minimality of .

We note at this point that rings for which the above theorem holds with instead of and (and a couple of more modifications, see the Wikipedia article) are called Euclidean rings.

Theorem 1.6:

There are exactly different congruency classes modulo , where .

Proof 1:

We prove the theorem from division with remainder.

We claim that define pairwise different congruency classes. Indeed, assume that two of those elements defined the same congruency class, call them and . Then , and hence in particular or . The latter is a contradiction since we may make as large as possible and as small as possible.

Let now . By division with remainder, we obtain . Then , where is in the range .

In summary, we obtain that each element 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 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 define pairwise different congruency classes, since if , by corollary 1.7 there exists exactly one number among congruent to ( itself).

Then we note that each congruence class is represented by at least one , which in turn by corollary 1.7 is congruent to one of the elements . Hence, each congruence class is represented by an element in . Since these are exactly different elements, the theorem follows.

Corollary 1.7:

Let , and let successive integers be given. If is any other integer, then exactly one of the integers is congruent to modulo .

Proof 1:

We prove the corollary using theorem 1.2.

Indeed, by theorem 1.2 the integers congruent to modulo are given exactly by . Assume none of those integers were contained within . Define to be the largest integer such that and to be the smallest integer such that . By assumption , since otherwise would be larger than the largest integer such that and smaller than the smallest integer such that and hence contrary to our assumption. But the difference between and is exactly , and in particular there are numbers enclosed between the two. This contradicts the assumption that the numbers are enclosed within the two; those are different numbers.

Assume two of the integers were congruent to modulo . Call them and . Then , for some by theorem 1.2. Hence, . In particular, the difference between and is either zero or greater or equal to in contradiction to the fact that the difference between any to numbers within is less or equal to (for, we may maximise the difference by moving the lower element to and the higher element to ).

Proof 2:

We prove the corollary using theorem 1.2 and fractions.

If is an integer, then . Otherwise, is a fraction. Let be the next larger integer. Then

and hence is contained within . Since furthermore for all

,

only one of the fractions can be an integer, which is equivalent to .

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 represent pairwise distinct congruence classes. Since there are exactly many of them, the elements indeed represent all of the congruency classes. Since the equivalence classes of any equivalence relation form a partition, we conclude that each is congruent to one of .

Residues

[edit | edit source]

Definition 1.7:

Let and . is called a residue of modulo if and only if .

From theorem 1.2 now directly follows that the residues modulo of are exactly the numbers

.

Lemma 1.8

Let and . Then has exactly one residue within and exactly one residue within . They coincide if and only if .

Proof:

This follows from corollary 1.6 with or respectively.

Definition 1.9:

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

Theorem 1.10:

Let , , be the negative least residue and be the positive least residue. Then one of four cases occurs:

Proof:

We have and hence , i.e. . We separate four cases:

  1. . Then since , zero is the positive least residue and the negative least residue at once.

Theorem and definition 1.11:

Let and . There exists exactly one residue in the range

The rings of residue classes

[edit | edit source]

Divisibility criteria

[edit | edit source]

Theorem 1.?:

Let be given by the decimal expansion , i. e.

.

Then is divisible by three or nine if and only if is.

Proof:

Since (and hence ), we have

, .

Exercises

[edit | edit source]
  • Exercise 1.?.1: