7. PGCD dans Z Flashcards

1
Q

**

Plan

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Intro

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Définition du PGCD dans N

A

Il existe un plus grand élément aux diviseurs commun de (a et b) (ensemble de N majoré par Max(a,b) )

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Outils nécessaires à la démonstration de l’existence et l’unicité

A

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)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Lien entre PGCD et PPCM

A

a. Si a et b premiers PPCM(a;b)=|ab|
b. PPCM(a;b)*PGCD(a;b)=|ab|

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Algorithme d’Euclide aboutit ? et preuve que le dernier reste non nul est le PGCD(a;b)

A

suite des (rn) strictement décroissante majorée par b
on remonte pour finalement obtenir D(Rn-1) = D(a;b)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Identité de Bezout

A

commencer avec a et b entiers
(sous ensemble des au+bv=n)…

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Homogénéité du PGCD

A

on raisonne dans N , on remonte l’Algorithme d’Euclide en multipliant toutes les égalités par K puis on revient à Z

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Théorème de Bezout

A

Les diviseurs de a et b divisent 1 donc PGCD(a;b) divise 1…

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Theoreme de Gauss et corollaire

A

au+bv=1 <=> acu+bcv=c
revenir à la definition

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Homogénéité du PPCM

A

double relation de division => egalité en valeur absolue

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

PPCM(a;b)xPGCD(a;b)=|ab|

A

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….

How well did you know this?
1
Not at all
2
3
4
5
Perfectly