Exercices d'utilisation de la congruence.

Exercice 1 : Montrer que pour tout entier naturel non nul n, 3²ⁿ - 1 est divisible par 8.
3² = 9 = 1×8 + 1, donc 3² ≡ 1 [8] et par compatiblilité avec les puissances (3²)ⁿ ≡ 1ⁿ [8].
Soit encore 3²ⁿ ≡ 1 [8] et par compatibilités avec l'addition, 3²ⁿ - 1 ≡ 0 [8].
Par conséquent, 3²ⁿ - 1 est bien divisible par 8, ∀ n ∈ ℕ*.

Exercice 2 : Déterminer selon les valeurs de n entier naturel, le reste de la division de 3ⁿ par 5.
Dans ce genre d'exercice il faut tester avec les premiers entier et conjecturer le résultat. Ensuite, il faut démontrer cette conjecture...

n	0	1	2	3	4	5	6	...
reste	1	3	4	2	1	3	4	...
rmq	30 = 1	31 = 3	32 = 9 = 1×5+4	33 = 27 = 5×5+2	34 = 81 = 16×5+1	35 = 81×3 = 48×5+3	36 = 81×9 = 144×5+9	...

Si n = 4p, p ∈ ℕ ; 3^4p = (3⁴)^p = 81^p Or 81 ≡ 1 [5] donc 81^p ≡ 1^p [5] d'où 3^4p ≡ 1 [5]
Si n = 4p+1, p ∈ ℕ ; 3^4p+1 = 81^p×3 ... d'où 3^4p+1 ≡ 3 [5]
Si n = 4p+2, p ∈ ℕ ; 3^4p+2 = 81^p×9 Or ... et 9 ≡ 4 [5] d'où 3^4p+2 ≡ 4 [5]
Si n = 4p+3, p ∈ ℕ ; 3^4p+3 = 81^p×27 Or ... et 27 ≡ 2 [5] d'où 3^4p+3 ≡ 2 [5]

Raisonnement par disjonction de cas.

Pour démonstrer une propriété dépendant d'une variable x, on peut utiliser une disjonction de cas. C'est-à-dire étudier la propriété pour toutes les valeurs que peut prendre cette variable x.
Dans le cas de la congruence, on peut dresser un tableau de congruence. Par exemple, lorsqu'on veut étudier la divisibilté d'une variable dépend d'un entier n par un entier non nul p.

Exemple 1 : Montrer que pour tout entier relatif n, que le nombre N = n³ + 11n est divisible par 6.
Les restes possibles de la division euclidienne d'un entier relatif par 6 sont 0, 1, 2, 3, 4, 5.
De plus 11 ≡ -1 [6]. En utilisant la compatibilité des congruence avec l'addition et la multiplication, on peut dresser le tableau suivant :

n = ... [6]	0	1	2	3	4	5
11n = ... [6]	0	-1	-2	-3	-4	-5
n3 = ... [6]	0	1	2	3	4	5
n3 + 11n = ... [6]	0	0	0	0	0	0

2³ = 8 = 1×6 + 2 ; 3³ = 27 = 4×6 + 3 ; 4³ = 64 = 10×6 + 4 ; 5³ = 125 = 20×6 + 5 ;
Pour tout n, on obtient N ≡ 0 [6]. Donc n³ + 11n est bien divisible par 6, ∀ n ∈ ℤ .

PGCD de deux entiers.

On considère deux entiers naturels a et b non tous les deux nuls et leur ensemble de diviseurs respectivement D(a) et D(b).
L'ensembles des diviseurs communs de a et de b est noté D(a ; b). Cette ensemble est fini. Il adment un plus petit et un plus grand élement. Ce dernier noté PGCD(a;b) est appelé plus grand commun diviseur de a et de b.

Remarque : Les ensembles D(a) avec a ≠ 0 sont forcement non vides car 1 est un diviseur de tous les entiers.
1 ∈ D(a) et 1 ∈ D(b) donc 1 ∈ D(a ; b) et par conséquent PGCD(a;b) ≥ 1.
On peut écrire D(a ; b) = D(a) ∩ D(b). D(a ; b) ⊂ D(a) et D(a ; b) ⊂ D(b).

Exercice 1 : Donner la liste des diviseurs de 15 et de 6. En déduire D(6 ; 15) puis PGCD(6 ; 15). En se limitant aux entiers naturels, on a :
D(15) = {15, 5, 3, 1} et D(6) = {6 ; 3 ; 2 ; 1} donc D(6 ; 15) = {3 ; 1} et PGCD(6; 15) = 3.

Algorithme d'Euclide.

On considére deux entiers naturels a et b.
Si r désigne le reste de la division euclidienne de a par b alors D(a ; b)= D(b ; r).

En effet, si d est un élément de D(a ; b) alors d divise a et d divise b ainsi que toute combinaison linéaire de a et de b.
Or la division euclidienne de a par b s'écrit a = q×b + r avec (q; r) ∈ ℕ et 0 ≤ r < b.
On a donc r = a - q×b. Par conséquent d divise r. Comme d divise également b, d ∈ D(b ; r).
Inversement, si d est un élement de D(b ; r) alors d divise b et d divise r et par conséquent d divise a = q×b + r.
Ainsi d divise a et d divise b donc d ∈ D(a ; b).
On peut en conclure que D(b ; r) = D(a ; b).

En repétant les divisions euclidiennes, de a par b puis de b par r, ainsi de suite, le reste finit par être nul.
Le dernier reste non nul est le PGCD(a ; b).

Remarques : Dans ℤ un nombre et son opposé ont mêmes diviseurs donc PGCD(a ; b) = PGCD(∣a∣ ; ∣b∣).
Tout entier non nul divise 0 donc D(a, 0) = D(a) et par conséquent PGCD(a ; 0) = ∣a∣.

Exercice 2 : Déterminer le PGCD de 321 et 678.

678 = 2×321 + 36	678 = 2×107×3 + 12×3 = 226×3
321 = 8×36 + 33	321 = 8×12×3 + 11×3 = 107×3
36 = 1×33 + 3	36 = 11×3 + 3 = 12×3
33 = 11×3 + 0

Le dernier reste non nul est 3, donc PGCD( 321 ; 678) = 3.
En remontant l'algorithme, on peut exprimer tout les valeurs en fonction de 3 et en particulier 321 et 678.
(cf fraction irréductible...)