THE MATHS TAILOR

PGCD et nombres premiers | The Maths Tailor

PGCD et nombres premiers

Cours Exercices

Cours

1PGCD de deux entiers

2Théorème de Bézout et théorème de Gauss

Contenu réservé aux abonnés

3Nombres premiers

Contenu réservé aux abonnés

Méthodes12p.1/2

PavlovPGCD de deux entiers : définition et propriétés

Soit $a$ et $b$ deux entiers naturels non tous deux nuls. Le $P GC D$ de $a$ et $b$ , noté $P GC D (a; b)$ , est le plus grand diviseur commun à $a$ et $b$ . On retient trois propriétés immédiates : $P GC D (a; 0) = a$ (pour $a \neq = 0$ ) ; $P GC D (a; 1) = 1$ ; et si $b$ divise $a$ alors $P GC D (a; b) = b$ . Pour des entiers relatifs $a$ et $b$ non tous deux nuls, on pose $P GC D (a; b) = P GC D (∣ a ∣; ∣ b ∣)$ .

Pourquoi ça marche

Démonstration : Tout entier divise $0$ , donc l'ensemble des diviseurs communs à $a$ et $0$ est l'ensemble des diviseurs de $a$ ; son plus grand élément est $a$ , d'où $P GC D (a; 0) = a$ . Le seul diviseur positif de $1$ est $1$ lui-même, donc $P GC D (a; 1) = 1$ . Enfin, si $b$ divise $a$ , tout diviseur de $b$ divise aussi $a$ (transitivité de la divisibilité) : l'ensemble des diviseurs communs à $a$ et $b$ est donc exactement l'ensemble des diviseurs de $b$ , dont le plus grand est $b$ . Ainsi $P GC D (a; b) = b$ .

TunnelThéorème d'Euclide : PGCD et division euclidienne

Méthode complète avec le plan Élève

Voir les offres

ClassiqueCalculer un PGCD par l'algorithme d'Euclide

Méthode complète avec le plan Élève

Voir les offres

PavlovDiviseurs communs et homogénéité du PGCD

Méthode complète avec le plan Élève

Voir les offres

TunnelIdentité de Bézout

Méthode complète avec le plan Élève

Voir les offres

TunnelThéorème de Bézout : caractérisation des entiers premiers entre eux

Méthode complète avec le plan Élève

Voir les offres

ClassiqueDémontrer que deux entiers sont premiers entre eux

Méthode complète avec le plan Élève

Voir les offres

ClassiqueDéterminer un inverse modulo n et résoudre une congruence linéaire

Méthode complète avec le plan Élève

Voir les offres

TunnelThéorème de Gauss et son corollaire

Méthode complète avec le plan Élève

Voir les offres

ClassiqueRésoudre une équation diophantienne ax + by = c

Méthode complète avec le plan Élève

Voir les offres

1 / 2

Exercices

Exercice

Soient

a

et

b

deux entiers naturels non nuls. On pose

d = pgcd (a, b)

,

a = d α

et

b = d β

.

1. Montrer que

pgcd (α, β) = 1

.
2. Montrer que

pgcd (α + β, α β) = 1

, puis que

pgcd (a + b, ab) = d pgcd (α + β, d)

.
3. Application : calculer

pgcd (35, 150)

.

Découper deux rubans sans chute

Une couturière dispose de deux rubans mesurant

460

cm et

320

cm. Elle veut découper les deux rubans en morceaux tous de même longueur, la plus grande possible, sans aucune chute. Quelle longueur de morceau doit-elle choisir, et combien de morceaux obtiendra-t-elle ?

Pourquoi l'algorithme d'Euclide calcule le PGCD

Soient

a

et

b

deux entiers avec

b > 0

, et soit

r

le reste de la division euclidienne de

a

par

b

:

a = b q + r

avec

0 ⩽ r < b

. Démontrer que le PGCD de

a

et

b

est égal au PGCD de

b

et

r

. En déduire une justification de l'algorithme d'Euclide : montrer que le dernier reste non nul obtenu par les divisions successives est bien le PGCD de

a

et

b

.

Une propriété du PGCD : soustraire un multiple

(1) Soient

a

et

b

deux entiers non nuls et

k

un entier relatif. Démontrer que

PGCD (a, b) = PGCD (a, b - k a)

.
(2) Application : déterminer, pour tout entier naturel

n

, le PGCD de

5 n + 3

et

3 n + 2

.

Démontrer que $PGCD (a, b) = PGCD (a, b - k a)$ pour des entiers $a$ et $b$ non nuls et un entier relatif $k$
En déduire, pour tout entier naturel $n$ , le PGCD de $5 n + 3$ et $3 n + 2$