8. Arithmétique dans ℤ
Divisibilité, division euclidienne, congruences, PGCD, Bézout, Gauss, nombres premiers et Fermat.
∑Résumé du cours
Divisibilité et division euclidienne
a = bq + r, 0 ≤ r < |b|. Si d | a et d | b alors d | (au + bv).
Congruences
a ≡ b [n] ⇔ n | (a − b). Compatibles avec + et × ; a ≡ b [n] ⇒ aᵏ ≡ bᵏ [n].
PGCD, PPCM
Algorithme d’Euclide : PGCD(a, b) = PGCD(b, r). PGCD × PPCM = |ab|.
Théorèmes
- Bézout : a ∧ b = 1 ⇔ ∃ (u, v) ∈ ℤ², au + bv = 1.
- Gauss : a | bc et a ∧ b = 1 ⇒ a | c.
- Équation ax + by = c : solutions si PGCD(a, b) | c ; solution particulière + solutions de ax + by = 0.
Nombres premiers
Infinité de nombres premiers ; décomposition unique. Fermat : p premier, p ∤ a ⇒ ap−1 ≡ 1 [p].
✎Exemples corrigés
Exemple 1
Résoudre 7x + 5y = 1 dans ℤ².
Voir la correction
Exemple 2
Reste de 2²⁰²⁶ dans la division par 7.
Voir la correction
?Teste-toi
Clique sur la bonne réponse.
-
Théorème de Bézout : a ∧ b = 1 ⇔ …
Réponse
a) ∃ u, v : au + bv = 1 — Coefficients de Bézout. -
3⁶ ≡ ? [7]
Réponse
a) 1 — Fermat. -
PGCD(84, 36) = ?
Réponse
b) 12 — Euclide : 84 = 2×36 + 12, 36 = 3×12.
القسمة، القسمة الأقليدية، الموافقات، القاسم المشترك الأكبر، مبرهنتا بوزو وغوص، الأعداد الأولية ومبرهنة فيرما.
∑ملخص الدرس
القسمة والقسمة الأقليدية
a = bq + r، 0 ≤ r < |b|. إذا كان d | a و d | b فإن d | (au + bv).
الموافقات
a ≡ b [n] ⇔ n | (a − b). متلائمة مع + و × ؛ a ≡ b [n] ⇒ aᵏ ≡ bᵏ [n].
القاسم المشترك الأكبر والمضاعف المشترك الأصغر
خوارزمية أقليدس: PGCD(a, b) = PGCD(b, r). PGCD × PPCM = |ab|.
مبرهنات
- بوزو: a ∧ b = 1 ⇔ ∃ (u, v) ∈ ℤ²، au + bv = 1.
- غوص: a | bc و a ∧ b = 1 ⇒ a | c.
- المعادلة ax + by = c: لها حلول إذا كان PGCD(a, b) | c ؛ حل خاص + حلول ax + by = 0.
الأعداد الأولية
مجموعة الأعداد الأولية لا منتهية؛ التفكيك وحيد. فيرما: p أولي، p ∤ a ⇒ ap−1 ≡ 1 [p].
✎أمثلة محلولة
مثال 1
حل في ℤ² المعادلة 7x + 5y = 1.
عرض الحل
مثال 2
باقي قسمة 2²⁰²⁶ على 7.
عرض الحل
?اختبر نفسك
اضغط على الجواب الصحيح.
-
مبرهنة بوزو: a ∧ b = 1 ⇔ …
الجواب
أ) ∃ u, v : au + bv = 1 — معاملات بوزو. -
3⁶ ≡ ؟ [7]
الجواب
أ) 1 — فيرما. -
PGCD(84, 36) = ؟
الجواب
ب) 12 — أقليدس: 84 = 2×36 + 12، 36 = 3×12.
Résumé rédigé par Nqraw selon le programme officiel marocain.