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.

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 2222 par 4 ?
  2. Quel est le reste de la division euclidienne de 2626 par 4 ?
  3. Quel est le reste de la division euclidienne de 5555 par 9 ?

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 3838 par 6 ?

Bilan

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

  1. Quel est le reste de la division euclidienne de 2222 par 4 ?
  2. Quel est le reste de la division euclidienne de 2626 par 4 ?
  3. Quel est le reste de la division euclidienne de 5555 par 9 ?

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.

2. Congruences

Échauffement

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

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 18≡x [4]18 \equiv x\ [4] ?
  2. Quel est le plus petit entier positif xx tel que 29≡x [9]29 \equiv x\ [9] ?
  3. Quel est le plus petit entier positif xx tel que 9≡x [4]9 \equiv x\ [4] ?

Attention !

Entraînement ★★

  1. Quel est le reste de la division de 2202^{ 20 } par 5 ?
  2. Quel est le reste de la division de 2242^{ 24 } 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 101010^{ 10 } par 11 ?

Bilan

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

  1. Quel est le plus petit entier positif xx tel que 18≡x [4]18 \equiv x\ [4] ?
  2. Quel est le plus petit entier positif xx tel que 29≡x [9]29 \equiv x\ [9] ?
  3. Quel est le plus petit entier positif xx tel que 9≡x [4]9 \equiv x\ [4] ?

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.

3. Nombres premiers et décomposition

Échauffement

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

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 24×322^{ 4 } \times 3^{ 2 } a-t-il ?
  3. Combien de diviseurs positifs le nombre 23×322^{ 3 } \times 3^{ 2 } 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 24×322^{ 4 } \times 3^{ 2 } a-t-il ?
  3. Combien de diviseurs positifs le nombre 23×322^{ 3 } \times 3^{ 2 } a-t-il ?

Fiche résumé

Nombres premiers

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

Attention : 1 n'est pas premier.

4. Petit théorème de Fermat

Échauffement

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

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 4124^{ 12 } par 7 ?
  2. Quel est le reste de la division de 6186^{ 18 } par 7 ?
  3. Quel est le reste de la division de 5185^{ 18 } 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. Problème final. On étudie 3253^{ 25 } modulo 7.
  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 272^{ 7 } par 7 ?

Bilan

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

  1. Quel est le reste de la division de 4124^{ 12 } par 7 ?
  2. Quel est le reste de la division de 6186^{ 18 } par 7 ?
  3. Quel est le reste de la division de 5185^{ 18 } 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.

Corrigé: Divisibilité et congruences

1. Divisibilité et division euclidienne

A

  1. 22
  2. 22
  3. 11

B

  1. 22
  2. 11

C

  1. 7x+4y7x + 4y

D

  1. 66

E

  1. 22
  2. 22
  3. 11

2. Congruences

A

  1. 22
  2. 22
  3. 11

B

  1. 11
  2. 11

C

  1. 33

D

  1. 11

E

  1. 22
  2. 22
  3. 11

3. Nombres premiers et décomposition

A

  1. 66
  2. 1515
  3. 1212

B

  1. 101101
  2. 101101

C

  1. 44

D

  1. Non : un nombre premier a exactement deux diviseurs

E

  1. 66
  2. 1515
  3. 1212

4. Petit théorème de Fermat

A

  1. 11
  2. 11
  3. 11

B

  1. 88
  2. 77

C

  1. 33

D

  1. 1

E

  1. 22

F

  1. 11
  2. 11
  3. 11