7. PGCD dans Z Flashcards
**
Plan
I. PGCD dans Z
1. PGCD dans N
Exemple d’illustration PGCD Dans N Tansmaths Seconde, des carreaux dans la Salle de bain.
2. Outils nécessaires à la démonstration de l’existence et l’unicité
a. D(a;b)=D(b;r)
b. Algorithme d’Euclide (Algo Python)
c. Les diviseurs communs de a et b sont les diviseurs de PGCD(a;b)
3. PGCD dans Z
II. Propriétés du PGCD
1. Identité de Bezout
2. Homogénéité du PGCD
3. PGCD et decomposition en produits de facteurs premiers
III. Nombre premiers entre eux
1. Définition
2. Théorème de Bezout
3. Théorème de Gauss
IV. Applications
1. Simplification de fractions (mise sous forme irréductible) + sqrt(5) est irrationnel
2. Résolution d’équations diophantiennes
3. Inversible modulo n et Cryptage affine
Intro
Le PGCD est utilisé dès le collège pour la simplification de fractions
En arithmétique il va être utile pour résoudre des problèmes à l’aide de la notion de nombre premiers entre eux
Définition du PGCD dans N
Il existe un plus grand élément aux diviseurs commun de (a et b) (ensemble de N majoré par Max(a,b) )
Outils nécessaires à la démonstration de l’existence et l’unicité
a. D(a;b)=D(b;r)
b. Algorithme d’Euclide
c. Les diviseurs communs de a et b sont les diviseurs de PGCD(a;b)
Lien entre PGCD et PPCM
a. Si a et b premiers PPCM(a;b)=|ab|
b. PPCM(a;b)*PGCD(a;b)=|ab|
Algorithme d’Euclide aboutit ? et preuve que le dernier reste non nul est le PGCD(a;b)
suite des (rn) strictement décroissante majorée par b
on remonte pour finalement obtenir D(Rn-1) = D(a;b)
Identité de Bezout
commencer avec a et b entiers
(sous ensemble des au+bv=n)…
Homogénéité du PGCD
on raisonne dans N , on remonte l’Algorithme d’Euclide en multipliant toutes les égalités par K puis on revient à Z
Théorème de Bezout
Les diviseurs de a et b divisent 1 donc PGCD(a;b) divise 1…
Theoreme de Gauss et corollaire
au+bv=1 <=> acu+bcv=c
revenir à la definition
Homogénéité du PPCM
double relation de division => egalité en valeur absolue
PPCM(a;b)xPGCD(a;b)=|ab|
prouver d’abord si a et b premiers entre eux PPCM(a;b)=|ab|grace au théorème de Gauss
pui poser d= PGCD(a;b) a’=a/d; b’=b/d….
