Arithmétique

 

ILa divisibilité

ALes diviseurs

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 :
\[a = kb\]

Les propositions suivantes sont équivalentes :

  • \(\displaystyle{a}\) est divisible par \(\displaystyle{b}\) ;
  • \(\displaystyle{b}\) est un diviseur de \(\displaystyle{a}\) ;
  • \(\displaystyle{b}\) divise \(\displaystyle{a}\).
  • 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 cominaison linéaire de \(\displaystyle{a}\) et de \(\displaystyle{b}\) : \(\displaystyle{ka + k'b}\), avec \(\displaystyle{k}\) et \(\displaystyle{k'}\) entiers relatifs.
\(\displaystyle{4}\) divise \(\displaystyle{16}\) et \(\displaystyle{24}\), donc \(\displaystyle{4}\) divise \(\displaystyle{71 \times 16 - 13 \times 24}\).

BLes multiples

L'entier \(\displaystyle{a}\) est un multiple de \(\displaystyle{b}\) si et seulement si \(\displaystyle{b}\) est un diviseur de \(\displaystyle{a}\).
\(\displaystyle{81}\) est un multiple de \(\displaystyle{9}\), et \(\displaystyle{9}\) est un diviseur de \(\displaystyle{81}\).
  • 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).

CLa 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{(q ; r)}\) tel que :

\(\displaystyle{a = bq + r}\) et \(\displaystyle{0 \leqslant 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}\).
La division euclidienne de \(\displaystyle{103}\) par \(\displaystyle{12}\) est : \(\displaystyle{103 = 12 \times 8 + 7}\)

Dans cet exemple, \(\displaystyle{q = 8}\) et \(\displaystyle{r = 7}\).

DLe PGCD

Le plus grand diviseur commun de \(\displaystyle{a}\) et de \(\displaystyle{b}\), noté PGCD(\(\displaystyle{a ; b}\)), est le plus grand entier naturel qui divise à la fois \(\displaystyle{a}\) et \(\displaystyle{b}\).

On veut déterminer le PGCD(\(\displaystyle{ 12;30 }\)).

On recherche les diviseurs communs à \(\displaystyle{12}\) et \(\displaystyle{30}\) :

  • Les diviseurs de \(\displaystyle{12}\) sont : \(\displaystyle{\color{Red}{1}}\), \(\displaystyle{\color{Red}{2}}\), \(\displaystyle{\color{Red}{3}}\), \(\displaystyle{4}\), \(\displaystyle{\color{Red}{6}}\), \(\displaystyle{12}\)
  • Les diviseurs de \(\displaystyle{30}\) sont : \(\displaystyle{\color{Red}{1}}\), \(\displaystyle{\color{Red}{2}}\), \(\displaystyle{\color{Red}{3}}\), \(\displaystyle{5}\), \(\displaystyle{\color{Red}{6}}\), \(\displaystyle{10}\), \(\displaystyle{15}\), \(\displaystyle{30}\)

Les diviseurs communs à \(\displaystyle{12}\) et \(\displaystyle{30}\) sont donc les nombres : \(\displaystyle{1}\), \(\displaystyle{2}\), \(\displaystyle{3}\) et \(\displaystyle{6}\).

Parmi ceux-ci le plus grand étant \(\displaystyle{6}\), on en déduit que PGCD(\(\displaystyle{ 12;30 }\)) \(\displaystyle{= 6}\).

Pour déterminer le PGCD de deux nombres, on peut procéder par divisions euclidiennes successives, d'après l'algorithme d'Euclide.
Soit \(\displaystyle{d}\) = PGCD(\(\displaystyle{a ; b}\)).
Il existe alors deux entiers \(\displaystyle{a'}\) et \(\displaystyle{b'}\) tels que :
\(\displaystyle{a = da'}\) et \(\displaystyle{b = db'}\)
Soit \(\displaystyle{d}\) = PGCD(\(\displaystyle{a ; b}\)).
L'ensemble des diviseurs communs à \(\displaystyle{a}\) et \(\displaystyle{b}\) est l'ensemble des diviseurs de \(\displaystyle{d}\).

IILes nombres premiers

ALa définition

Un entier naturel est premier si et seulement s'il admet exactement deux diviseurs positifs : \(\displaystyle{1}\) et lui-même.
L'entier \(\displaystyle{1}\) n'admet qu'un seul diviseur positif (\(\displaystyle{1}\)), il n'est donc pas premier.
Il existe une infinité de nombres premiers.
Tout entier supérieur ou égal à \(\displaystyle{2}\) admet au moins un diviseur premier.
Si \(\displaystyle{a}\) n'est pas premier, il admet alors au moins un diviseur premier \(\displaystyle{p}\) tel que :
\[2 \leqslant p \leqslant \sqrt{a} \]

BLa décomposition

Soient \(\displaystyle{a}\) un entier naturel supérieur ou égal à \(\displaystyle{2}\), \(\displaystyle{(p_{1}, p_{2},..., p_{r})}\) des nombres premiers deux à deux distincts, \(\displaystyle{(\alpha_{1}, \alpha_{2},..., \alpha_{r})}\) des entiers naturels non nuls.
On peut décomposer \(\displaystyle{a}\) comme un unique produit de facteurs premiers :
\[a = p_{1}^{\alpha_{1}} \times p_{2}^{\alpha_{2}} \times... \times p_{r}^{\alpha_{r}}\]
On décompose le nombre \(\displaystyle{60}\) sous la forme d'un produit de facteurs premiers :

\(\displaystyle{60 = 6 \times 10}\)

\(\displaystyle{60 = 2 \times 3 \times 2 \times 5}\)

\(\displaystyle{60 = 2^2 \times 3 \times 5}\)

Les entiers \(\displaystyle{2}\), \(\displaystyle{3}\) et \(\displaystyle{5}\) sont bien premiers.

CLes nombres premiers entre eux

Deux entiers sont premiers entre eux si et seulement si leur seul diviseur positif commun est \(\displaystyle{1}\).
Les nombres \(\displaystyle{15}\) et \(\displaystyle{28}\) n'ayant pas d'autre diviseur commun que \(\displaystyle{1}\), ils sont premiers entre eux.
D'après le théorème de Bezout, les entiers \(\displaystyle{a}\) et \(\displaystyle{b}\) sont premiers entre eux si et seulement s'il existe des entiers \(\displaystyle{u}\) et \(\displaystyle{v}\) tels que :
\[ua + vb = 1\]
Soient \(\displaystyle{a}\), \(\displaystyle{b}\) et \(\displaystyle{c}\) trois entiers.
D'après le théorème de Gauss, si \(\displaystyle{c}\) divise \(\displaystyle{ab}\) et \(\displaystyle{c}\) premier avec \(\displaystyle{a}\), alors \(\displaystyle{c}\) divise \(\displaystyle{b}\).

IIILes congruences

ALa caractérisation

Soient \(\displaystyle{a}\) et \(\displaystyle{b}\) deux entiers et \(\displaystyle{n}\) un entier naturel supérieur ou égal à \(\displaystyle{2}\).
On dit que \(\displaystyle{a}\) est congru à \(\displaystyle{b}\) modulo \(\displaystyle{n}\), noté \(\displaystyle{a \equiv b [n]}\), si et seulement si :
\(\displaystyle{a - b}\) est multiple de \(\displaystyle{n}\)
On peut écrire que \(\displaystyle{51 \equiv 27 [6]}\) car \(\displaystyle{51-27 = 24}\) et \(\displaystyle{24}\) est multiple de \(\displaystyle{6}\).
On peut également écrire \(\displaystyle{51 \equiv 27 [4]}\), \(\displaystyle{51 \equiv 27 [2]}\), \(\displaystyle{51 \equiv 27 [24]}\)...
\(\displaystyle{a \equiv b [n] \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 à \(\displaystyle{2}\)) si et seulement si \(\displaystyle{a \equiv 0 [b]}\).

BLes opérations

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

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

ImprimerE-mail

Statistiques

Visiteurs
165
Articles
1392
Compteur d'affichages des articles
7309411