Arithmétique

À retenir. $a=bq+r$ avec $0\leq r<b$ (le reste est toujours positif, même si $a<0$). $d\mid a$ et $d\mid b$ $\Rightarrow$ $d\mid(au+bv)$.

À retenir. $a\equiv b\,[n]$ si $n\mid a-b$. Compatibilité avec $+$, $\times$ et les puissances. Pour $a^k\bmod n$, chercher la période des restes.

À retenir. Algorithme d’Euclide : $\text{pgcd}(a,b)=\text{pgcd}(b,r)$. Bézout : $\text{pgcd}(a,b)=1\iff\exists u,v,\ au+bv=1$. Gauss : $a\mid bc$ et $\text{pgcd}(a,b)=1$ $\Rightarrow$ $a\mid c$.

À retenir. Décomposition $n=p_1^{a_1}\cdots p_k^{a_k}$ ; nombre de diviseurs : $(a_1+1)\cdots(a_k+1)$. Petit théorème de Fermat : $p$ premier ne divisant pas $a$ $\Rightarrow$ $a^{p-1}\equiv1\,[p]$.