Download Congruences 2 Chapitre B

2
Congruences
Chapitre A - Congruences
1. Divisibilité
1.1. Cours.
Définition 1. Pour tous entiers relatifs m et n, m divise n ssi il existe un entier relatif k tel que n = km.
Notation 1. On note m|n.
Remarque 1. Tout entier relatif est un diviseur de 0.
p|q
Théorème 1. ∀p, q, r ∈ Z,
⇒ p|r
q|r
Théorème 2. Si p divise m et n alors p divise toute combinaison linéaire à coefficients entiers de m et n.
2. Division euclidienne
2.1. Cours.
Axiome 1. Tout ensemble non vide d’entiers naturels admet un plus petit élément.
n = mq + r
∗
Théorème 3. ∀n ∈ Z, ∀m ∈ N , ∃!q ∈ Z, ∃!r ∈ N,
0≤r<m
q est le quotient et r le reste de cette division euclidienne.
Exemple 1. 328 = 17 × 19 + 5, q = 19, r = 5
Exemple 2. −328 = 17 × (−20) + 12, q = −20, r = 12
Démonstration. Soit E = {k ∈ N/km > n}.
Existence lorsque n>0
m≥1
donc (n + 1)m > n donc n + 1 ∈ E donc E 6= {} donc E admet un plus petit élément k0 .
n+1>n
Soit q = k0 − 1 et r = n − qm.
qm + r = n
(k0 − 1)m ≤ n < k0 m donc 0 ≤ n − (k0 − 1)m < m donc 0 ≤ n − qm < m donc 0 ≤ r < m.
Existence lorsque n<0
On se ramène au cas précédent en effectuant la division euclidienne de −n par m : −n = qm+r et 0 ≤ r < m.
n = −mq − r = (−q − 1)m + (m − r)
Si r = 0, la première expression est la division euclidienne cherchée, sinon c’est la deuxième. Dans ce dernier
cas, on vérifie la condition sur le reste :
0 < r < m donc −m < −r < 0 donc 0 ≤ m − r < m
Existence lorsque n=0
n = m × 0 + 0 et 0 ≤ 0 < m
Unicité
Supposons qu’il existe deux divisions euclidiennes différentes : n = m × q + r = m × q 0 + r0 .
(q − q 0 )m = r0 − r
0≤r<m
donc −m < r0 − r < m or r0 − r est divisible par m donc r0 − r = 0 or (1) donc q − q 0 = 0.
0 ≤ r0 < m
Absurde !
Remarque 2. Plus de dénominateurs en Spécialité.