5. Arithmétique dans ℤ
Divisibilité, division euclidienne, congruences, PGCD et nombres premiers.
∑Résumé du cours
Divisibilité et division euclidienne
a | b s’il existe k ∈ ℤ tel que b = ka. Pour a ∈ ℤ et b ∈ ℕ*, il existe un unique couple (q, r) : a = bq + r, 0 ≤ r < b.
Congruences
a ≡ b [n] ⇔ n | (a − b). Compatible avec + et × : si a ≡ b et c ≡ d [n], alors a + c ≡ b + d et ac ≡ bd [n], et aᵏ ≡ bᵏ [n].
PGCD et PPCM
Algorithme d’Euclide : PGCD(a, b) = PGCD(b, r). a ∧ b × a ∨ b = |ab|.
Nombres premiers
Il y a une infinité de nombres premiers. Décomposition unique en facteurs premiers. Test : n est premier s’il n’a aucun diviseur premier p avec p² ≤ n.
✎Exemples corrigés
Exemple 1
Reste de la division de 2²⁰²⁶ par 7.
Voir la correction
Exemple 2
PGCD(252 ; 198) par Euclide.
Voir la correction
?Teste-toi
Clique sur la bonne réponse.
-
17 ≡ ? [5]
Réponse
a) 2 — 17 = 3 × 5 + 2. -
Dans a = bq + r, on exige…
Réponse
a) 0 ≤ r < b — Unicité du reste. -
10ⁿ ≡ ? [9]
Réponse
b) 1 — 10 ≡ 1 [9] : d’où le critère de divisibilité par 9.
القسمة، القسمة الأقليدية، الموافقات، القاسم المشترك الأكبر والأعداد الأولية.
∑ملخص الدرس
القسمة والقسمة الأقليدية
a | b إذا وُجد k ∈ ℤ بحيث b = ka. لكل a ∈ ℤ و b ∈ ℕ*، يوجد زوج وحيد (q, r): a = bq + r، 0 ≤ r < b.
الموافقات
a ≡ b [n] ⇔ n | (a − b). متلائمة مع + و ×: إذا كان a ≡ b و c ≡ d [n]، فإن a + c ≡ b + d و ac ≡ bd [n]، و aᵏ ≡ bᵏ [n].
القاسم المشترك الأكبر والمضاعف المشترك الأصغر
خوارزمية أقليدس: PGCD(a, b) = PGCD(b, r). a ∧ b × a ∨ b = |ab|.
الأعداد الأولية
مجموعة الأعداد الأولية لا منتهية. التفكيك إلى جداء عوامل أولية وحيد. الاختبار: n أولي إذا لم يكن له أي قاسم أولي p بحيث p² ≤ n.
✎أمثلة محلولة
مثال 1
باقي قسمة 2²⁰²⁶ على 7.
عرض الحل
مثال 2
PGCD(252 ; 198) بخوارزمية أقليدس.
عرض الحل
?اختبر نفسك
اضغط على الجواب الصحيح.
-
17 ≡ ؟ [5]
الجواب
أ) 2 — 17 = 3 × 5 + 2. -
في a = bq + r، نشترط…
الجواب
أ) 0 ≤ r < b — وحدانية الباقي. -
10ⁿ ≡ ؟ [9]
الجواب
ب) 1 — 10 ≡ 1 [9]: ومنه معيار القسمة على 9.
Résumé rédigé par Nqraw selon le programme officiel marocain.