coursenligne1s6 site de cours en ligne première terminale et bac Coursenligne1s6.fr, fiches de révision pour lycéens de première, terminale & bac

Coursenligne1s6: 1er site de cours & révision en ligne fait pour des lycéens par des lycéens (2012)

Problème de chiffrement |cours de spé maths terminale

logo cours en ligne 1s6 site de cours en ligne pour première

Cours et code réalisé par Vincent Maffet

I PGCD de deux entiers

1) Diviseurs communs à deux entiers naturels

a) définition

Soit a et b deux entiers naturels non nuls. Le plus grand diviseur commun à a et b est appelé PGCD de a et b. On le note PGCD(a;b)

b) PGCD et decomposition en produit de facteurs premiers

Théorème :

Le PGCD(a;b) est égal au produit des facteurs premiers communs aux décompositions de a et de b, chacun d'eux étant affecté du plus petit exposant avec lequel il figure dans les décompositions de a et de b.

c) Proposition fondamentale

Proposition :

Soit deux entiers naturels a et b tels que a>b et r le reste de la division euclidienne de a par b

- Si r=0 alors les diviseurs communs à a et b sont les diviseurs de b et PGCD(a;b)=b

- si r≠0 alors les diviseurs communs à a et b sont les diviseurs communs à b et r et PGCD(a;b)=PGCD(b;r)

Démonstration :

- Si r=o alors b divise a soit d un diviseur commun à a et b, alors d divise b

Réciproquement, si d divise b, comme b divise a, d divise a et d est un diviseur commun à a et b

Conclusion, les diviseurs communs à a et b sont les diviseurs de b et PGCD(a;b)=b

- Si r≠0 alors a=bq+r avec 0<r<b

Soit d un diviseur commun à a et b, alors d divise a-bq, c'est à dire d divise r et d est donc un diviseur commun à b et r

2) Calcul du PGCD de deux entiers naturels non nuls : Algorithme d'Euclide

Soit a et b deux entiers naturels non nuls avec a>b

Opération Reste  Commentaire
On divise a par b  r0  0≤r0<b et PGCD(a;b)=PGCD(b;r0)
Si r0≠0, on divise b par r0  r1  0≤r1<r0 et PGCD(b;r0)=PGCD(r0;r1)
Si r1≠0, on divise r0 par r1 r2 0≤r2<r1 et PGCD(r0;r1)=PGCD(r1;r2)
|  |  |
Si rn≠0, on divise rn-1 par rn  0  PGCD(rn-1;rn)=rn

Après un nombre fini de diviseurs, on obtient un reste nul car les restes sont des entiers positifs qui vont en décroissant strictement :

0<rn<rn+1<...<r2<r1<r0

PGCD(a;b)=PGCD(b;r0)=PGCD(r0;r1)=...=PGCD(rn-1;rn)=rn, rn étant le dernier reste non nul

Propriété :

Lorsque b ne divise pas a, le PGCD des entiers naturels non nuls a et b est égal au dernier reste non nul obtenu par l'algorithme d'Euclide

Algorithme d'Euclide

Cf. page algorithme

Propriété :

Les diviseurs communs à deux entiers naturels non nuls a et b sont les diviseurs du PGCD(a;b)

Démonstration

d divise a et b ⇔ d divise b et r0

d divise b et r0 ⇔ d divise r0 et r1

|

d divise rn et rn-1 ⇔ d divise rn car rn divise rn-1

3) Propriété du PGCD

Propriété :

Soit a ∈ N*, b ∈ N* et k ∈ N*

PGCD(ka;kb)=k*PGCD(a;b)

Démonstration :

a=bq+r0 avec 0≤r0<b

Alors ka=kbq+kr0 avec 0≤kr0<kb

kr0 est le reste de la division euclidienne de ka par kb d'après l'unicité de l'écriture,

PGCD(ka;kb)=PGCD(kb;kr0)=PGCD(kr0;kr1)=...=krn=PGCD(a;b)*k

4) Extension du PGCD aux entiers relatifs

Définition :

Soit a et b deux entiers relatifs non nuls

PGCD(a;b)=PGCD(|a|;|b|)

Remarques :

- Pour tout k ∈ Z*, PGCD(ka;kb)=|k|PGCD(a;b)

- LEs diviseurs communs à a et b sont les diviseurs du PGCD(a;b)

5) Nombres premiers entre eux

définition :

Dire que deux entiers relatifs non nuls a et b sont premiers entre eux signifie PGCD(a;b)=1

Propriété :

Soit a et b deux entiers relatifs non nuls

Si d=PGCD(a;b) alors il existe 2 entiers relatifs a' et b' premiers entre eux tels que a=da' et b=db'

Démonstration (exigible) :

d divise a donc il existe un entier relatif a' tel que a=da'

d divise b donc il existe un entier relatif b' tel que b=db'

d=PGCD(da';db')=d*PGCD(a';b')

d>0 donc PGCD(a';b')=1

-

Partagez ce cours !

Suivez Vincent Maffet sur google + ( cours inspiré de celui fait par le professeur de la classe)