Divisibilité dans Z

La divisibilité c'est comme demander "est-ce que ce nombre rentre parfaitement dans un autre ?" On dit que a divise b (noté a|b) quand il existe un entier k tel que b = ak.

Quelques règles importantes à retenir : 1 et -1 divisent tous les nombres (ils sont les diviseurs universels). Le zéro est divisible par tout nombre non nul, mais il ne divise que lui-même.

Pour tout nombre n non nul, ses diviseurs sont toujours compris entre -|n| et |n|. Ça veut dire qu'un nombre a forcément un nombre fini de diviseurs ! La divisibilité se transmet aussi : si a divise b et b divise c, alors a divise c automatiquement.

💡 Astuce pratique : Si a divise b et a divise c, alors a divise aussi toute combinaison linéaire kb + lc (où k et l sont des entiers).

Division euclidienne

La division euclidienne te donne une façon précise de diviser deux nombres entiers. Quand tu divises 23 par 4, tu obtiens 5 avec un reste de 3, car 23 = 4×5 + 3.

Le théorème fondamental dit que pour deux entiers a et b (avec b ≠ 0), il existe toujours un unique couple (q,r) tel que a = bq + r avec 0 ≤ r < |b|. Le q c'est le quotient et le r c'est le reste.

Cette division fonctionne même avec des nombres négatifs, il faut juste faire attention à garder le reste positif et plus petit que la valeur absolue du diviseur.

Congruences

Les congruences te permettent de travailler avec les restes de façon élégante. On dit que a est congru à b modulo n (noté a ≡ b [n]) quand a et b ont le même reste dans la division par n.

Par exemple, 17 ≡ 5 [3] parce que 17 et 5 donnent tous les deux un reste de 2 quand on les divise par 3. Autre façon de voir : a ≡ b [n] signifie que $a-b$ est un multiple de n.

Les congruences se comportent comme des égalités : elles sont réflexives (a ≡ a [n]), symétriques et transitives. Tu peux aussi faire des calculs avec : si a ≡ b [n] et c ≡ d [n], alors a+c ≡ b+d [n], a-c ≡ b-d [n] et ac ≡ bd [n].

💡 Méthode rapide : Pour trouver a [n], calcule simplement le reste de la division euclidienne de a par n !

Cette propriété est géniale pour simplifier les calculs avec de gros nombres en gardant seulement les restes !