image/svg+xml
La division euclidienne
Si a et b sont deux nombres entiers non nuls tels que Alors il existe deux nombres q et r vérifiant :Cette égalité correspond à la division euclidienne de a par b. b est le diviseur, q est le quotient et r le reste.
PGCD
Deux nombres entiers non nuls ont toujours au moins un diviseurcommun : le nombre 1.On appelle PGCD de deux nombres entiers non nuls le plus granddiviseur commun à ces deux nombres entiers.On le note PGCD(a;b)
Algorithme d'Euclide
Pour calculer le PGCD(a;b) où a>b- effectuer la division euclidienne de a par b;- si le reste est nul alors b est le PGCD- sinon on recommence la première étape en divisant le diviseur par le reste jusqu'à obtenir un reste nul. Le PGCD est alors le dernier reste non nul.
Algorithme des soustractions successives
Diviseurs et multiples
Si le reste de la division de a par b est nul, c'est à dire si il existe un entier q tel que Alors on dit que a est un multiple de b et b est un diviseur de a.
Nombres premiers
Un nombre entier supérieur à 1 ayant pour seuls diviseurs 1 et lui-même est un nombre premier.
Nombres premiers entre eux
Deux nombres entiers sont premiers entre eux si leur plus grand diviseurcommun est 1. Deux nombres sont premiers entre eux si et seulement si leur PGCD vaut 1Une fraction est irréductible si elle n'est pas simplifiable.Une fraction est irréductible si et seulement si son numérateur et son dénominateur sont premiers entre eux.
876
67
67
206
201
5
13
donc
12 est un diviseur de 156
13 est un diviseur de 156
156 est un multiple de 12
156 est un multiple de 13
Comparons les deux méthodes en calculant
Algorithme d'Euclide
Algorithme des soustractions
Donc
Arithmétique
Arithmétique