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

Soit $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 élément, pour $\leq$, de l'ensemble des diviseurs communs de $a$ et $b$. Par convention, on pose $0\wedge 0=0$.

Théorème (algorithme d'Euclide) : Soit $a$ et $b$ deux entiers relatifs avec $b\neq 0$. Soit $r$ le reste dans la division euclidienne de $a$ par $b$. Alors $a\wedge b=b\wedge r$.

On en déduit l'algorithme suivant pour calculer $a\wedge b$ lorsque $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$. Tant qu'elle ne devient pas nulle, la suite $(r_i)$ est une suite strictement décroissante d'entiers naturels. Elle finit donc par s'annuler. Le dernier reste non nul est $a\wedge b$.

Proposition : Soit $a,b,d\in\mathbb Z$. On a $(d|a\textrm{ et }d|b)\iff d|a\wedge b$.

Autrement dit, l'ensemble des diviseurs communs de $a$ et de $b$ est égal à l'ensemble des diviseurs de leur pgcd $a\wedge b$.

Proposition (relation de Bézout) : Soit $a,b\in\mathbb Z$. Alors il existe $(u,v)\in\mathbb Z^2$ tel que $au+bv=a\wedge b$.
Proposition : Si $a,b,k\in (\mathbb Z\backslash\{0\})^3$, alors $(ka)\wedge (kb)=|k|(a\wedge 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$, au sens de $\leq$.

Proposition : Pour tout couple d'entiers relatifs $(a,b)$, on a $$|ab|=(a\wedge b)(a\vee b).$$

Comme un diviseur de $a$ et de $b$ est un diviseur de $a\wedge b$, un multiple de $a$ et $b$ est un multiple de $a\vee b$.

Théorème : Soit $a,b,m\in\mathbb Z$. Alors $m$ est un multiple commun de $a$ et de $b$ si et seulement si $m$ est un multiple de $a\vee b$.

Plus généralement, on peut définir le pgcd d'un nombre fini d'entiers $a_1,\dots,a_r$ dont l'un au moins est non-nul. Il s'agit du plus grand élément, pour $\leq$, de l'ensemble des diviseurs communs à $a_1,\dots,a_r$. On le note $a_1\wedge\cdots\wedge a_r$ et on étend la définition en posant $0\wedge \cdots\wedge 0=0$.

Comme précédemment, on peut prouver que :

  • l'ensemble des diviseurs communs à $a_1,\dots,a_r$ coïncide avec l'ensemble des diviseurs communs de leur pgcd $a_1\wedge\cdots\wedge a_r$;
  • pour tout $k\in\mathbb Z$, $$(ka_1)\wedge\cdots \wedge (ka_r)=|k|a_1\wedge\cdots\wedge a_r;$$
  • Il existe $(u_1,\dots,u_r)\in\mathbb Z^r,\ a_1u_1+\cdots+a_ru_r=a_1\wedge\cdots\wedge a_r.$
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 : Soit $(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 : Soit $(a,b,c)\in\mathbb Z^3$. On suppose que $a|bc$ et $a\wedge b=1$, alors $a|c$.
Corollaire : Soit $a,b,n\in\mathbb Z$.
  • Si $a|n$, $b|n$ et $a\wedge b=1$, alors $ab|n$.
  • Si $a\wedge n=1$ et si $b\wedge n=1$, alors $ab\wedge n=1$.

Le théorème de Gauss permet aussi de démontrer que tout rationnel $r\in\mathbb Q^*$ s'écrit de manière unique $r=\frac pq$ avec $p\in\mathbb Z$, $q\in\mathbb N^*$ et $p\wedge q=1$. Cette écriture s'appelle la forme irréductible de $r$.

Soit $a_1,\dots,a_r$ un nombre fini d'entiers. On dit qu'ils sont

  • premiers entre eux dans leur ensemble si leurs seuls diviseurs communs sont $1$ et $-1$, autrement dit si $a_1\wedge\cdots\wedge a_r=1$.
  • <premiers entre eux deux à deux si pour tous $i,j\in\{1,\dots,r\}$ avec $i\neq j$, $a_i\wedge a_j=1$.

Des nombres premiers entre eux deux à deux sont premiers dans leur ensemble, mais la réciproque est fausse. Par exemple, $6$, $10$ et $15$ sont premiers entre eux dans leur ensemble, mais $6\wedge 10=2$, $6\wedge 15=3$ et $10\wedge 15=5$.

Nombres premiers

Un entier $p\geq 2$ est dit premier si ses seuls diviseurs positifs sont $1$ et $p$.

Proposition : Soit $n\in\mathbb N$ tel que $n\geq 2$. Alors $n$ admet au moins un diviseur premier. De plus, si $n$ n'est pas premier, alors il admet un diviseur premier inférieur ou égal à $\sqrt n$.
Théorème : 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$.

Proposition : Soit $a,b\geq 2$ et $p$ un nombre premier. Alors $v_p(ab)=v_p(a)+v_p(b)$.

Application à la divisibilité, 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|b&\iff&\forall i\in\{1,\dots,r\},\ \alpha_i\leq \beta_i\\ 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]$.