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

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=bq₀+r₀ ; b=q₁r₀+r₁ ; r₀=q₂r₁+r₂; ..... ; r_n-1=q_nr_n avec 0<r_n<r_n-1<...<r₀<b

On obtient alors : - a-bq₀=r₀=au₀+bv₀ avec u₀=1 et v₀=q₀

b-r₀q₁=r₁=b-(a-bq₀)q₁ soit -aq₁+b(1+q₁q₀)=r₁=au₁+bv₁ avec u₁=-q₁ et v₁=1+q₁q₀

|

Ainsi de suite, on montre que les restes r_k avec 0<k≤n, s'écrivent sous la forme r_k=au_k+bv_k où u_k et v_k s'écrivent en fonction de q₀, q₁, ..., q_n et en particulier le dernier reste r_n 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)