Arithmétique modulaire

Définition

Rappel : On définit la relation d’équivalence modulo \(n\) par

\[a ≡ b \mod n \quad⇔\quad n \mid (a-b).\]

On note \(\bar{a}\) la classe d’équivalence de \(a\) modulo \(n\), ou simplement \(a\) lorsque cela est clair du contexte.

  1. Montrer qu’il s’agit bien d’une relation d’équivalence.

  2. Donner la classe d’équivalence de \(-3\mod 7\).

  3. Lesquelles des égalités suivantes sont vraies ? Lesquelles sont fausses ?

    \[6 = 4 \mod 2,\quad 5 = -5 \mod 12,\quad 11 = -2 \mod 13,\quad 24 = 0 \mod 12.\]
  4. Montrer que la définition est équivalente à

    \[a ≡ b \mod n \quad⇔\quad ∃c.\; a = b + cn.\]
  5. Montrer que pour \(n=2\), la définition est équivalente à

    \[a ≡ b \mod 2 \quad⇔\quad 2 \mid (a + b).\]
  6. Soit \(n\) un entier quelconque, montrer les deux propriétés suivantes:

    • Si \(a ≡ b \mod n\) alors pour tout entier \(c\) on a \(a+c ≡ b+c \mod n\),
    • Si \(a ≡ b \mod n\) alors pour tout entier \(c\) on a \(ac ≡ bc \mod n\).

Structure additive

  1. Calculer un représentant pour les sommes suivantes

    \[5 + 5 \mod 10,\quad -1 + 4 \mod 6,\quad 9 - 15 \mod 4.\]
  2. Calculer un représentant pour les produits suivants

    \[3·3 \mod 7,\quad -1·9 \mod 5,\quad 14·12 \mod 15.\]
  3. Calculer les tables d’addition et de multiplication de \(ℤ/2ℤ\). A quels opérateurs du calcul des propositions correspondent-elles ?

  4. Calculer les tables d’addition et de multiplication de \(ℤ/6ℤ\).

  5. Calculer le résultat des expressions suivantes

    \[3 · (4 + 7) \mod 11,\quad 4 - 4 · 12 \mod 11,\quad (1234 + 789) · 12 \mod 10.\]

Structure multiplicative

Voici la table de multiplication de \(ℤ/15ℤ\). À partir de maintenant on va arrêter d’écrire \(\mod n\) partout: lorsque le module est clair du contexte, on se contentera d’écrire \(6+8=-1\), plutôt que \(6 + 8 = -1 \mod 15\).

  0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
2 0 2 4 6 8 10 12 14 1 3 5 7 9 11 13
3 0 3 6 9 12 0 3 6 9 12 0 3 6 9 12
4 0 4 8 12 1 5 9 13 2 6 10 14 3 7 11
5 0 5 10 0 5 10 0 5 10 0 5 10 0 5 10
6 0 6 12 3 9 0 6 12 3 9 0 6 12 3 9
7 0 7 14 6 13 5 12 4 11 3 10 2 9 1 8
8 0 8 1 9 2 10 3 11 4 12 5 13 6 14 7
9 0 9 3 12 6 0 9 3 12 6 0 9 3 12 6
10 0 10 5 0 10 5 0 10 5 0 10 5 0 10 5
11 0 11 7 3 14 10 6 2 13 9 5 1 12 8 4
12 0 12 9 6 3 0 12 9 6 3 0 12 9 6 3
13 0 13 11 9 7 5 3 1 14 12 10 8 6 4 2
14 0 14 13 12 11 10 9 8 7 6 5 4 3 2 1
  1. Quel est l’inverse (multiplicatif) de 2, 4, 7 ?

  2. Trouver un élément qui n’a pas d’inverse multiplicatif. \(ℤ/15ℤ\) est-il un corps ?

  3. Combien d’éléments contient \((ℤ/15ℤ)^*\) (le groupe des éléments inversibles de \(ℤ/15ℤ\)) ?

  4. Calculer \(3^3\), \(5^4\) et \(2^7\).

Corps finis

  1. Calculer la table de multiplication de \(ℤ/7ℤ\). Quels sont les éléments inversibles ? \(ℤ/7ℤ\) est-il un corps ?

  2. Calculer toutes les puissances de \(3\mod 7\).

  3. Montrer que si \(n=ab\), alors \(a \mod n\) est un diviseur de zéro.

  4. Montrer que un élément est inversible si et seulement s’il n’est pas un diviseur de zéro.

  5. Montrer que \(ℤ/nℤ\) est un corps si et seulement si \(n\) est premier.

Fork me on GitHub