Devenir Premium
Se connecter
ou

Arithmétique Fiche bac

I

Divisibilité

Entier divisible

Soient \(\displaystyle{a}\) et \(\displaystyle{b}\) deux entiers relatifs, avec \(\displaystyle{b}\) non nul.
L'entier \(\displaystyle{a}\) est divisible par \(\displaystyle{b}\) si et seulement s'il existe un entier relatif \(\displaystyle{k}\) tel que :

\(\displaystyle{a = kb}\)

  • Si \(\displaystyle{b}\) divise \(\displaystyle{a}\), alors \(\displaystyle{- b}\) divise \(\displaystyle{a}\).
  • Si \(\displaystyle{d}\) divise les entiers \(\displaystyle{a}\) et \(\displaystyle{b}\), il divise alors toute combinaison linéaire de \(\displaystyle{a}\) et de \(\displaystyle{b}\) : \(\displaystyle{ka + k'b}\), avec \(\displaystyle{k}\) et \(\displaystyle{k'}\) entiers relatifs.

Multiple d'un entier

L'entier \(\displaystyle{a}\) est un multiple de \(\displaystyle{b}\) si et seulement si \(\displaystyle{b}\) est un diviseur de \(\displaystyle{a}\).

  • Si \(\displaystyle{a}\) est un multiple de \(\displaystyle{b}\), alors \(\displaystyle{- a}\) est un multiple de \(\displaystyle{b}\).
  • La somme et / ou la différence de multiples de \(\displaystyle{b}\) est un multiple de \(\displaystyle{b}\).
  • Si \(\displaystyle{a}\) est un multiple de \(\displaystyle{b}\), alors \(\displaystyle{ka}\) est un multiple de \(\displaystyle{b}\) ( \(\displaystyle{k}\) entier relatif).

Division euclidienne

Soient \(\displaystyle{a}\) et \(\displaystyle{b}\) deux entiers relatifs, avec \(\displaystyle{b}\) non nul.
Il existe un unique couple d'entiers relatifs \(\displaystyle{\left(q ; r\right)}\) tel que :

\(\displaystyle{a = bq + r}\) et \(\displaystyle{0 \leq r \lt |b|}\)

  • L'entier \(\displaystyle{q}\) est le quotient de la division euclidienne de \(\displaystyle{a}\) par \(\displaystyle{b}\).
  • L'entier \(\displaystyle{r}\) est le reste de la division euclidienne de \(\displaystyle{a}\) par \(\displaystyle{b}\).
II

Nombres premiers

Nombre premier

Un entier naturel est dit premier lorsqu'il admet exactement deux diviseurs dans \(\displaystyle{\mathbb{N}}\) : 1 et lui-même.

Infinité des nombres premiers

Il existe une infinité de nombres premiers.

Nombre de diviseurs

Tout entier supérieur ou égal à 2 admet au moins un diviseur premier.

Diviseur premier

Si \(\displaystyle{a}\) n'est pas premier, il admet alors au moins un diviseur premier \(\displaystyle{p}\) tel que :

\(\displaystyle{2 \leq p \leq \sqrt{a}}\)

Pour \(\displaystyle{n\geq 2}\), si \(\displaystyle{n}\) n'admet aucun diviseur premier inférieur ou égal à \(\displaystyle{\sqrt n}\), alors \(\displaystyle{n}\) est premier.

Nombres premiers entre eux

Deux entiers sont premiers entre eux si et seulement si leur seul diviseur positif commun est 1.

Si \(\displaystyle{p}\) premier et \(\displaystyle{p}\) ne divise pas \(\displaystyle{a}\), alors \(\displaystyle{a}\) et \(\displaystyle{p}\) sont premiers entre eux.

Divisibilité par un nombre premier

Si \(\displaystyle{p}\) est premier et divise \(\displaystyle{ab}\) , alors \(\displaystyle{p}\) divise \(\displaystyle{a}\) ou \(\displaystyle{p}\) divise \(\displaystyle{b}\) .

Si, en plus, \(\displaystyle{a}\) et \(\displaystyle{b}\) sont premiers, alors \(\displaystyle{p=a}\) ou \(\displaystyle{p=b}\) .

Décomposition en produit de facteurs premiers

Tout entier \(\displaystyle{n}\) supérieur ou égal à 2 s'écrit de façon unique sous la forme :

\(\displaystyle{n=p_1^{\alpha_1}\times p_2^{\alpha_2}\times \cdot\cdot\cdot \times p_m^{\alpha_m}}\),

\(\displaystyle{p_1,p_2,\cdot\cdot\cdot,p_m}\) sont des nombres premiers tels que \(\displaystyle{p_1\lt p_2 \lt \cdot\cdot\cdot\lt p_m}\) et \(\displaystyle{\alpha_1,\alpha_2,\cdot\cdot\cdot,\alpha_m}\) des entiers naturels non nuls.

Cette écriture est la décomposition en produit de facteurs premiers.

III

Congruences

Congruence

Soient \(\displaystyle{a}\) et \(\displaystyle{b}\) deux entiers relatifs quelconques et \(\displaystyle{n}\) un entier naturel supérieur ou égal à 2.
On dit que \(\displaystyle{a}\) est congru à \(\displaystyle{b}\) modulo \(\displaystyle{n}\), noté \(\displaystyle{a \equiv b \left[n\right]}\), si et seulement si : \(\displaystyle{a - b}\) est multiple de \(\displaystyle{n}\).

\(\displaystyle{a \equiv b \left[n\right] \Leftrightarrow a}\) et \(\displaystyle{b}\) ont le même reste dans la division euclidienne par \(\displaystyle{n}\).

L'entier \(\displaystyle{a}\) est divisible par \(\displaystyle{b}\) (supérieur ou égal à 2) si et seulement si \(\displaystyle{a \equiv 0 \left[b\right]}\).

Soient \(\displaystyle{n}\) un entier naturel supérieur ou égal à 2, \(\displaystyle{a}\), \(\displaystyle{a'}\), \(\displaystyle{b}\) et \(\displaystyle{b'}\) des entiers relatifs tels que \(\displaystyle{a \equiv a' \left[n\right]}\) et \(\displaystyle{b \equiv b' \left[n\right]}\), alors :

  • \(\displaystyle{a + b \equiv a' + b' \left[n\right]}\)
  • \(\displaystyle{a - b \equiv a' - b' \left[n\right]}\)
  • \(\displaystyle{ab \equiv a'b' \left[n\right]}\)
  • \(\displaystyle{a^{k} \equiv a'^{k} \left[n\right]}\) ( \(\displaystyle{k}\) entier naturel non nul)

Soient \(\displaystyle{a}\), \(\displaystyle{b}\) et \(\displaystyle{k}\) des entiers relatifs et \(\displaystyle{n}\) un entier supérieur ou égal à 2.

Si \(\displaystyle{a\equiv b\left[n\right]}\), alors \(\displaystyle{ka\equiv kb\left[n\right]}\).

IV

PGCD, théorème de Bézout et théorème de Gauss

A

PGCD

\(\displaystyle{PGCD\left(a;b\right)}\)

Soient \(\displaystyle{a}\) et \(\displaystyle{b}\) deux entiers relatifs dont l'un au moins est non nul. L'ensemble des diviseurs communs à \(\displaystyle{a}\) et \(\displaystyle{b}\) admet un plus grand élément, que l'on appelle le plus grand diviseur commun à \(\displaystyle{a}\) et \(\displaystyle{b}\) que l'on note \(\displaystyle{PGCD\left(a;b\right)}\).

\(\displaystyle{PGCD\left(a;b\right)=1}\) si et seulement si \(\displaystyle{a}\) et \(\displaystyle{b}\) sont premiers entre eux.

Soient deux entiers relatifs \(\displaystyle{a}\) et \(\displaystyle{b}\), avec \(\displaystyle{a\neq0}\).

  • \(\displaystyle{PGCD\left(a;0\right)=a}\)
  • \(\displaystyle{PGCD\left(a;1\right)=1}\)
  • \(\displaystyle{PGCD\left(a;b\right)=PGCD\left(\left| a \right|;\left| b \right|\right)}\)
  • Si \(\displaystyle{b}\) divise \(\displaystyle{a}\), alors \(\displaystyle{PGCD\left(a;b\right)=\left| b \right|}\) .
  • Si \(\displaystyle{b}\) est premier et ne divise pas \(\displaystyle{a}\) , alors \(\displaystyle{PGCD\left(a;b\right)=1}\) .

Soient deux entiers naturels non nuls \(\displaystyle{a}\) et \(\displaystyle{b}\) dont le PGCD est \(\displaystyle{D}\). L'ensemble des diviseurs communs à \(\displaystyle{a}\) et \(\displaystyle{b}\) est l'ensemble des diviseurs de \(\displaystyle{D}\).

Soient des entiers naturels non nuls \(\displaystyle{a}\), \(\displaystyle{b}\) et \(\displaystyle{k}\).

\(\displaystyle{PGCD\left(ka;kb\right)=k\times PGCD \left(a;b\right)}\)

Soient \(\displaystyle{a}\) et \(\displaystyle{b}\) deux entiers naturels non nuls.

\(\displaystyle{D}\) est le PGCD de \(\displaystyle{a}\) et \(\displaystyle{b}\) si et seulement si \(\displaystyle{\dfrac{a}{D}}\) et \(\displaystyle{\dfrac{b}{D}}\) sont des entiers premiers entre eux.

B

Algorithme d'Euclide

Algorithme d'Euclide

Soient a et b deux entiers naturels non nuls tels que b ne divise pas a.

La suite des divisions euclidiennes suivantes s'arrête au bout d'un certain nombre d'étapes :

  • Étape 1 : On divise a par b : \(\displaystyle{a=bq_0+r_0}\), avec \(\displaystyle{0\leq r_0 \lt b}\)
  • Étape 2 : On divise b par \(\displaystyle{r_0}\) : \(\displaystyle{b=r_0q_1+r_1}\), avec \(\displaystyle{0\leq r_1 \lt r_0}\)
  • Étape 3 : On divise \(\displaystyle{r_0}\) par \(\displaystyle{r_1}\) : \(\displaystyle{r_0=r_1q_2+r_2}\), avec \(\displaystyle{0\leq r_2 \lt r_1}\)
  • Étape \(\displaystyle{\left(n+2\right)}\) : On divise \(\displaystyle{r_{n-1}}\) par \(\displaystyle{r_n}\) : \(\displaystyle{r_{n-1}=r_nq_{n+1}+0}\)

On a alors : \(\displaystyle{PGCD\left(a;b\right)=r_n}\)

Déterminons PGCD (1632;538).

  • Étape 1 : On divise 1632 par 538 : \(\displaystyle{1\ 632=3\times 538+18}\)
  • Étape 2 : On divise 538 par 18 : \(\displaystyle{538=29\times 18+16}\)
  • Étape 3 : On divise 18 par 16 : \(\displaystyle{18=1\times 16+2}\)
  • Étape 4 : On divise 16 par 2 : \(\displaystyle{16=8\times 2+0}\)

Le dernier reste non nul est 2.

Ainsi, \(\displaystyle{PGCD\left(1\ 632;538\right)=2}\).

C

Théorème de Bézout

Soient \(\displaystyle{a}\) et \(\displaystyle{b}\) deux entiers relatifs non nuls, et \(\displaystyle{D}\) leur PGCD. Alors, il existe des entiers relatifs \(\displaystyle{u}\) et \(\displaystyle{v}\) tels que \(\displaystyle{au+bv=D}\).

En remontant les étapes de l'algorithme d'Euclide appliqué à deux entiers naturels a et b, on détermine un couple \(\displaystyle{\left(u;v\right)}\) tel que \(\displaystyle{au+bv=D}\).

Théorème de Bézout

Deux entiers relatifs \(\displaystyle{a}\) et \(\displaystyle{b}\) sont premiers entre eux si et seulement s'il existe des entiers \(\displaystyle{u}\) et \(\displaystyle{v}\) (entiers relatifs) tels que :

\(\displaystyle{au + bv = 1}\)

D

Théorème de Gauss

Théorème de Gauss

Soient \(\displaystyle{a}\), \(\displaystyle{b}\) et \(\displaystyle{c}\) trois entiers non nuls.
Si \(\displaystyle{a}\) divise \(\displaystyle{bc}\) et \(\displaystyle{a}\) premier avec \(\displaystyle{b}\), alors \(\displaystyle{a}\) divise \(\displaystyle{c}\).