Lessons and exercises follow the school system and stay in its language.Les leçons et les exercices suivent le système scolaire et restent dans sa langue.Lektionen und Übungen folgen dem Schulsystem und bleiben in seiner Sprache.

Divisibilité et congruences

Imprimer le chapitre

Toutes les leçons du chapitre, prêtes pour le papier. Les séries d'exercices sont notées A, B, C… et corrigées à la fin.

Pour obtenir un PDF, choisis « Enregistrer au format PDF » dans la fenêtre d'impression.

1. Divisibilité et division euclidienne

Échauffement

Trois questions rapides sur des leçons déjà vues.

  1. Un rectangle a pour sommets (−3;6)(-3 ; 6), (5;6)(5 ; 6), (5;−3)(5 ; -3) et (−3;−3)(-3 ; -3).
    1. Sa largeur (côté horizontal) :   ?\;?
    2. Sa hauteur (côté vertical) :   ?\;?
    3. Son périmètre :   ?\;?
    4. Ce rectangle est la base d'un prisme droit de hauteur 4. Son volume :
    5. La distance du sommet (−3;6)(-3 ; 6) à l'axe des ordonnées est ∣−3∣|-3| :
    6. On empile des prismes de hauteur 4 et de hauteur 5 en deux tours. La plus petite hauteur commune :
  2. Quel est le PGCD de 10 et 14 ?
  3. Quel est le PPCM de 4 et 14 ?

Découvrir

Lequel de ces nombres divise 12 ?

  1. 33
  2. 2424

L'idée clé

Dans Z\mathbb{Z}, on parle de multiples et de diviseurs.

aa divise bb s'il existe un entier kk tel que b=kab = ka. Si aa divise bb et cc, alors aa divise ub+vcub + vc.

Division euclidienne de aa par b≥1b \geq 1 : il existe un unique couple (q;r)(q ; r) tel que a=bq+ra = bq + r et 0≤r<b0 \leq r < b.

Exemple corrigé

Effectue la division euclidienne de −17-17 par 5.

−17=5×(−4)+3-17 = 5 \times (-4) + 3
On cherche un reste positif.
q=−4q = -4, r=3r = 3
0 ≤ 3 < 5 : c'est bon.

À toi, guidé

À toi : quel est le reste de la division de 23 par 4 ?

33
23 = 4 × 5 + 3.

Entraînement ★

  1. Quel est le reste de la division euclidienne de 1414 par 3 ?
  2. Quel est le reste de la division euclidienne de 293293 par 11 ?
  3. Quel est le reste de la division euclidienne de 1010 par 3 ?

Attention !

Entraînement ★★

  1. Quel est le reste de la division euclidienne de −10-10 par 4 ?
  2. Quel est le reste de la division euclidienne de −15-15 par 4 ?
  1. On sait que 9 divise xx et yy. Quel nombre 9 divise-t-il toujours ?
    1. 7x+4y7x + 4y
    2. x+1x + 1
    3. xy\dfrac{x}{y}
  1. Quel est le quotient de la division euclidienne de 2222 par 5 ?

Bilan

Trois questions pour vérifier que c'est acquis.

  1. Quel est le reste de la division euclidienne de 1414 par 3 ?
  2. Quel est le reste de la division euclidienne de 293293 par 11 ?
  3. Quel est le reste de la division euclidienne de 1010 par 3 ?

Fiche résumé

Division euclidienne

  • a=bq+ra = bq + r, avec 0≤r<b0 \leq r < b.
  • a∣ba \mid b signifie b=kab = ka.

Attention : le reste n'est jamais négatif.

Il reste une étape facultative : un défi. Tente-le, ou termine la leçon maintenant.

Défi ★★★

  1. Le reste de la division euclidienne de xx par 11 est 1. Quel est le reste de la division de 3x3x par 11 ?

2. Congruences

Échauffement

Trois questions rapides sur des leçons déjà vues.

  1. Quel est le reste de la division euclidienne de 1414 par 3 ?
  2. Quel est le reste de la division euclidienne de −10-10 par 4 ?
  3. On sait que 9 divise xx et yy. Quel nombre 9 divise-t-il toujours ?
    1. 7x+4y7x + 4y
    2. x+1x + 1
    3. xy\dfrac{x}{y}

Découvrir

Il est 22 h. Quelle heure sera-t-il dans 5 heures ?

  1. 3 h
  2. 27 h

L'idée clé

Deux entiers sont congrus s'ils ont le même reste.

a≡b [n]a \equiv b\ [n] signifie que nn divise a−ba - b.

On peut additionner, multiplier et élever à une puissance : si a≡b [n]a \equiv b\ [n] et c≡d [n]c \equiv d\ [n], alors a+c≡b+da + c \equiv b + d, ac≡bdac \equiv bd et ak≡bk [n]a^k \equiv b^k\ [n].

Exemple corrigé

Quel est le reste de la division de 71007^{100} par 5 ?

7≡2 [5]7 \equiv 2\ [5]
On réduit.
24≡1 [5]2^4 \equiv 1\ [5]
2⁴ = 16 ≡ 1.
7100≡(24)25≡1 [5]7^{100} \equiv (2^4)^{25} \equiv 1\ [5]
100 = 4 × 25.

À toi, guidé

À toi : réduis 38 modulo 7.

33
38 = 7 × 5 + 3.

Entraînement ★

  1. Quel est le plus petit entier positif xx tel que 21≡x [5]21 \equiv x\ [5] ?
  2. Quel est le plus petit entier positif xx tel que 399≡x [15]399 \equiv x\ [15] ?
  3. Quel est le plus petit entier positif xx tel que 16≡x [3]16 \equiv x\ [3] ?

Attention !

Entraînement ★★

  1. Quel est le reste de la division de 282^{ 8 } par 5 ?
  2. Quel est le reste de la division de 21602^{ 160 } par 5 ?
  1. On sait que x≡2 [9]x \equiv 2\ [9] et y≡1 [9]y \equiv 1\ [9]. Quel est le reste de x+yx + y modulo 9 ?
  1. Quel est le reste de la division de 10210^{ 2 } par 11 ?

Bilan

Trois questions pour vérifier que c'est acquis.

  1. Quel est le plus petit entier positif xx tel que 21≡x [5]21 \equiv x\ [5] ?
  2. Quel est le plus petit entier positif xx tel que 399≡x [15]399 \equiv x\ [15] ?
  3. Quel est le plus petit entier positif xx tel que 16≡x [3]16 \equiv x\ [3] ?

Fiche résumé

Congruences

  • a≡b [n]  ⟺  n∣a−ba \equiv b\ [n] \iff n \mid a - b.
  • On additionne, on multiplie, on élève à une puissance.

Attention : on ne divise pas dans une congruence.

Il reste une étape facultative : un défi. Tente-le, ou termine la leçon maintenant.

Défi ★★★

  1. Quel est le chiffre des unités de 7177^{ 17 } ?

3. Nombres premiers et décomposition

Échauffement

Trois questions rapides sur des leçons déjà vues.

  1. Quel est le reste de la division euclidienne de 1414 par 3 ?
  2. Quel est le reste de la division euclidienne de −10-10 par 4 ?
  3. On sait que 9 divise xx et yy. Quel nombre 9 divise-t-il toujours ?
    1. 7x+4y7x + 4y
    2. x+1x + 1
    3. xy\dfrac{x}{y}

Découvrir

Lequel de ces nombres est premier ?

  1. 1313
  2. 99

L'idée clé

Un nombre premier a exactement deux diviseurs positifs.

Tout entier n≥2n \geq 2 se décompose de façon unique en produit de facteurs premiers.

L'ensemble des nombres premiers est infini. Pour tester si nn est premier, il suffit d'essayer les premiers pp tels que p2≤np^2 \leq n.

Exemple corrigé

Décompose 360.

360=23×45360 = 2^3 \times 45
On divise par 2.
45=32×545 = 3^2 \times 5
On divise par 3.
360=23×32×5360 = 2^3 \times 3^2 \times 5
Décomposition.

À toi, guidé

À toi : quel est le plus petit nombre premier ?

22
1 n'est pas premier.

Entraînement ★

  1. Combien de diviseurs positifs le nombre 21×322^{ 1 } \times 3^{ 2 } a-t-il ?
  2. Combien de diviseurs positifs le nombre 27×382^{ 7 } \times 3^{ 8 } a-t-il ?
  3. Combien de diviseurs positifs le nombre 21×312^{ 1 } \times 3^{ 1 } a-t-il ?

Attention !

Entraînement ★★

  1. Lequel de ces nombres est premier ?
    1. 101101
    2. 9191
    3. 11
  2. Lequel de ces nombres est premier ?
    1. 101101
    2. 9191
    3. 11
  1. On écrit 432432 sous la forme 2x×3y2^x \times 3^y. Que vaut xx ?
  1. Le nombre 1 est-il premier ?
    1. Non : un nombre premier a exactement deux diviseurs
    2. Oui : il n'est divisible que par lui-même
    3. Oui : tout nombre impair est premier

Bilan

Trois questions pour vérifier que c'est acquis.

  1. Combien de diviseurs positifs le nombre 21×322^{ 1 } \times 3^{ 2 } a-t-il ?
  2. Combien de diviseurs positifs le nombre 27×382^{ 7 } \times 3^{ 8 } a-t-il ?
  3. Combien de diviseurs positifs le nombre 21×312^{ 1 } \times 3^{ 1 } a-t-il ?

Fiche résumé

Nombres premiers

  • Exactement deux diviseurs positifs.
  • Décomposition unique.

Attention : 1 n'est pas premier.

Il reste une étape facultative : un défi. Tente-le, ou termine la leçon maintenant.

Défi ★★★

  1. Combien de diviseurs positifs le nombre 21×32×512^{ 1 } \times 3^{ 2 } \times 5^{ 1 } a-t-il ?

4. Petit théorème de Fermat

Échauffement

Trois questions rapides sur des leçons déjà vues.

  1. Quel est le plus petit entier positif xx tel que 21≡x [5]21 \equiv x\ [5] ?
  2. Quel est le reste de la division de 282^{ 8 } par 5 ?
  3. On sait que x≡2 [9]x \equiv 2\ [9] et y≡1 [9]y \equiv 1\ [9]. Quel est le reste de x+yx + y modulo 9 ?

Découvrir

Calcule 262^6 modulo 7.

  1. 11
  2. 00

L'idée clé

Ce théorème simplifie les grandes puissances.

Petit théorème de Fermat : si pp est premier et si pp ne divise pas aa, alors ap−1≡1 [p]a^{p - 1} \equiv 1\ [p].

Pour tout entier aa : ap≡a [p]a^p \equiv a\ [p].

Exemple corrigé

Trouve le reste de la division de 31003^{100} par 11.

310≡1 [11]3^{10} \equiv 1\ [11]
Fermat : 3¹⁰ ≡ 1.
3100≡1 [11]3^{100} \equiv 1\ [11]
100 = 10 × 10.

À toi, guidé

À toi : quel est le reste de la division de 464^{6} par 7 ?

11
7 est premier et ne divise pas 4.

Entraînement ★

  1. Quel est le reste de la division de 5125^{ 12 } par 7 ?
  2. Quel est le reste de la division de 42704^{ 270 } par 7 ?
  3. Quel est le reste de la division de 4124^{ 12 } par 7 ?

Attention !

Entraînement ★★

  1. Quel est le reste de la division de 8118^{11} par 11 ?
  2. Quel est le reste de la division de 7117^{11} par 11 ?
  1. D'après le petit théorème de Fermat, quel est le reste de 4124^{12} modulo 13 ?
    1. 1
    2. 44
    3. 0
  1. Quel est le reste de la division de 575^{ 7 } par 7 ?

Bilan

Trois questions pour vérifier que c'est acquis.

  1. Quel est le reste de la division de 5125^{ 12 } par 7 ?
  2. Quel est le reste de la division de 42704^{ 270 } par 7 ?
  3. Quel est le reste de la division de 4124^{ 12 } par 7 ?

Fiche résumé

Fermat

  • ap−1≡1 [p]a^{p - 1} \equiv 1\ [p], pour pp premier ne divisant pas aa.
  • ap≡a [p]a^p \equiv a\ [p].

Attention : vérifie que pp est premier.

Il reste une étape facultative : un défi. Tente-le, ou termine la leçon maintenant.

Défi ★★★

  1. Quel est le reste de la division de 320263^{2026} par 7 ?

5. Compter les diviseurs

Découvrir

12=22×312 = 2^2 \times 3 a pour diviseurs 1, 2, 3, 4, 6, 12 : six diviseurs. Peut-on trouver ce nombre sans les écrire ?

  1. Oui : (2+1)(1+1)=6(2 + 1)(1 + 1) = 6
  2. Oui : 2+1=32 + 1 = 3

L'idée clé

Compter les diviseurs.

Si n=p1a1×p2a2×⋯×pkakn = p_1^{a_1} \times p_2^{a_2} \times \dots \times p_k^{a_k} (décomposition en facteurs premiers), le nombre de diviseurs positifs de nn est

(a1+1)(a2+1)⋯(ak+1)(a_1 + 1)(a_2 + 1) \cdots (a_k + 1).

Exemple corrigé

Nombre de diviseurs de 360=23×32×5360 = 2^3 \times 3^2 \times 5.

(3+1)(2+1)(1+1)(3 + 1)(2 + 1)(1 + 1)
Exposants 3, 2, 1.
=24= 24 diviseurs
On multiplie.

À toi, guidé

À toi : nombre de diviseurs de 252^5 ?

66
5+15 + 1.

Entraînement ★

  1. Combien de diviseurs positifs a 26×322^{ 6 } \times 3^{ 2 } ?
  2. Combien de diviseurs positifs a 24×332^{ 4 } \times 3^{ 3 } ?
  3. Combien de diviseurs positifs a 23×352^{ 3 } \times 3^{ 5 } ?

Entraînement ★★

  1. Combien de diviseurs positifs a n=25×52×72n = 2^{ 5 } \times 5^{ 2 } \times 7^{ 2 } ?
  2. Combien de diviseurs positifs a n=22×52×71n = 2^{ 2 } \times 5^{ 2 } \times 7^{ 1 } ?

Bilan

Deux questions pour vérifier.

  1. Combien de diviseurs positifs a 26×322^{ 6 } \times 3^{ 2 } ?
  2. Combien de diviseurs positifs a 24×332^{ 4 } \times 3^{ 3 } ?

Fiche résumé

Nombre de diviseurs

  • (a1+1)(a2+1)⋯(a_1 + 1)(a_2 + 1) \cdots
  • Un carré parfait a un nombre impair de diviseurs.

On a choisi 360 degrés pour le tour complet en partie parce que 360 a beaucoup de diviseurs.

6. Histoire de l'arithmétique : Euclide, Fermat et Gauss

Découvrir

Le livre VII des Éléments d'Euclide (vers 300 av. J.-C.) contient une méthode pour trouver le PGCD de deux nombres. Laquelle ?

  1. Les divisions successives : l'algorithme d'Euclide
  2. Écrire tous les diviseurs et comparer

L'idée clé

De l'algorithme d'Euclide aux congruences.

150010001500vers 300 av. J.-C.Euclidevers 300 av. J.-C.Euclide
  1. Étape 1150010001500vers 300 av. J.-C.Euclidevers 300 av. J.-C.EuclideEuclide vers 300 av. J.-C.Portrait imaginéAuteur inconnu. Domaine publicVers 300 av. J.-C. : le livre VII des Éléments et l'algorithme d'Euclide.
  2. Étape 2150010001500vers 300 av. J.-C.Euclide1640Fermatvers 300 av. J.-C.Euclide1640FermatPierre de Fermat vers 1607 – 1665Rolland Lefebvre. Domaine public1640 : correspondance de Fermat et Frenicle sur les nombres.
  3. Étape 3150010001500vers 300 av. J.-C.Euclide1640Fermat1801Gaussvers 300 av. J.-C.Euclide1640Fermat1801GaussCarl Friedrich Gauss 1777–1855Gottlieb Biermann / After Christian Albrecht Jensen, 1840. Domaine publicÉté 1801 : Gauss publie les Disquisitiones arithmeticae.

Le livre VII des Éléments d'Euclide est une introduction à la théorie des nombres et contient l'algorithme d'Euclide. Fermat (1601–1665) échange des problèmes de nombres avec Frenicle de Bessy, notamment en 1640. À l'été 1801, Gauss publie les Disquisitiones arithmeticae (« Recherches arithmétiques »), qui fondent la théorie moderne des nombres.

Exemple corrigé

PGCD de 252 et 198 par l'algorithme d'Euclide.

54=1×36+1854 = 1 \times 36 + 18, 36=2×18+036 = 2 \times 18 + 0
252=1×198+54252 = 1 \times 198 + 54, 198=3×54+36198 = 3 \times 54 + 36.
PGCD=18\mathrm{PGCD} = 18
Dernier reste non nul.

Entraînement ★

  1. Quel livre Gauss publie-t-il à l'été 1801 ?
    1. Les Disquisitiones arithmeticae
    2. Les Éléments
    3. La Géométrie
  1. Première étape de l'algorithme d'Euclide : quel est le reste de la division euclidienne de 252 par 15 ?
  2. Première étape de l'algorithme d'Euclide : quel est le reste de la division euclidienne de 122 par 17 ?
  1. Avec la notation de Gauss : x≡2(mod8)x \equiv 2 \pmod{ 8 } et y≡2(mod8)y \equiv 2 \pmod{ 8 }. Quel est le reste de x+yx + y modulo 8 ?

Fiche résumé

L'arithmétique aujourd'hui

  • Cryptographie : les paiements en ligne reposent sur les nombres premiers et les congruences.
  • Codes correcteurs : numéros ISBN, IBAN et cartes bancaires ont une clé de contrôle.
  • Calendriers : les jours de la semaine se calculent modulo 7.

Sources : biographies d'Euclide, de Fermat et de Gauss sur MacTutor (voir « Sources et crédits »).