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

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 Théorème de Bezout

1) Identité de Bezout

Théorème :

Soit a et b deux entiers relatifs non nuls, tels que PGCD(a;b)=d. Alors il existe deux entiers relatifs u et v tels que au+bv=d

Démonstration :

Dans le cas où a>0 et b>0

- Si b divise a, PGCD(a;b)=b en prenant u=0 et v=1, au+bv=b

- Si a divise b, PGCD(a;b)=a en prenant u=1 et v=0, au+bv=a

- Dans les autres cas, en supposant 0<b<a par exemple, l'algorithme d'Euclide s'écrit : a=bq0+r0 ; b=q1r0+r1 ; r0=q2r1+r2; ..... ; rn-1=qnrn avec 0<rn<rn-1<...<r0<b

On obtient alors : - a-bq0=r0=au0+bv0 avec u0=1 et v0=q0

b-r0q1=r1=b-(a-bq0)q1 soit -aq1+b(1+q1q0)=r1=au1+bv1 avec u1=-q1 et v1=1+q1q0

|

Ainsi de suite, on montre que les restes rk avec 0<k≤n, s'écrivent sous la forme rk=auk+bvk où uk et vk s'écrivent en fonction de q0, q1, ..., qn et en particulier le dernier reste rn qui est le PGCD(a;b)

- Si a<0 et b>0 d=PGCD(-a;b)

- Si a>0 et b<0 d=PGCD(a;-b)

- Si a<0 et b<0 d=PGCD(-a;-b)

Remarque :

Le couple (u;v) n'est pas unique

2) Théorème de Bezout

Théorème (R.O.C.)

Soit a et b deux entiers relatifs non nuls, a et b sont premiers entre eux si et seulement S'il existe des entiers relatifs u et v tels que au+bv=1

Démonstration :

- Si a et b sont premiers entre eux, alors PGCD(a;b)=1, l'identité de Bezout permet alors de dire qu'il existe des entiers relatifs u et v tels que au+bv=1

- Réciproquement, s'il existe des entiers relatifs tels que au+bv=1 alors le PGCD(a;b) divise 1 [le PGCD(a;b) divise a et b donc divise au+bv]. Le PGCD(a;b) est un entier positif diviseur de 1, c'est donc 1. D'où a et b sont premiers entre eux.

Conséquence :

Propriété :

Soit a, b et c 3 entiers relatifs non nuls, si a est premier avec c alors PGCD(a;bc)=PGCD(a;b)

Démonstration :

Soit d∈N*

- Si d divise a et b, alors d divise a et bc

-Réciproquement, a et c sont premiers entre eux donc il existe des entiers relatifs u et v tels que au+cv=1

Alors aub+cvb=b, soit a(ub)+(bc)v=b

Donc si d divise a et bc donc d divise b et a

Les diviseurs communs à a et b sont les diviseurs communs à a et bc

Donc PGCD(a;b)=PGCD(a;bc)

-

Partagez ce cours !

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