3- مبرهنة بيزو Bézout ومبرهنة كوص Gauss

3.1 مبرهنة بيزو

3.1.1 متفاوتة بيزو

مبرهنة: ليكن (a;b)∈ℤ² حيث a.b≠0
a∧b=d ⇒ ∃(u;v)∈ℤ² / au+bv=d .

3.1.2 مبرهنة بيزو

ليكن (a;b)∈ℤ²
a∧b=1 ⇔ ∃(u;v)∈ℤ²: au+bv=1 .

برهان :

1) اذا كان a∧b=1 فان حسب مبرهنة بيزو ∃(u;v)∈ℤ²: au+bv=1 .
2) عكسيا : ∃(u;v)∈ℤ²: au+bv=1 .
نضع d=a∧b اذن d|a ∧ d|b ومنه فان d|au+bv,
وبما ان au+bv=1 فان d|1 اذن d=1 وبالتالي a∧b=1

تمرين 1

بين ان ∃(u;v)∈ℤ²/ 10u+15v=5

تصحيح

نضع: a=10=2.5 و b=15=3.5
10 ∧ 15 غير منعدمين معا و 10∧15=5
وحسب متفاوتة بيزو فان ∃(u;v)∈ℤ² : 10u+15v=5 .

تمرين 2

ليكن (a;b)∈ℤ² : 25a-18b=1
بين ان a∧b=1

تصحيح

25∧(-18)=1 حسب مبرهنة بيزو فان a∧b=1

3.2 مبرهنة كوص

3.2.1 lemme de Gauss

(a;b)∈ℤ*² ; c∈ℤ
a|bc و a∧b=1 ⇒a|c

برهان:

من جهة a|bc ⇔ ∃k∈ℤ ; bc=ka
ومن جهة اخرى بما ان a∧b=1 حسب مبرهنة بيزو فان
∃(u;v)∈ℤ²: au+bv=1

ومنه فان cau+cbv=c اي acu+kav=c اي a(cu+kv)=c
وبما ان cu+kv∈ℤ فان a|c

3.2.2 مثال :

8|240 ; 240=16.15 ; 8∧15=1 ⇒ 8|16

3.2.3. لازمة مبرهنة كوص

ليكن a عددا صحيحا و p و q عددين صحيحين وموجبين و p∧q=1
a≡0[p] و a≡0[q]يستلزم a≡0[pq]

برهان:

a≡0[p] ⇔ p|a
وايضا a≡0[q] ⇔ q|a
وبما ان p∧q=1 فان pq|a

3.3 lemme d'Euclide

ليكن p عددا اوليا و (a;b)∈ℤ²
لدينا p|a.b يستلزم p|a او p|b او يقسم الاثنين

مثال :

3|18 و 18=2.9 و 3 عدد اولي اذن 3|9

3.4 خاصيات

3.4.1 خاصية 1

ليكن (a;b)∈ℤ² ;(d;m)∈Z²
d=a∧b يكافئ d|a و d|b
a|m و b|m يكافئ m=a∨b

3.4.2 خاصية 2

ليكن (a;b)∈ℤ*² و k∈IN*
ka∧kb=k(a∧b) و ka∨kb=k(a∨b)

3.4.3 خاصية 3

ليكن (a;b)∈ℤ² و d∈IN* بحيث a=da' و b=db'
d=a∧b يكافئ a'∧b'=1

3.4.4 مثال:

a=105 و b=56
لدينا : 105=7.15 و 56=7.8 و 15∧8=1 اذن
105∧56=7(15∧8)=7

4- الحلول في Z²: معادلة (diophantienne): ax+by=c

4.1 مبرهنة

لتكن a;b;c∈ℤ و a∧b=d
اذا كان d|c فان المعادلة ax+by=c تقبل حلول في ℤ²

تمرين

1. بين ان (-7;14) حل خاص للمعادلة (E) 10x+6y=14
2. حدد مجموعة حلول المعادلة (E).

تصحيح

1) لدينا 10x+6y=14 ⇔ 5x+3y=7
وحسب خوارزمية اقليدس فان
5=1.3+2
3=1.2+1
2=1.2+0

اذن 5∧3=1 ونعلم ان 1 | 7 اذن حسب المبرهنة السابقة فان المعادلة تقبل على الاقل حلا واحدا في ℤ²
الآن نبحث عن حل خاص (p;q)
5=1.3+2
3=1.2+1
اذن 1=3-1.2=3-1.(5-1.3)=-5+2.3
اي 5.(-1)+3.2=1 اي 5.(-7)+3.14=7
اذن (-7;14) حل خاص للمعادلة
(2
5x+3y=7
5p+3q=7

وبطرح طرفي المعادلتين طرفا طرفا نحصل على
5(x+7)+3(y-14)=0
اي 3(y-14)=-5(x+7)
وبما ان 3∧5=1 فان 3|x+7
اي x+7=3k, k∈Z اي x=-7+3k, k∈Z
or 5x+3y=7 donc 5(-7+3k)+3y=7 اي 3y=7+35-15k اي 3y=42-15k اذن y=14-5k
ومنه فان S={(-7+3k;14-5k) ; k∈ℤ}
ملاحظة: نجد نفس النتيجة لو بدأنا ب 5|y-14.