144
45
1 re année
Arithmétique dans Z
1. Divisibilité dans Z
1.1 Division euclidienne
Pour tout (a,b) ∈ Z × N
∗ , il existe un élément unique (q,r) ∈ Z × N tel que :
a = bq + r
avec 0 r < b.
q est le quotient et r le reste de la division euclidienne de a par b.
1.2 Divisibilité
Si (a,b) ∈ Z × Z, on dit que b divise a si, et seulement si, il existe q ∈ Z tel que
a = bq.
On dit que a est un multiple de b, ou que b est un diviseur de a.
La relation de divisibilité est une relation d'ordre partiel dans N.
1.3 Nombres premiers
Un entier p est premier si p 2, et si ses seuls diviseurs sont 1 et p.
Il y a une infinité de nombres premiers.
Si n n'est divisible par aucun nombre premier inférieur ou égal à
√
n, alors il est
premier.
Tout entier n, avec n 2, s'écrit de façon unique comme produit de nombres
premiers.
1.4 Idéaux de Z
Les idéaux de Z sont de la forme nZ avec n ∈ N.
2. pgcd et ppcm
2.1 pgcd
• Définition
Soit a et b deux entiers relatifs non nuls. L'ensemble des nombres de N
∗ qui divisent à la fois a et b, admet un plus grand élément d, pour la relation d'ordre de
divisibilité.
9782100549245-fredon-C37-51.qxd 18/06/10 10:33 Page 144