Learning number theory with Gauß/Congruent numbers

Definition and elementary theorems 0 100% #FFFFFF Definition 1.1: Let and . and are said to be congruent to each other modulo if and only if . In this case, we write . Modular arithmetic 0 100% #FFFFFF 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 . 0 100% #FFFFFF 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, . 0 100% #FFFFFF 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 . 0 100% #FFFFFF Theorem 1.5 (Euclid; division with remainder): Let , . Then there exist and such that and . Euclidean division 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. Euclidean ring 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. 0 100% #FFFFFF 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 0 100% #FFFFFF 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. 0 100% #FFFFFF Definition 1.9: The two residues from lemma 1.8 are called negative least residue and positive least residue respectively. 0 100% #FFFFFF 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: . Then since , zero is the positive least residue and the negative least residue at once. 0 100% #FFFFFF Theorem and definition 1.11: Let and . There exists exactly one residue in the range The rings of residue classes Divisibility criteria 0 100% #FFFFFF 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 Exercise 1.?.1: