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

Démonstrations capes - Arithmétique

Division euclidienne dans $\mathbb N
Soient $a$ et $b$ deux entiers naturels avec $b\neq 0$. Alors il existe un unique couple d'entiers $(q,r)$ tel que $a=bq+r$ et $0\leq r<b$.

Division euclidienne dans $\mathbb Z$
Soient $a$ et $b$ deux entiers relatifs avec $b\neq 0$. Alors il existe un unique couple d'entiers $(q,r)$ avec $a=bq+r$ et $0\leq r<|b|$.

Algorithme d'Euclide
Soient $a$ et $b$ deux entiers avec $b$ non-nul et soit $r$ le reste dans la division euclidienne de $a$ par $b$. Alors $\text{pgcd}(a,b)=\text{pgcd}(b,r).$

Égalité de Bézout
Soit $a,b$ deux entiers dont l'un est non-nul et $d$ leur pgcd. Alors il existe $u,v\in\mathbb Z$ tels que $au+bv=d$.

Théorème de Bézout
Deux entiers $a$ et $b$ sont premiers entre eux si et seulement s'il existe deux entiers $u$ et $v$ tels que $au+bv=1$.

Lemme de Gauss
Soit $a,b,c$ des entiers tels que $a|bc$ et $a\wedge b=1$. Alors $a|c$.

Critères de divisibilité
Un entier $n$ est
  • divisible par 3 si et seulement si la somme de ses chiffres est divisible par 3;
  • divisible par 5 si et seulement si son chiffre des unités est 0 ou 5;
  • divisible par 9 si et seulement si la somme de ses chiffres est divisible par 9;
  • divisible par 11 si et seulement si la somme de ses chiffres d'ordre impair moins la somme de ses chiffres d'ordre pair est divisible par 11.

Irrationnalité de $\sqrt 2$
$\sqrt 2$ est irrationnel.

Critère de non-primalité
Un entier $n\geq 2$ n'est pas premier si et seulement s'il admet un diviseur premier inférieur ou égal à $\sqrt n$.

Théorème d'Euclide
L'ensemble des nombres premiers est infini.

Décomposition en produits de facteurs premiers
Soit $n\geq 2$ un entier. Alors $n$ s'écrit de manière unique, à l'ordre des termes près, $p_1^{\alpha_1}\dots p_r^{\alpha_r}$ où les $p_i$ sont des nombres premiers distincts et les $\alpha_i$ sont des éléments de $\mathbb N\backslash\{0\}$.

pgcd et divisibilité
Soit $a,b$ deux entiers naturels. Alors $\textrm{pgcd}(a,b)=b\iff b|a$.

pgcd et décomposition en produits de facteurs premiers
Soit $a,b$ deux entiers naturels non nuls dont les décompositions en produits de facteurs premiers sont respectivement $$a=p_1^{\alpha_1}\cdots p_r^{\alpha_r}\textrm{ et }b=p_1^{\beta_1}\cdots p_r^{\beta_r}.$$ Alors $$\textrm{pgcd}(a,b)=p_1^{\delta_1}\cdots p_r^{\delta_r}$$ où pour tout $i=1,\dots,r$, $\delta_i=\min(\alpha_i,\beta_i)$.

Homogénéité du pgcd
Soit $a,b,k$ des entiers non nuls. Alors $\textrm{pgcd}(ka,kb)=k\textrm{pgcd}(a,b)$.

pgcd et nombres premiers entre eux
Soit $a$ et $b$ des entiers non-nuls et $\delta$ un diviseur commun à $a$ et $b$. Alors $\textrm{pgcd(a,b)}=\delta$ si et seulement si $\frac a\delta$ et $\frac b\delta$ sont premiers entre eux.

Deux définitions de la congruence
Soit $a,b\in\mathbb Z$ et $n\in\mathbb N$ non nul. Alors $n|a-b$ si et seulement si $a$ et $b$ ont même reste dans la division euclidienne par $n$.

La relation "être congru" est une relation d'équivalence
Soit $m\geq 1$ et $a,b,c\in\mathbb Z$. Alors
  • $a\equiv a\ [m]$;
  • Si $a\equiv b\ [m]$, on a $b\equiv a\ [m]$;
  • Si $a\equiv b\ [m]$ et $b\equiv c\ [m]$, alors $a\equiv c\ [m]$.

Compatibilité de la congruence et des opérations algébriques
Soit $m\geq 1$ et $a,b,a',b'\in\mathbb Z$ tels que $a\equiv a'\ [m]$ et $b\equiv b'\ [m]$. Alors $a+b\equiv a'+b'\ [m]$ et $ab\equiv a'b'\ [m]$.

Le petit théorème de Fermat
Soit $p$ un nombre premier et $1\leq a\leq p-1$. Alors $p$ divise $a^{p-1}-1$.

Théorème des restes chinois
Soit $m$ et $n$ des entiers premiers entre eux. Alors, pour tout $(a,b)\in\mathbb Z^2$, le système $$\left\{ \begin{array}{rcl} x&\equiv&a\ [m]\\ x&\equiv&b\ [n] \end{array}\right.$$ admet au moins une solution. De plus, si $x_0$ est une solution particulière, l'ensemble des solutions est $\{x_0+kmn;\ k\in\mathbb Z\}.$