Arithmétique et congruences
Definition and Notations of Congruence
Definition of Congruence Modulo :
- Let , , and be integers ().
- is congruent to modulo when is a multiple of (i.e., there exists an integer such that ).
Notations:
- To express that is congruent to modulo , several notations exist:
- Historical notation reference: In Disquisitiones arithmeticae, Carl Friedrich Gauss wrote:
- "Numerorum congruentiam hoc signo, , in posterum denotabimus, modulum vbi opus erit in clausulis adiungentes, , "
- The notation is the standard notation adopted for this course.
Special Cases and Initial Exercises:
- Exercice 1: Link between and when :
- means is a multiple of .
- Since the only multiple of is , it follows that . Thus, and must be equal numbers.
- Exercice 2: Link between and when :
- means is a multiple of .
- Since every integer is a multiple of , this relation holds for any arbitrary integers and .
- Exercice 4: Determining if in specific cases:
- Case 1: , , :
- . Since is a multiple of , is True.
- Case 2: , , :
- . Since is a multiple of , is True.
- Case 3: , , :
- . Since is not a multiple of , is False ().
Fundamental Properties of Congruence
Theorem (Equivalence Relation Properties):
- Let , , , and be integers.
- Reflexivity: .
- Symmetry: If , then .
- Transitivity: If and , then .
Remarks and Proofs:
- The symmetry property implies that it is indifferent to state that is congruent to or that is congruent to , modulo . For simplification, the terminology " and are congruent modulo " is used.
- For any natural number , the congruence relation modulo defines an equivalence relation on .
- Exercice 3 (Proof of the Equivalence Relation Theorem):
- Proof of Reflexivity: For any integer , . Thus, .
- Proof of Symmetry: If , then for some . Therefore, , where , which proves .
- Proof of Transitivity: If and , then there exist integers such that and . Summing these equations yields . Since , .
Euclidean Division and Congruence
Scope Restriction Context:
- To stay within the final year high school (terminale) curriculum regarding Euclidean division, the modulus is restricted to non-zero natural numbers ().
- This does not represent a real limitation because, setting aside , numbers congruent modulo are also congruent modulo , and vice versa.
Theorem (Congruence to the Remainder):
- Let . Every relative integer is congruent modulo to the remainder of its Euclidean division by
- Proof:
- Let be the quotient and be the remainder of the Euclidean division of by .
- By definition of Euclidean division, with .
- Rearranging the equation yields , which directly implies .
Theorem (Equality of Remainders):
- Let and be relative integers, and n \in \mathbb{N}^*$.\n - a = b \; (n)abn are identical.\n - **Proof**:\n - Let rr'qq'abn respectively.\n - a = b \; (n) \iff \exists k \in \mathbb{Z}, b - a = kn\n - Substituting a = nq + rb = nq' + r' gives:\n \exists k \in \mathbb{Z}, (nq' + r') - (nq + r) = kn \iff \exists k \in \mathbb{Z}, n(q' - q) + (r' - r) = kn \iff \exists k' \in \mathbb{Z}, r' - r = k'n\n - If a = b \; (n)0 \le r < n0 \le r' < n-n < r' - r < n.\n - The only multiple of n]-n, n[0.\n - Therefore, r' - r = 0 \implies r' = r.\n - Conversely, if r' = rb - a = n(q' - q)a = b \; (n).\n\n# Modular Arithmetic Operations and Algebraic Compatibility\n\n- **Theorem (Compatibility with Addition and Multiplication)**:\n - The relation of congruence is compatible with addition and multiplication.\n - Let nabcda = b \; (n)c = d \; (n), then:\n - a + c = b + d \; (n)\n - ac = bd \; (n)\n - **Proof**:\n - There exist integers kk'b - a = knd - c = k'n.\n - For addition:\n (b + d) - (a + c) = (b - a) + (d - c) = kn + k'n = (k + k')nk + k' \in \mathbb{Z}a + c = b + d \; (n).\n - For multiplication:\n bd - ac = (a + kn)(c + k'n) - ac = ac + ak'n + knc + kk'n^2 - ac = (ak' + kc + kk'n)nak' + kc + kk'n \in \mathbb{Z}ac = bd \; (n).\n\n- **Exercice 7 (Scalar Multiplication and Powers)**:\n - Under the hypotheses of the compatibility theorem, for any relative integer s \in \mathbb{Z}p \in \mathbb{N}:\n - sa = sb \; (n)\n - a^p = b^p \; (n)\n\n- **Exercice 8 (Divisibility Applications)**:\n - Show that for any relative integer n3 \mid n(n + 2)(n + 4).\n - *Proof using modular cases*:\n - Any integer n3012$.
- If , then .
- If , then , so .
- If , then , so .
- In all cases, , meaning .
- Related algebraic identity: Note that represents the product of three consecutive integers, which is always divisible by as one factor is necessarily a multiple of .
Solving Congruence Equations and Tabular Methods
- Exercice 6 (Table Modulo 5 and Equation Solving):
- 1. Complete table modulo containing the remainders of the Euclidean division by :
- For :
- For :
- For :
- For :
- For :
- 2. Solution in of the equation :
- Inspecting the table reveals that if and only if .
- The solutions in are all integers of the form , where .
- 3. Solution in of the equation :
- Testing each remainder class modulo :
- For :
- For :
- For :
- For :
- For :
- The solutions modulo are and .
- The full solution set in is .
Applications: Casting Out Nines and Divisibility Criteria
La Preuve par 9 (Casting Out Nines):
- Historical context: Before calculators, schoolchildren learning multiplication algorithms practiced on large calculations such as . To verify accuracy, they performed a check known as "la preuve par 9".
- Demonstration example: Verification of :
- Add digits of ; whenever total reaches , reset to : . is replaced by
- Perform same operation for : . is replaced by
- Multiply replaced values: . The expected product check value is
- Add digits of calculated result : . The result check value is
- Since both check values match (), the calculated product is validated.
- Exercice 9:
- 1. Proof that any natural number is congruent modulo 9 to the sum of its digits:
- Let be a natural number written in decimal notation as , with .
- Since , it follows from power compatibility that for all .
- Thus, .
- 2. Mechanism explanation: "La preuve par 9" verifies the congruence modulo of the operation. Since , it checks whether the necessary modular condition holds.
- 3. Guarantee of correctness: No. Passing "la preuve par 9" does not guarantee that the result is correct, because errors that differ by multiples of (such as digit transpositions or extra zeros) will produce identical remainders modulo
Divisibility Criteria:
- Exercice 10 (Divisibility by 5):
- Let be a natural number with decimal expansion , meaning , where .
- Since , for all , .
- Therefore, .
- Criterion: A natural number is divisible by if and only if its unit digit is divisible by (i.e., or ).
- Exercice 11 (Divisibility by 9, 3, and 6):
- 1. Divisibility by 9: Since , if and only if . A natural number is divisible by if and only if the sum of its digits is a multiple of
- 2. Divisibility by 3: Since , by similar reasoning . An integer is divisible by if and only if the sum of its digits is a multiple of
- 3. Divisibility by 6: An integer is divisible by if and only if it is divisible by both and . Thus, it must be even (ending in ) and the sum of its digits must be a multiple of
- Exercice 12 (Divisibility by 11):
- For any natural number :
- Criterion: An integer is congruent modulo to the alternating sum of its digits: . A number is divisible by if and only if this alternating sum of its digits is a multiple of
Python Implementations and Vigenère Cipher
- Exercice 5 (Python Congruence Function):
- Implementation of
congrus(a, b, n)to test congruence:
- Implementation of
def congrus(a, b, n):
"""a, b et n entiers, n > 0.
Retourne True si a et b sont congrus
modulo n, False sinon."""
return (a - b) % n == 0
Test execution:
Input:
congrus(-5, -9, 3)Calculation: . Since , output is
False.Exercice 13 (Vigenère Cipher Implementation):
Text formatting helper function:
def formater_texte(texte):
"""Formate la chaine de caractères texte en une chaine
de caractères sans accent et en majuscule.
Les caractères produits sont des caractères ASCII."""
import unicodedata
texte = texte.upper()
return (
unicodedata.normalize("NFKD", texte)
.encode("ascii", "ignore")
.decode("ascii")
)
- Text formatting test:
- Input:
formater_texte('Il fait très beau Comment ça va ?') - Output:
'IL FAIT TRES BEAU COMMENT CA VA ?'
- Input:
- Character encoding reference functions:
ord('A')outputs65,chr(65)outputs'A'ord('B')outputs66,chr(66)outputs'B'
- Vigenère encryption/decryption algorithm function:
def vigenere(texte, clef, decode=0):
"""Retourne la chaine de caractère résultat du chiffrement de
Vigenère de la chaine de caractères texte à l'aide de la clef
clef (chaine de caractères).
Pour décoder: decode = 1."""
texte = formater_texte(texte)
clef = formater_texte(clef)
resultat = []
clef_index = 0
len_clef = len(clef)
for char in texte:
if "A" <= char <= "Z":
shift = ord(clef[clef_index % len_clef]) - ord("A")
if decode == 1:
shift = -shift
code_base = ord("A")
nouveau_char = chr(
(ord(char) - code_base + shift) % 26 + code_base
)
resultat.append(nouveau_char)
clef_index += 1
else:
resultat.append(char)
return "".join(resultat)
- Execution tests:
- Encryption:
- Call:
vigenere('Il fait très beau ! Comment ça va ?', 'ab') - Output:
'IM FBIU TSET BFAV! CPMNEOT DA WA ?'
- Call:
- Decryption:
- Call:
vigenere('IM FBIU TSET BFAV! CPMNEOT DA WA ?', 'ab', 1) - Output:
'IL FAIT TRES BEAU! COMMENT CA VA ?'
- Call:
- Encryption:
Historical Notes and Institutional Context
- Historical References in Modular Arithmetic:
- Carl Friedrich Gauss: Introduced the standard symbol and modular syntax in Disquisitiones arithmeticae.
- Sophie Germain: At the end of the 18th century, Sophie Germain had to assume a male pseudonym to correspond with professors at the École Polytechnique, as the institution was closed to women at the time.
- Institutional Legacy:
- Today, the Mathematics and Computer Science departments (UFR de mathématiques et d'informatique) of the Université de Paris are housed in the Sophie Germain building, located on the Grands Moulins campus in the 13th arrondissement of Paris.
- Course Metadata & License:
- Material authored by Thierry Cuesta, Lycée Martin Luther King.
- Licensed under Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License (CC BY-NC-SA 4.0).