Critère de divisibilité. (Rappel)

Un entier est divisible par 2 si le dernier chiffre est pair.

Un entier est divisible par 3 si la somme des chiffres qui le composent est divisble par 3.

Un entier est divisible par 4 si le nombre formé par les deux derniers chiffres est un multiple de 4.

Un entier est divisible par 5 si le dernier chiffre est 0 ou 5.

Un entier est divisible par 6 si il est divisible par 2 et par 3.

Un entier est divisible par 9 si la somme des chiffres qui le composent est un multiple de 9.

Un entier est divisible par 10 si le dernier chiffre est 0.

Un entier est divisible par 11 si la différence entre la somme des chiffres de rangs pairs et la somme des chifffres de rangs impairs est un multiple de 11.

Un entier est divisible par 7 si son nombre de dizaines moins deux fois le chiffre à la position des unités est divisible par 7.
Exemple : Vérifier que 1183 est divisible par 7.
On sépare le chiffre des unités 118 | 3 puis on effectue le calcul 118 - 3×2 = 112 = 7×16.
Sinon, on peut recommencer avec ce dernier nombre. 11 | 2 et 11 - 2×2 = 7. En effet, 1183 = 7×169.

Division euclidienne d'un élément de ℤ par un élément de ℕ*

Effectuer un division euclidienne de a par b, revient à trouver un couple unique (q ; r) tel que
a = q×b + r avec 0 ≤ r < b ( r doit être positif et strictement inférieur à b)
q est appelé quotient et r le reste. (a est le dividende et b le divisuer)

Exemple 1 : Ecrire la division euclidienne de 65 par 7.
En déduire la division euclidienne de -65 par 7, de 65 par -7 et celle de -65 par -7.
On a 7×9 = 63 donc 65 = 9×7 + 2
On peut écrire -65 = -9×7 - 2 = -10×7 + 7 -2 = -10×7 + 5 (le reste doit être positif)
On peut écrire 65 = -9×(-7) + 2
On peut écrire -65 = 10×(-7) + 5
remarque : 2 < 9, donc 65 = 9×7 + 2 correspond également à la division euclidienne de 65 par 9.

Exemple 2 : Soit n un entier naturel.
Montrer que n2 +3n -5 = Ecrire la division euclidienne de 65 par 7.
En déduire la division euclidienne de -65 par 7, de 65 par -7 et celle de -65 par -7.
On a 7×9 = 63 donc 65 = 9×7 + 2
On peut écrire -65 = -9×7 - 2 = -10×7 + 7 -2 = -10×7 + 5 (le reste doit être positif)
On peut écrire 65 = -9×(-7) + 2
On peut écrire -65 = 10×(-7) + 5
remarque : 2 < 9, donc 65 = 9×7 + 2 correspond également à la division euclidienne de 65 par 9.

Congruences dans ℤ.

Dans ℤ, un nombre a est congru à un nombre b modulo un entier naturel n non nul si et seulement si il existe un entier relatif k tel que a - b = k×n. En d'autre terme si n divise la différence a - b, ou si a - b est un multiple de n.
On dit également que a et b sont congrus modulo n. On note a ≡ b [n]

Remarque : Si n divise la différence a - b alors n divise la différence b - a.
Ainsi si a ≡ b [n] alors b ≡ a [n].

Propriètés : Si a est divisible par n alors a ≡ 0 [n].

Pour tout entier a - a = 0 et 0 est un multiple de tout entier naturel n. Par conséquent a ≡ a [n].

La division euclidienne de a par n conduit à a = k×n + r avec 0 ≤ r < n et k ∈ ℤ.
On peut donc écrire a ≡ r [n]

Si a - b = k×n et b - c = k'×n alors a - c = (k +k')×n. En terme de congruence cela donne :
Si a ≡ b [n] et b ≡ c [n] alors a ≡ c [n]

Compatibilité des congruences avec les opérations.

On considére les entiers relatifs a, b, c et d et un entier naturel non nul n.

L'addition est compatible avec les congruences:

Si a ≡ b [n] alors a + c ≡ b + c [n]
Si a ≡ b [n] et alors c ≡ d [n] alors a + c ≡ b + d [n]

La multiplication est compatible avec les congruences:

Si a ≡ b [n] alors a × c ≡ b × c [n]
Si a ≡ b [n] et alors c ≡ d [n] alors a × c ≡ b × d [n]
Si c = a et d = b, cette dernière propriété conduit à : a² ≡ b² [n], et ainsi de suite...
Par conséquent, pour tout entier naturel non nul p, Si a ≡ b [n] alors a^p ≡ b^p [n]
Les congruences sont compatibles avec les puissances. On peut le démontrer par récurrence...

Remarque : La division n'est pas compatible avec les congruences.
En effet, 80 - 44 = 36 = 6×6 donc 80 ≡ 44 [6] Or 80 = 4×20 et 44 = 4×11.
Toutefois, 20 - 11 = 9 et 9 n'est pas multiple de 6. Par conséquent 20 ≢ 11 [6].

Divisibilité par 7 : 1 ≡ 1 [7], 10 ≡ 3 [7], 10² ≡ 3² [7] soit 100 ≡ 2 [7].
Un nombre décimal à 3 chiffres peut s'écrire : a + b×10 + c×100. Il est congru à : a + 3b + 2c modulo 7.
Si le nombre ainsi obtenu est un multiple de 7, le nombre sera divisible par 7.
On peut continuer avec les puissances de 10 supérieures : 10³ ≡ -1 [7], 10⁴ = -3 [7], , 10⁵ = -2 [7],
10⁶ = 1 [7], 10³ = 3 [7], ...