Arithmétique et congruences

📋 Plan du Cours

1. Division euclidienne et congruences
2. Écriture en bases de numération

📖 1. Division euclidienne et congruences

🔑 Notions clés & Définitions

• Division euclidienne : Associe de manière unique des entiers q et r tels que $a=bq+r$ et $0\le r<b$.
• Congruence modulo n : Pour un entier n supérieur ou égal à 2, deux entiers a et b sont congruents modulo n lorsqu'ils ont le même reste dans la division euclidienne par n, ce qui équivaut à dire que n divise a−b.

★ À maîtriser

📐 Formule — La congruence modulo n vérifie $a\equiv b\pmod n\Longleftrightarrow n\mid(a-b)$.

• La congruence modulo n est une relation d'équivalence, car elle est réflexive, symétrique et transitive.

📌 Si a est congru à b modulo n et c est congru à d modulo n, alors a+c est congru à b+d modulo n, a×c est congru à b×d modulo n et, pour tout k naturel, a^k est congru à b^k modulo n.

Compléments

📌 Tout entier a est congru à son reste r dans la division euclidienne par n, avec $0\le r<n$.

💡 Astuce mémo

Division : quotient et reste ; congruence : même reste ou différence divisible

📖 2. Écriture en bases de numération

🔑 Notions clés & Définitions

• Écriture en base b : Tout entier N s'écrit de manière unique en base b, pour 2≤b≤10, sous la forme $N=a_kb^k+a_{k-1}b^{k-1}+\cdots+a_1b+a_0=\overline{a_ka_{k-1}\ldots a_1a_0}^{(b)}$.