Divisibilité et congruences

Merci !

Fiches
Classe(s) : Tle Générale | Thème(s) : Arithmétique


La relation de congruence est l’une des bases de l’arithmétique modulaire. Au lieu de considérer les entiers, on raisonne suivant leur reste dans la division euclidienne par un entier fixé.

I Divisibilité dans ℤ

Définitions : Si a et b sont deux entiers relatifs, on dit que b divise a ou que b est un diviseur de a ou que a est un multiple de b ou que a est divisible par b lorsqu’il existe un entier relatif k tel que a=kb.

On note b|a.

Propriétés

Tout entier relatif non nul n possède un nombre fini de diviseurs, compris entre n et n.

Soit a, b et c trois entiers relatifs, avec a0 et b0. Si a divise b et b divise c, alors a divise c.

MOT CLÉ

ℤ est l’ensemble des entiers relatifs, ℕ est l’ensemble des entiers naturels.

ℕ est inclus dans ℤ, on note   .

Soit a, b et c trois entiers relatifs, avec a0. Si a divise b et c, alors a divise tout nombre de la forme mb+nc, où m et n sont des entiers relatifs.

II Division euclidienne

Soit a un entier relatif et b un entier naturel non nul.

Théorème : Il existe un unique couple q;r d’entiers relatifs tels que :

a=bq+r et 0r<b.

Définitions : a est le dividende, b est le diviseur, q est le quotient, r est le reste dans la division euclidienne de a par b.

III Congruences

Définition : Soit a et b deux entiers relatifs et n un entier naturel non nul. On dit que a et b sont congrus modulo n lorsque a et b ont le même reste dans la division euclidienne par n. On note ab n.

Propriétés : Soit a, a, b, b et c des entiers relatifs et n un entier naturel non nul.

a et b sont congrus modulo n si et seulement si ba est divisible par n.

Si ab n et bc n, alors ac n.

Si ab n et ab n, alors a+ab+b n et aabb n.

Si ab n alors, pour tout entier relatif c, a+cb+c n.

Si ab n alors, pour tout entier naturel non nul p, apbp n.

Méthodes

1 Construire et utiliser un tableau de congruences

Pour tout entier relatif n, on pose gn=n23n+6.

On veut déterminer les entiers n tels que gn soit divisible par 5.

a. Étudier suivant le reste de n dans la division euclidienne par 5 (on dit « reste de n modulo 5 ») le reste de gn modulo 5. Consigner les résultats dans un tableau.

b. Conclure à l’aide du tableau de la question précédente.

Conseils

a. Utilisez les propriétés des congruences.

b. Utilisez l’équivalence « gn est divisible par 5gn0 5 ».

Solution

a. On peut dresser le tableau suivant.

Tableau de 2 lignes, 6 colonnes ;Corps du tableau de 2 lignes ;Ligne 1 : Reste de n modulo 5; 0; 1; 2; 3; 4; Ligne 2 : Reste de g(n) modulo 5; 1; 4; 4; 1; 0;

Remarque : On dit qu’on raisonne par disjonction des cas : on considère de manière exhaustive tous les cas possibles.

Par exemple : si n3 5, alors n23n+699+6 5, donc gn6 5, donc gn1 5.

On raisonne de la même manière pour les autres cas.

b. D’après le tableau précédent, on constate que gn0 5 si et seulement si n4 5. Les entiers n tels que gn soit divisible par 5 sont les entiers n de la forme 4 + 5k, avec k entier.

2 Montrer une divisibilité à l’aide de congruences

Montrer que, pour tout entier naturel n, 52n14n est divisible par 11.

Conseils

Utilisez des congruences modulo 11.

Solution

52=25, donc 523 1125=11×2+3, donc, pour tout entier naturel n, 52n3n 11 (1).

14=11+3, donc 143 11, donc 14n3n 11 (2).

Des relations (1) et (2) on déduit, par soustraction, que, pour tout entier naturel n, 52n14n0 11, ce qui signifie que 52n14n est divisible par 11.

Annabac est gratuit en septembre !

Inscris-toi pour en profiter.