Arithmétique Fiche bac

Sommaire

IDivisibilitéIINombres premiersIIICongruencesIVPGCD, théorème de Bézout et théorème de GaussAPGCDBAlgorithme d'EuclideCThéorème de BézoutDThéorème de Gauss
I

Divisibilité

Entier divisible

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

a = kb

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

Multiple d'un entier

L'entier a est un multiple de b si et seulement si b est un diviseur de a.

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

Division euclidienne

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

a = bq + r et 0 \leq r \lt |b|

  • L'entier q est le quotient de la division euclidienne de a par b.
  • L'entier r est le reste de la division euclidienne de a par b.
II

Nombres premiers

Nombre premier

Un entier naturel est dit premier lorsqu'il admet exactement deux diviseurs dans \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 a n'est pas premier, il admet alors au moins un diviseur premier p tel que :

2 \leq p \leq \sqrt{a}

Pour n\geq 2, si n n'admet aucun diviseur premier inférieur ou égal à \sqrt n, alors 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 p premier et p ne divise pas a, alors a et p sont premiers entre eux.

Divisibilité par un nombre premier

Si p est premier et divise ab , alors p divise a ou p divise b .

Si, en plus, a et b sont premiers, alors p=a ou p=b .

Décomposition en produit de facteurs premiers

Tout entier n supérieur ou égal à 2 s'écrit de façon unique sous la forme :

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

p_1,p_2,\cdot\cdot\cdot,p_m sont des nombres premiers tels que p_1\lt p_2 \lt \cdot\cdot\cdot\lt p_m et \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 a et b deux entiers relatifs quelconques et n un entier naturel supérieur ou égal à 2.
On dit que a est congru à b modulo n, noté a \equiv b \left[n\right], si et seulement si : a - b est multiple de n.

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

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

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

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

Soient a, b et k des entiers relatifs et n un entier supérieur ou égal à 2.

Si a\equiv b\left[n\right], alors ka\equiv kb\left[n\right].

IV

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

A

PGCD

PGCD\left(a;b\right)

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

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

Soient deux entiers relatifs a et b, avec a\neq0.

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

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

Soient des entiers naturels non nuls a, b et k.

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

Soient a et b deux entiers naturels non nuls.

D est le PGCD de a et b si et seulement si \dfrac{a}{D} et \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 : a=bq_0+r_0, avec 0\leq r_0 \lt b
  • Étape 2 : On divise b par r_0 : b=r_0q_1+r_1, avec 0\leq r_1 \lt r_0
  • Étape 3 : On divise r_0 par r_1 : r_0=r_1q_2+r_2, avec 0\leq r_2 \lt r_1
  • Étape \left(n+2\right) : On divise r_{n-1} par r_n : r_{n-1}=r_nq_{n+1}+0

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

Déterminons PGCD (1632;538).

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

Le dernier reste non nul est 2.

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

C

Théorème de Bézout

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

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

Théorème de Bézout

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

au + bv = 1

D

Théorème de Gauss

Théorème de Gauss

Soient a, b et c trois entiers non nuls.
Si a divise bc et a premier avec b, alors a divise c.