1- القسمة الاقليدية والاعداد الاولية

1.1 القسمة الاقليدية في ℤ

1.1.1 تعريف

ليكن a و b عددين صحيحين نسبيين
يوجد زوج وحيد (q,r)∈ℤ×IN* بحيث b=aq+r
q يسمى الخارج والعدد a يسمى القاسم والعدد b المقسوم عليه والعدد r حيث 0 ≤r< a يسمى الباقي
والعملية التي تمكن من تحديد الزوج (q;r) تسمى القسمة الاقليدية ل b على a

1.1.2 امثلة

1) b=17 و a=5
17=5.3 + 2 اذن q=3 و r=2 حيث 0≤2< 5
2) b=-21 و a=7:
-21=7.(-3) + 0 اذن q=-3 و r=0 ,

ملاحظة

a يقسم b اذا كان r=0 ونكتب a|b

1.1.3 خاصيات

1) لتكن a;b∈ℤ
a|b يعني يوجد عدد نسبي t بحيث b=ta
بتعبير آخر
a|b ⇔ ∃t∈ℤ: b=ta

لتكن a;b;c∈ℤ
1) a|0
2) a|a
3) a|b و b|a⇔|a|=|b|
مثال
-3|3 و 3|-3
4) المتعدية
a|b و b|c⇒a|c
5)
a|b⇒a|bc
( العكس خاطئ 3|21 اي 3|7.3 لكن 3 لا يقسم 7)

1.1.4 خاصية

a|b و a|c ⇒ ∀(x;y)∈ℤ² : a|xb+yc

برهان:

a|b اذن b=ka حيث k∈Z و a|c اذن c=k'a حيث k'∈Z
ومنه فان xb+yc=xka+yk'a=a(xk+yk')
وبما ان xk+yk'∈Z فان a|xb+yc

1.1.5 خاصية

ac | b ⇒ a|b و c|b
∀ n∈IN*: aⁿ|b ⇒ a|b

1.2 الاعداد الاولية

1.2.1 تعريف

1) ليكن a∈ℤ
a عدد اولي اذا كان يقبل بالضبط اربعة قواسم مختلفة: -1 ; 1 ; a ; -a.
2) ليكن a∈IN
a عدد اولي اذا كان يقبل بالضبط قاسمين مختلفين 1 و a

1.2.2 مثال

1) قواسم الاعداد -7 في ℤ هي -1; -7; 1; 7 اذن يقبل اربعة قواسم مختلفة
اذن العدد -7 عدد اولي
2) مبدئيا العدد 7 اولي

1.2.3 ملاحظات

1) |a| عدد اولي ⇔ a عدد اولي
2) -1;0;1 ليست اعدادا اولية
3) ∀a∈ℤ: -1|a ∧ -a|a

1.2.4 خاصية

كل عدد n≥2 يقبل على الاقل قاسما اوليا

برهان :

ليكن n عددا صحيحا غير اوليا و > 1 و D مجموعة القواسم الاولية للعدد n
D≠∅ (لان n ليس اوليا) و D⊂IN* اذن D مصغورة بعدد نرمز له ب p حيث
1< p< n و p|n .
نفترض ان p ليس اوليا اذن
∃q∈IN*: q|p, 1< q< p
وبما ان p|n فان q|n وهذا يتناقض مع كون المجموعة D مصغورة ب اذن p ومنه ما افترضناه كان خاطئا وبالتالي p عدد اولي

1.2.5 مجموعة الاعداد الاولية

خاصية

مجموعة الاعداد الاولية هي مجموعة لا منتهية

برهان :

نفترض ان مجموعة الاعداد الاولية الموجبة P={p1; p2;...;pn} منتهية
ليكن N= 1+p1.p2...pn
N≥3≥2 اذن N يقبل على الاقل قاسما اوليا, فليكن d
d|N و d|p1.p2...pn
اذن d|N-p1.p2...pn اي d|1 وهذا يتناقض مع كون d اوليا وبالتالي P غير منتهية

1.3 خوارزمية اقليدس

1.3.1 مبرهنة اقليدس

ليكن (a;b)∈ℤ² حيث a< b
اذا كان b=qa+r حيث 0≤r< |a| فان a∧b=a∧r

برهان

نعين ب Da; Db و Dr لمجموعات قواسم على التوالي ل a; b و r
وبعد ذلك يكفي ان نبين ان Da∩Db= Da∩Dr
تذكير E=F⇔E⊂F و F⊂E

ليكن d∈Da∩Db اذن d|a و d|b
تذكير p|e و p|f⇒ ∀(x;y)∈ℤ²: p|xe+yf
وبما ان b=qa+r او b-qa=r فان d|b-qa اي d|r
ومنه فان d∈Da∩Dr اذن Da∩Db⊂Da∩Dr
وكذلك ليكن d∈Da∩Dr اذن d|a و d|r
وبما ان b=qa+r فان d|b اذن d∈Da∩Db ومنه فان Da∩Dr⊂Da∩Db; Da∩Db=Da∩Dr وبالتالي a∧b=a∧r

1.3.2 مثال

حدد 320 ∧ 2030

تصحيح

2030 = 6.320 + 110
320 ∧ 2030 = 320 ∧ 110
320 = 2.110 + 100
320 ∧ 110 = 110 ∧ 100
110 = 1.100 + 10
110 ∧ 100 = 100 ∧ 10
100 = 10.10 + 0 آخر باقي غير منعدم هو 10 اذن 320∧2030=10
هذه الطريقة تسمى خوارزمية اقليدس

1.3.3 حالة عامة

لدينا a;b∈ℤ حيث a< b و b= qa + r و 0≤r< |a|
لدينا a∧b=a∧r حيث 0≤r < |a|
اذا كان r=0 فان a∧b= a
واذا كانت r≠0 فان a=q₁.r + r₁
ومنه فان a∧b=r∧r₁ حيث0≤r₁ < r
اذا كان r₁=0 فان a∧b= r
واذا كان r₁≠0 فان r = q₂.r₁ +r₂
ومنه فان a∧b = r₁∧r₂ حيث 0 ≤ r₂ < r₁
اذا كان r₂ = 0 فان a ∧b= r₁
واذا كان r₂≠0 فان r₁ = q₃.r₂ +r₃
ومنه فان a∧b = r₂∧r₃ حيث 0 ≤ r₃ < r₂
.......................
اذا كان r_n-1≠0 فان r_n-2= q_n.r_n-1 +r_n
ومنه فان a∧b=r_n-1∧r_n حيث 0≤r_n < r_n-1

نفترض ان r_n =0 اذن a∧b=r_n-1 (آخر باقي غير منعدم )
والا المتتالية (r_n) للاعداد الصحيحة الطبيعية تناقصية قطعا وهذا غير ممكن

1.3.4 مبرهنة

(∀(a;b)∈ℤ² )(∃(x;y)∈ℤ²): a∧b=xa+yb

1.3.5 مبرهنة

(∀a;b;c∈ℤ): ca∧cb= |c|(a∧b)
(∀a;b;c∈ℤ): ca∨cb= |c|(a∨b)

نتيجة

a∧b=d⇒(∀c∈ℤ*): ca∧cb=|c|d