Arithmétique et congruences

Definition and Notations of Congruence

  • Definition of Congruence Modulo nn:

    • Let aa, bb, and nn be integers (a,b,n∈Za, b, n \in \mathbb{Z}).
    • aa is congruent to bb modulo nn when b−ab - a is a multiple of nn (i.e., there exists an integer k∈Zk \in \mathbb{Z} such that b−a=knb - a = kn).
  • Notations:

    • To express that aa is congruent to bb modulo nn, several notations exist:
    • a≡b(modn)a \equiv b \pmod{n}
    • a=b(modn)a = b \pmod{n}
    • a=b  [n]a = b \; [n]
    • a=b  (n)a = b \; (n)
    • Historical notation reference: In Disquisitiones arithmeticae, Carl Friedrich Gauss wrote:
    • "Numerorum congruentiam hoc signo, ≡\equiv, in posterum denotabimus, modulum vbi opus erit in clausulis adiungentes, 16≡9(mod5)16 \equiv 9 \pmod{5}, −7≡15(mod11)-7 \equiv 15 \pmod{11}"
    • The notation a=b  (n)a = b \; (n) is the standard notation adopted for this course.
  • Special Cases and Initial Exercises:

    • Exercice 1: Link between aa and bb when a=b  (0)a = b \; (0):
    • a=b  (0)a = b \; (0) means b−ab - a is a multiple of 00.
    • Since the only multiple of 00 is 0×k=00 \times k = 0, it follows that b−a=0  ⟹  a=bb - a = 0 \implies a = b. Thus, aa and bb must be equal numbers.
    • Exercice 2: Link between aa and bb when a=b  (1)a = b \; (1):
    • a=b  (1)a = b \; (1) means b−ab - a is a multiple of 11.
    • Since every integer is a multiple of 11, this relation holds for any arbitrary integers aa and bb.
    • Exercice 4: Determining if a=b  (n)a = b \; (n) in specific cases:
    • Case 1: a=6a = 6, b=0b = 0, n=2n = 2:
      • b−a=0−6=−6=(−3)×2b - a = 0 - 6 = -6 = (-3) \times 2. Since −6-6 is a multiple of 22, 6=0  (2)6 = 0 \; (2) is True.
    • Case 2: a=−2a = -2, b=7b = 7, n=3n = 3:
      • b−a=7−(−2)=9=3×3b - a = 7 - (-2) = 9 = 3 \times 3. Since 99 is a multiple of 33, −2=7  (3)-2 = 7 \; (3) is True.
    • Case 3: a=4a = 4, b=−5b = -5, n=2n = 2:
      • b−a=−5−4=−9b - a = -5 - 4 = -9. Since −9-9 is not a multiple of 22, 4=−5  (2)4 = -5 \; (2) is False (4≠−5  (2)4 \neq -5 \; (2)).

Fundamental Properties of Congruence

  • Theorem (Equivalence Relation Properties):

    • Let aa, bb, cc, and nn be integers.
    • Reflexivity: a=a  (n)a = a \; (n).
    • Symmetry: If a=b  (n)a = b \; (n), then b=a  (n)b = a \; (n).
    • Transitivity: If a=b  (n)a = b \; (n) and b=c  (n)b = c \; (n), then a=c  (n)a = c \; (n).
  • Remarks and Proofs:

    • The symmetry property implies that it is indifferent to state that aa is congruent to bb or that bb is congruent to aa, modulo nn. For simplification, the terminology "aa and bb are congruent modulo nn" is used.
    • For any natural number nn, the congruence relation modulo nn defines an equivalence relation on Z\mathbb{Z}.
    • Exercice 3 (Proof of the Equivalence Relation Theorem):
    • Proof of Reflexivity: For any integer aa, a−a=0=0×na - a = 0 = 0 \times n. Thus, a=a  (n)a = a \; (n).
    • Proof of Symmetry: If a=b  (n)a = b \; (n), then b−a=knb - a = kn for some k∈Zk \in \mathbb{Z}. Therefore, a−b=(−k)na - b = (-k)n, where −k∈Z-k \in \mathbb{Z}, which proves b=a  (n)b = a \; (n).
    • Proof of Transitivity: If a=b  (n)a = b \; (n) and b=c  (n)b = c \; (n), then there exist integers k,k′∈Zk, k' \in \mathbb{Z} such that b−a=knb - a = kn and c−b=k′nc - b = k'n. Summing these equations yields (c−b)+(b−a)=k′n+kn  ⟹  c−a=(k+k′)n(c - b) + (b - a) = k'n + kn \implies c - a = (k + k')n. Since k+k′∈Zk + k' \in \mathbb{Z}, a=c  (n)a = c \; (n).

Euclidean Division and Congruence

  • Scope Restriction Context:

    • To stay within the final year high school (terminale) curriculum regarding Euclidean division, the modulus nn is restricted to non-zero natural numbers (n∈N∗n \in \mathbb{N}^*).
    • This does not represent a real limitation because, setting aside n=0n = 0, numbers congruent modulo −n-n are also congruent modulo nn, and vice versa.
  • Theorem (Congruence to the Remainder):

    • Let n∈N∗n \in \mathbb{N}^*. Every relative integer mm is congruent modulo nn to the remainder of its Euclidean division by nn
    • Proof:
    • Let qq be the quotient and rr be the remainder of the Euclidean division of mm by nn.
    • By definition of Euclidean division, m=nq+rm = nq + r with 0≤r<n0 \le r < n.
    • Rearranging the equation yields m−r=nqm - r = nq, which directly implies m=r  (n)m = r \; (n).
  • Theorem (Equality of Remainders):

    • Let aa and bb be relative integers, and n \in \mathbb{N}^*$.\n - a = b \; (n)ifandonlyiftherespectiveremaindersoftheEuclideandivisionsofif and only if the respective remainders of the Euclidean divisions ofaandandbbybyn are identical.\n - **Proof**:\n - Let randandr'betheremainders,andbe the remainders, andqandandq'bethequotientsoftheEuclideandivisionsofbe the quotients of the Euclidean divisions ofaandandbbybyn respectively.\n - a = b \; (n) \iff \exists k \in \mathbb{Z}, b - a = kn\n - Substituting a = nq + randandb = 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),since, since0 \le r < nandand0 \le r' < n,subtractingtheinequalitiesgives, subtracting the inequalities gives-n < r' - r < n.\n - The only multiple of nbelongingtotheopenintervalbelonging to the open interval]-n, n[isis0.\n - Therefore, r' - r = 0 \implies r' = r.\n - Conversely, if r' = r,then, thenb - a = n(q' - q),whichproves, which provesa = 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 nbeaninteger.Forallrelativeintegersbe an integer. For all relative integersa,,b,,c,and, andd,if, ifa = b \; (n)andandc = d \; (n), then:\n - a + c = b + d \; (n)\n - ac = bd \; (n)\n - **Proof**:\n - There exist integers kandandk'suchthatsuch thatb - a = knandandd - c = k'n.\n - For addition:\n      (b + d) - (a + c) = (b - a) + (d - c) = kn + k'n = (k + k')n.Since. Sincek + 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)n.Since. Sinceak' + 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}andanynaturalnumberand any natural numberp \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 n,,3 \mid n(n + 2)(n + 4).\n - *Proof using modular cases*:\n - Any integer niscongruentmodulois congruent modulo3toeitherto either0,,1,or, or2$.
    • If n=0  (3)n = 0 \; (3), then n(n+2)(n+4)=0×(2)×(4)=0  (3)n(n + 2)(n + 4) = 0 \times (2) \times (4) = 0 \; (3).
    • If n=1  (3)n = 1 \; (3), then n+2=1+2=3=0  (3)n + 2 = 1 + 2 = 3 = 0 \; (3), so n(n+2)(n+4)=1×0×5=0  (3)n(n + 2)(n + 4) = 1 \times 0 \times 5 = 0 \; (3).
    • If n=2  (3)n = 2 \; (3), then n+4=2+4=6=0  (3)n + 4 = 2 + 4 = 6 = 0 \; (3), so n(n+2)(n+4)=2×4×0=0  (3)n(n + 2)(n + 4) = 2 \times 4 \times 0 = 0 \; (3).
    • In all cases, n(n+2)(n+4)=0  (3)n(n + 2)(n + 4) = 0 \; (3), meaning 3∣n(n+2)(n+4)3 \mid n(n + 2)(n + 4).
    • Related algebraic identity: Note that n(n−1)(n+1)n(n - 1)(n + 1) represents the product of three consecutive integers, which is always divisible by 33 as one factor is necessarily a multiple of 33.

Solving Congruence Equations and Tabular Methods

  • Exercice 6 (Table Modulo 5 and Equation Solving):
    • 1. Complete table modulo 55 containing the remainders of the Euclidean division by 55:
    • For n=0n = 0: 2n=2(0)=0  (5)2n = 2(0) = 0 \; (5)
    • For n=1n = 1: 2n=2(1)=2  (5)2n = 2(1) = 2 \; (5)
    • For n=2n = 2: 2n=2(2)=4  (5)2n = 2(2) = 4 \; (5)
    • For n=3n = 3: 2n=2(3)=6=1  (5)2n = 2(3) = 6 = 1 \; (5)
    • For n=4n = 4: 2n=2(4)=8=3  (5)2n = 2(4) = 8 = 3 \; (5)
    • 2. Solution in Z\mathbb{Z} of the equation 2n=1  (5)2n = 1 \; (5):
    • Inspecting the table reveals that 2n=1  (5)2n = 1 \; (5) if and only if n=3  (5)n = 3 \; (5).
    • The solutions in Z\mathbb{Z} are all integers of the form n=5k+3n = 5k + 3, where k∈Zk \in \mathbb{Z}.
    • 3. Solution in Z\mathbb{Z} of the equation n2+3n=0  (5)n^2 + 3n = 0 \; (5):
    • Testing each remainder class modulo 55:
      • For n=0n = 0: 02+3(0)=0=0  (5)0^2 + 3(0) = 0 = 0 \; (5)
      • For n=1n = 1: 12+3(1)=4  (5)1^2 + 3(1) = 4 \; (5)
      • For n=2n = 2: 22+3(2)=4+6=10=0  (5)2^2 + 3(2) = 4 + 6 = 10 = 0 \; (5)
      • For n=3n = 3: 32+3(3)=9+9=18=3  (5)3^2 + 3(3) = 9 + 9 = 18 = 3 \; (5)
      • For n=4n = 4: 42+3(4)=16+12=28=3  (5)4^2 + 3(4) = 16 + 12 = 28 = 3 \; (5)
    • The solutions modulo 55 are n=0  (5)n = 0 \; (5) and n=2  (5)n = 2 \; (5).
    • The full solution set in Z\mathbb{Z} is {5k∣k∈Z}∪{5k+2∣k∈Z}\{5k \mid k \in \mathbb{Z}\} \cup \{5k + 2 \mid k \in \mathbb{Z}\}.

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 2732×5262732 \times 526. To verify accuracy, they performed a check known as "la preuve par 9".
    • Demonstration example: Verification of 2732×526=14370322732 \times 526 = 1437032:
    • Add digits of 27322732; whenever total reaches 99, reset to 00: 2+7=9  ⟹  0+3+2=52 + 7 = 9 \implies 0 + 3 + 2 = 5. 27322732 is replaced by 55
    • Perform same operation for 526526: 5+2+6=13=9+45 + 2 + 6 = 13 = 9 + 4. 526526 is replaced by 44
    • Multiply replaced values: 5×4=20=2×9+25 \times 4 = 20 = 2 \times 9 + 2. The expected product check value is 22
    • Add digits of calculated result 14370321437032: 1+4+3+7+0+3+2=20=2×9+21 + 4 + 3 + 7 + 0 + 3 + 2 = 20 = 2 \times 9 + 2. The result check value is 22
    • Since both check values match (2=22 = 2), the calculated product is validated.
    • Exercice 9:
    • 1. Proof that any natural number is congruent modulo 9 to the sum of its digits:
      • Let aa be a natural number written in decimal notation as a=∑k=0n10kaka = \sum_{k=0}^n 10^k a_k, with ak∈{0,…,9}a_k \in \{0, \dots, 9\}.
      • Since 10=1  (9)10 = 1 \; (9), it follows from power compatibility that 10k=1k=1  (9)10^k = 1^k = 1 \; (9) for all k∈Nk \in \mathbb{N}.
      • Thus, a=∑k=0n10kak=∑k=0n(1)ak=∑k=0nak  (9)a = \sum_{k=0}^n 10^k a_k = \sum_{k=0}^n (1) a_k = \sum_{k=0}^n a_k \; (9).
    • 2. Mechanism explanation: "La preuve par 9" verifies the congruence modulo 99 of the operation. Since A×B=C  ⟹  (A mod 9)×(B mod 9)=(C mod 9)A \times B = C \implies (A \bmod 9) \times (B \bmod 9) = (C \bmod 9), 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 99 (such as digit transpositions or extra zeros) will produce identical remainders modulo 99
  • Divisibility Criteria:

    • Exercice 10 (Divisibility by 5):
    • Let aa be a natural number with decimal expansion anan−1…a0a_n a_{n-1} \dots a_0, meaning a=∑k=0n10kaka = \sum_{k=0}^n 10^k a_k, where ak∈N∩[0,9]a_k \in \mathbb{N} \cap [0, 9].
    • Since 10=0  (5)10 = 0 \; (5), for all k≥1k \ge 1, 10k=0  (5)10^k = 0 \; (5).
    • Therefore, a=100a0+∑k=1n10kak=a0+0=a0  (5)a = 10^0 a_0 + \sum_{k=1}^n 10^k a_k = a_0 + 0 = a_0 \; (5).
    • Criterion: A natural number aa is divisible by 55 if and only if its unit digit a0a_0 is divisible by 55 (i.e., a0=0a_0 = 0 or a0=5a_0 = 5).
    • Exercice 11 (Divisibility by 9, 3, and 6):
    • 1. Divisibility by 9: Since a=∑k=0nak  (9)a = \sum_{k=0}^n a_k \; (9), a=0  (9)a = 0 \; (9) if and only if ∑k=0nak=0  (9)\sum_{k=0}^n a_k = 0 \; (9). A natural number is divisible by 99 if and only if the sum of its digits is a multiple of 99
    • 2. Divisibility by 3: Since 10=1  (3)10 = 1 \; (3), by similar reasoning a=∑k=0nak  (3)a = \sum_{k=0}^n a_k \; (3). An integer is divisible by 33 if and only if the sum of its digits is a multiple of 33
    • 3. Divisibility by 6: An integer is divisible by 66 if and only if it is divisible by both 22 and 33. Thus, it must be even (ending in 0,2,4,6,80, 2, 4, 6, 8) and the sum of its digits must be a multiple of 33
    • Exercice 12 (Divisibility by 11):
    • For any natural number k∈Nk \in \mathbb{N}:
      • 10=−1  (11)10 = -1 \; (11)
      • 102k=(−1)2k=1  (11)10^{2k} = (-1)^{2k} = 1 \; (11)
      • 102k+1=(−1)2k+1=−1  (11)10^{2k+1} = (-1)^{2k+1} = -1 \; (11)
    • Criterion: An integer a=∑k=0n10kaka = \sum_{k=0}^n 10^k a_k is congruent modulo 1111 to the alternating sum of its digits: a=∑k=0n(−1)kak=a0−a1+a2−a3+…  (11)a = \sum_{k=0}^n (-1)^k a_k = a_0 - a_1 + a_2 - a_3 + \dots \; (11). A number is divisible by 1111 if and only if this alternating sum of its digits is a multiple of 1111

Python Implementations and Vigenère Cipher

  • Exercice 5 (Python Congruence Function):
    • Implementation of congrus(a, b, n) to test congruence:
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: −5−(−9)=4-5 - (-9) = 4. Since 4 mod 3≠04 \bmod 3 \neq 0, 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 ?'
  • Character encoding reference functions:
    • ord('A') outputs 65, chr(65) outputs 'A'
    • ord('B') outputs 66, 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 ?'
    • Decryption:
      • Call: vigenere('IM FBIU TSET BFAV! CPMNEOT DA WA ?', 'ab', 1)
      • Output: 'IL FAIT TRES BEAU! COMMENT CA VA ?'

Historical Notes and Institutional Context

  • Historical References in Modular Arithmetic:
    • Carl Friedrich Gauss: Introduced the standard symbol ≡\equiv 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).