$$\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

Résumé de cours : Arithmétique

Division euclidienne
  • Soient $a$ et $b$ deux entiers relatifs. On dit que $a$ divise $b$, ou que a est un diviseur de $b$ s'il existe $k\in\mathbb Z$ tel que $b=ka$. On dit encore que $b$ est un multiple de $a$.
  • Théorème (division euclidienne) : Soient $(a,b)\in\mathbb Z^2$ avec $b\neq 0$. Il existe un unique couple $(q,r)\in\mathbb Z^2$ tels que $$\left\{ \begin{array}{l} a=bq+r\\ 0\leq r< |b|. \end{array} \right. $$ $q$ s'appelle le quotient et $r$ s'appelle le reste.
pgcd,ppcm
  • Si $a$ et $b$ sont deux entiers relatifs dont l'un au moins est non-nul, alors le pgcd de $a$ et $b$, noté $a\wedge b$, est le plus grand diviseur commun de $a$ et $b$. Cette définition se généralise à plus de deux entiers, en supposant toujours qu'au moins un est non-nul.
  • Si $a=b=0$, on pose $a\wedge b=0$.
  • On a $(d|a\textrm{ et }d|b)\iff d|a\wedge b$.
  • Si $a,b,k\in (\mathbb Z\backslash\{0\})^3$, alors $(ka)\wedge (kb)=|k|(a\wedge b)$.
  • Algorithme d'Euclide :Si $r$ est le reste dans la division euclidienne de $a$ par $b$, alors on a $$a\wedge b=b\wedge r.$$ On en déduit l'algorithme suivant pour calculer le pgcd pour $a\geq b\geq 0$. On pose $r_0=a$ et $r_1=b$. Pour $i\in\mathbb N^*$, si $r_i\neq 0$, on note $r_{i+1}$ le reste de la division euclidienne de $r_{i-1}$ par $r_i$. Le dernier reste non nul est le pgcd de $a$ et $b$.
  • Si $a$ et $b$ sont deux entiers relatifs, le ppcm de $a$ et $b$, noté $a\vee b$, est le plus petit multiple commun positif de $a$ et $b$.
  • Proposition : Pour tout couple d'entiers relatifs $(a,b)$, on a $$|ab|=(a\wedge b)(a\vee b).$$
Nombres premiers entre eux
  • On dit que deux entiers relatifs sont premiers entre eux si leur pgcd vaut 1.
  • Théorème de Bézout : Soient $(a,b)\in\mathbb Z^2$. On a $$a\wedge b=1\iff \exists (u,v)\in\mathbb Z^2,\ au+bv=1.$$
  • Théorème de Gauss : Soient $(a,b,c)\in\mathbb Z^3$. On suppose que $a|bc$ et $a\wedge b=1$, alors $a|c$.
  • Conséquence : Si $b|a$, $c|a$ et $b\wedge c=1$, alors $bc|a$.
Nombres premiers
  • Un entier $p\geq 2$ est dit premier si ses seuls diviseurs positifs sont $1$ et $p$.
  • L'ensemble des nombres premiers est infini.
  • Théorème fondamental de l'arithmétique : Tout entier $n\geq 2$ s'écrit de manière unique $n=p_1^{\alpha_1}\cdots p_r^{\alpha_r}$ où $p_1<p_2<\dots<p_r$ sont des nombres premiers et $\alpha_1,\dots,\alpha_k$ sont dans $\mathbb N^*$. On dit que $n=p_1^{\alpha_1}\cdots p_r^{\alpha_r}$ est la décomposition en produit de facteurs premiers de $n$.
  • Si $n\geq 2$ et $p$ est un nombre premier, on appelle valuation $p$-adique de $n$, et on note $v_p(n)$, le plus grand entier $k\geq 0$ tel que $p^k|n$. La valuation $p$-adique de $n$ est l'exposant de $p$ dans la décomposition en produit de facteurs premiers de $n$.
  • Application au calcul du pgcd et du ppcm : si $a,b\geq 2$ se décomposent sous la forme $$a=p_1^{\alpha_1}\cdots p_r^{\alpha_r}$$ $$b=p_1^{\beta_1}\cdots p_r^{\beta_r}$$ où les $p_i$ sont des nombres premiers et $\alpha_i,\beta_i\in\mathbb N$, alors \begin{eqnarray*} a\wedge b&=&p_1^{\min(\alpha_1,\beta_1)}\cdots p_r^{\min(\alpha_r,\beta_r)}\\ a\vee b&=&p_1^{\max(\alpha_1,\beta_1)}\cdots p_r^{\max(\alpha_r,\beta_r)}. \end{eqnarray*}
Congruences
  • Soient $a$ et $b$ deux entiers relatifs et $n$ un entier naturel. On dit que $a$ et $b$ sont congrus modulo n s'il existe $k\in\mathbb Z$ tel que $a-b=kn$. On note $$a\equiv b\ [n].$$
  • La relation "être congrue modulo $n$", qui est une relation d'équivalence, est compatible avec les opérations $+,\times$ : $$\left\{ \begin{array}l a\equiv b\ [n]\\ c\equiv d\ [n] \end{array} \right. \implies \left\{ \begin{array}l a+c\equiv b+d\ [n]\\ a\times c\equiv b\times d\ [n] \end{array}\right. $$
  • Petit théorème de Fermat : Si $p$ est un nombre premier et $a\in \mathbb Z$, alors $a^{p}\equiv a\ [p]$. De plus, si $p$ ne divise pas $a$, alors $a^{p-1}\equiv 1\ [p]$.