$$\newcommand{\mtn}{\mathbb{N}}\newcommand{\mtns}{\mathbb{N}^*}\newcommand{\mtz}{\mathbb{Z}}\newcommand{\mtr}{\mathbb{R}}\newcommand{\mtk}{\mathbb{K}}\newcommand{\mtq}{\mathbb{Q}}\newcommand{\mtc}{\mathbb{C}}\newcommand{\mch}{\mathcal{H}}\newcommand{\mcp}{\mathcal{P}}\newcommand{\mcb}{\mathcal{B}}\newcommand{\mcl}{\mathcal{L}} \newcommand{\mcm}{\mathcal{M}}\newcommand{\mcc}{\mathcal{C}} \newcommand{\mcmn}{\mathcal{M}}\newcommand{\mcmnr}{\mathcal{M}_n(\mtr)} \newcommand{\mcmnk}{\mathcal{M}_n(\mtk)}\newcommand{\mcsn}{\mathcal{S}_n} \newcommand{\mcs}{\mathcal{S}}\newcommand{\mcd}{\mathcal{D}} \newcommand{\mcsns}{\mathcal{S}_n^{++}}\newcommand{\glnk}{GL_n(\mtk)} \newcommand{\mnr}{\mathcal{M}_n(\mtr)}\DeclareMathOperator{\ch}{ch} \DeclareMathOperator{\sh}{sh}\DeclareMathOperator{\th}{th} \DeclareMathOperator{\vect}{vect}\DeclareMathOperator{\card}{card} \DeclareMathOperator{\comat}{comat}\DeclareMathOperator{\imv}{Im} \DeclareMathOperator{\rang}{rg}\DeclareMathOperator{\Fr}{Fr} \DeclareMathOperator{\diam}{diam}\DeclareMathOperator{\supp}{supp} \newcommand{\veps}{\varepsilon}\newcommand{\mcu}{\mathcal{U}} \newcommand{\mcun}{\mcu_n}\newcommand{\dis}{\displaystyle} \newcommand{\croouv}{[\![}\newcommand{\crofer}{]\!]} \newcommand{\rab}{\mathcal{R}(a,b)}\newcommand{\pss}[2]{\langle #1,#2\rangle} $$
Bibm@th

Arithmétique modulaire

  Il est commode en arithmétique de considérer les entiers modulo m. Deux entiers a et b sont égaux (ou congrus) modulo m si a-b est un multiple de m. On note a=b mod m, et Z/mZ l'ensemble {0,...,m-1} : tout entier est égal modulo m à un unique élément de Z/mZ (son reste dans la division euclidienne par m).

  Les calculs usuels (addition, multiplication, puissance) peuvent être réalisés modulo m, exactement comme avec les entiers. Il suffit ensuite de réduire le résultat modulo m. On peut aussi remplacer tous les résultats intermédiaires par leur reste modulo m. Pour calculer 14×(7+2)15 modulo 8, on remarque que 7+2=9=1 modulo 8, d'où (7+2)15=1 modulo 8, et 14×(7+2)15=14=6 mod 8.

  L'utilisation des congruences est d'emploi plus courant qu'il n'y parait : s'il est 11H, dans 2H, il est 1H, car 11+2=13=1 mod 12!