Arithmétique/divisibilité et congruences dans Z

Multiples d'un entier relatif

Définition

L'entier relatif http://upload.wikimedia.org/math/d/a/f/daf78f2fbe9d3f724c6c3b93f516103b.png">[*]B)\,[*]plus généralement, http://upload.wikimedia.org/math/2/d/9/2d9d5071f91b280ce2f47f2b1b535fc5.png">B)c+b(c-d)=qnc+qB)n\," src="http://upload.wikimedia.org/math/c/3/7/c37aa565d6a8969d5cecac81b038a83a.png">.Par conséquent $ac-bd\,$ est divisible par $n \,$ .Donc $ac \equiv bd [n]$

(3) On utilise l'égalité suivante:B)(a^{p-1}+a^{p-2}b+ ... +a^{p-k}b^{k}+ ... +b^{p-1})\," src="http://upload.wikimedia.org/math/d/a/8/da89ec04020dd77ea8b6fd7a248eb13d.png"> pour $a\,$ et $b\,$ quelconques et $p \in \mathbb{N}$ Il suffit pour démontrer celle-ci de développer le membre de droite;après simplification on obtient bien le membre de gauche de l'égalité.Puisque $a \equiv b[n]$ , $a-b \,$ est un multiple de $n\,$ . Le membre de droite de l'égalité ci-dessus est par conséquent un multiple de $n\,$ comme multiple de $a-b\,$ .On a montré que $a^{p} - b^{p}\,$ est un multiple de $n\,$ .Donc $a^p \equiv b^p[n]$ .Autre démonstration. On applique la propriété (2) $p\,$ fois avec $c=a\,$ et $d=b\,$ .

Exemple de congruence

Quel est le reste de la division de $2^{16}\,$ par 7 ? $2 \equiv 2[7] \Rightarrow 2^3 \equiv 8[7] \Rightarrow 2^3 \equiv 1[7]$ $16 = 3\times 5+1 \Rightarrow 2^{16} = 2^{3\times 5+1} = (2^3)^5 \times 2$ Or $(2^3)^5 \equiv 1^5[7] \Leftrightarrow (2^3)^5 \equiv 1[7]$ et $2 \equiv 2[7]$ En multipliant membre à membre : $(2^3)^5\times 2 \equiv 1\times 2[7] \Leftrightarrow 2^{16} \equiv 2[7]$ Le reste de la division de $2^{16}\,$ par 7 est donc 2.