Divisibilité et division euclidienne

Arithmétique — Terminale Maths Expertes

Divisibilité et division euclidienne

1. Divisibilité dans Z

Divisibilité : Soient a et b deux entiers relatifs. On dit que b divise a (ou que a est divisible par b) s'il existe un entier q tel que :

[formule]

On note b a (lire "b divise a").

Si b ne divise pas a, on note b a.

Exemples :

  • 3 12 car 12 = 3 4
  • -5 15 car 15 = (-5) (-3)
  • 7 20 car il n'existe pas d'entier q tel que 20 = 7q
  • Tout entier divise 0 : a 0 pour tout a Z^*

Propriétés de la divisibilité : Pour tous a, b, c Z :

  1. Réflexivité : a a
  2. Transitivité : Si a b et b c, alors a c
  3. Linéarité : Si a b et a c, alors a ( b + c) pour tous , Z
  4. Multiplication : Si a b, alors ac bc pour tout c Z
  5. Division : Si a b et c 0, alors a{c} b{c} (si c divise aussi a et b)

Exemple : Montrer que si n est un entier pair, alors n^2 est pair.

Si n est pair, alors 2 n, donc il existe k Z tel que n = 2k.

Ainsi n^2 = (2k)^2 = 4k^2 = 2(2k^2), donc 2 n^2.

2. Division euclidienne

Théorème de la division euclidienne : Soient a Z et b N^*. Il existe un unique couple (q, r) Z N tel que :

[formule]

  • q est le quotient de la division euclidienne de a par b
  • r est le reste de la division euclidienne de a par b

Exemples :

  • Division de 23 par 5 : 23 = 5 4 + 3 (quotient 4, reste 3)
  • Division de -17 par 5 : -17 = 5 (-4) + 3 (quotient -4, reste 3)
  • Division de 100 par 7 : 100 = 7 14 + 2 (quotient 14, reste 2)

Algorithme de la division euclidienne : Pour diviser a par b > 0 :

  1. Si a 0 : q est le quotient de la division entière, r = a - bq
  2. Si a < 0 : on écrit -a = bq' + r' avec 0 r' < b
    • Si r' = 0 : a = b(-q') + 0
    • Si r' > 0 : a = b(-q' - 1) + (b - r') (car -a = bq' + r' implique a = -bq' - r' = b(-q' - 1) + b - r')

Exemple : Division de -23 par 5 :

On a 23 = 5 4 + 3, donc -23 = 5 (-4) - 3 = 5 (-5) + 2.

Ainsi quotient = -5 et reste = 2 (vérification : 5 (-5) + 2 = -25 + 2 = -23).

3. Congruences

Congruence modulo n : Soient a, b Z et n N^*. On dit que a est congru à b modulo n si n (a - b).

On note a b n.

Caractérisation : a b n si et seulement si a et b ont le même reste dans la division euclidienne par n.

Exemples :

  • 17 2 5 car 17 = 5 3 + 2 et 2 = 5 0 + 2
  • 23 3 10 car 23 = 10 2 + 3 et 3 = 10 0 + 3
  • -7 3 10 car -7 = 10 (-1) + 3

Propriétés des congruences : Pour tous a, b, c, d Z et n N^* :

  1. Réflexivité : a a n
  2. Symétrie : Si a b n, alors b a n
  3. Transitivité : Si a b n et b c n, alors a c n
  4. Compatibilité avec l'addition : Si a b n et c d n, alors a + c b + d n
  5. Compatibilité avec la multiplication : Si a b n et c d n, alors ac bd n
  6. Puissances : Si a b n, alors a^k b^k n pour tout k N

Exemple : Calculer le reste de la division de 2^{100} par 7.

On cherche r tel que 2^{100} r 7 avec 0 r < 7.

  • 2^1 = 2 2 7
  • 2^2 = 4 4 7
  • 2^3 = 8 1 7

Donc 2^3 1 7, d'où 2^{3k} 1 7 pour tout k.

Comme 100 = 3 33 + 1, on a 2^{100} = 2^{3 33 + 1} = (2^3)^{33} 2 1^{33} 2 = 2 7.

Le reste est 2.

4. Critères de divisibilité

Critères de divisibilité usuels : Soit n un entier écrit en base 10 : n = a_k a_{k-1} a_1 a_0 (où a_i sont les chiffres).

  • Divisibilité par 2 : n est divisible par 2 si et seulement si a_0 est pair (i.e. a_0 {0, 2, 4, 6, 8})
  • Divisibilité par 3 : n est divisible par 3 si et seulement si la somme de ses chiffres est divisible par 3
  • Divisibilité par 4 : n est divisible par 4 si et seulement si le nombre formé par ses deux derniers chiffres est divisible par 4
  • Divisibilité par 5 : n est divisible par 5 si et seulement si a_0 {0, 5}
  • Divisibilité par 9 : n est divisible par 9 si et seulement si la somme de ses chiffres est divisible par 9
  • Divisibilité par 11 : n est divisible par 11 si et seulement si la différence entre la somme des chiffres de rang pair et la somme des chiffres de rang impair est divisible par 11

Exemples :

  • 1234 est divisible par 2 car le chiffre des unités est 4 (pair)
  • 123 est divisible par 3 car 1 + 2 + 3 = 6 est divisible par 3
  • 1236 est divisible par 4 car 36 est divisible par 4
  • 12345 est divisible par 5 car le chiffre des unités est 5
  • 1233 est divisible par 9 car 1 + 2 + 3 + 3 = 9 est divisible par 9
  • 121 est divisible par 11 car (1 + 1) - 2 = 0 est divisible par 11

5. Nombres premiers

Nombre premier : Un entier p 2 est premier si ses seuls diviseurs positifs sont 1 et p.

Un entier n 2 qui n'est pas premier est dit composé.

Exemples :

  • Nombres premiers : 2, 3, 5, 7, 11, 13, 17, 19, 23, 29,
  • Nombres composés : 4 = 2^2, 6 = 2 3, 8 = 2^3, 9 = 3^2, 10 = 2 5, 12 = 2^2 3,
  • 1 n'est ni premier ni composé (par convention)

Théorème fondamental de l'arithmétique : Tout entier n 2 s'écrit de manière unique (à l'ordre près) comme produit de nombres premiers :

[formule]

où p_1 < p_2 < < p_k sont des nombres premiers et _i N^*.

Cette écriture est appelée la décomposition en facteurs premiers de n.

Exemples :

  • 12 = 2^2 3
  • 60 = 2^2 3 5
  • 100 = 2^2 5^2
  • 2310 = 2 3 5 7 11

Crible d'Ératosthène : Pour trouver tous les nombres premiers inférieurs à n :

  1. Écrire tous les entiers de 2 à n
  2. Barrer tous les multiples de 2 (sauf 2)
  3. Prendre le premier nombre non barré (3), barrer tous ses multiples
  4. Répéter avec le nombre suivant non barré
  5. Les nombres non barrés sont premiers

6. Applications

Preuve par contraposée : Montrer que si n^2 est pair, alors n est pair.

On utilise la contraposée : si n est impair, alors n^2 est impair.

Si n est impair, alors n = 2k + 1 pour un certain k Z.

Ainsi n^2 = (2k + 1)^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1, donc n^2 est impair.

Problème de congruences : Trouver tous les entiers n tels que n^2 1 8.

On teste les restes possibles modulo 8 :

  • 0^2 = 0 0 8
  • 1^2 = 1 1 8 ✓
  • 2^2 = 4 4 8
  • 3^2 = 9 1 8 ✓
  • 4^2 = 16 0 8
  • 5^2 = 25 1 8 ✓
  • 6^2 = 36 4 8
  • 7^2 = 49 1 8 ✓

Donc n^2 1 8 si et seulement si n 1, 3, 5, 7 8, c'est-à-dire si n est impair.

À retenir

Résumé :

  1. Divisibilité : b a s'il existe q tel que a = bq

  2. Division euclidienne : a = bq + r avec 0 r < b (unicité du couple (q, r))

  3. Congruence : a b n si n (a - b)

  4. Propriétés : compatibilité des congruences avec addition, multiplication, puissances

  5. Nombres premiers : entiers 2 dont les seuls diviseurs sont 1 et lui-même

  6. Décomposition : tout entier 2 s'écrit de manière unique comme produit de nombres premiers