2- PPCM ; PGCD

2.1 المضاعف المشترك الاصغر

2.1.1 تعريف

ليكن (a;b) ∈ℤ²
المضاعف المشترك الاصغر للعددين a و b هو اصغر عدد صحيح موجب لمضاعفات كل من a و b ونكتب a∨b او ppcm(a;b)

2.1.2 مثال

a=8 و a=12
مضاعفات 8 ≤ 8.12=96 هي 8; 16; 24; 32; 40; 48; 56; 64; 72; 80; 88 96
مضاعفات 12 ≤ 8.12=96 هي 12; 24; نقف الى هذا الحد اذن 24 هو من مضاعفات 8 بالاضافة الى ذلك فان 24 هو المضاعف المشترك الاصغر وبالتالي 8∨12=24

2.2 القاسم المشترك الاكبر

2.2.1 تعريف

ليكن (a;b) ∈ℤ²
القاسم المشترك الاكبر للعددين a و b هو اكبرر عدد صحيح موجب لقواسم كل من a و b ونكتب a∧b او pgcd(a;b)

وبتعبير آخر اذا كانت Da و Db على التوالي مجموعتا قواسم a و b فان
a∧b=d ⇔ d∈Da∩Db و ∀p∈Da∩Db: d≥p

2.2.2 امثلة

75∧50=25 و 24∨14=84

2.2.3 خاصية (crible d'Eratosthène)

ليكن n عددا صحيحا اكبر قطعا من 1
1. اذا كان n ليس اوليا فان القاسم او القواسم الاولية للعدد n تكون اصغر او تساوي √n
2. اذا لم يوجد عدد اولي اصغر من او يساوي √n لا يقسم n فان n عدد اولي

تمرين 1

اختبر اذا كان n=257 اوليا?

تصحيح

لدينا √257=16,03121...
الاعداد الاولية ≤16 هي 2 ; 3 ; 5 ; 7 ; 11 و 13
2∤257 لان n فردي
3∤257 لان 3 لا يقسم مجموع ارقام n
5∤257 لان وحدة n تخالف 0 و 5

7∤257 لان 257÷7=36,714...
11∤257 لان 257÷11=23,3636..
13∤257 لان 257÷13=19,7..
اذن 257 عدد اولي

تمرين 2

اختبر اذا كان n=123 اوليا?

تصحيح

لدينا √123=9,46.. ; الاعداد الاولية ≤9 هي 2 ; 3 ; 5 و 7
2∤123
3|123 لان 3 يقسم مجموع ارقام 123 اذن
123 ليس اوليا

2.2.4 خاصيات

1) avb= m ⇒ a|m و b|m
2) a∧b=d ⇒ d|a و d|b
3) (p|a و p|b) ⇒ p|a∧b
4) (avb).(a∧b)=|a×b|
lemme d'Euclide
ليكن p عددا اوليا و (a;b)∈ℤ²
p|a.b ⇒ p|a او p|b او يقسم الاثنين

2.2.5 نتيجة

لتكن p₁;p₂;...;p_n اعدادا طبيعية اولية و d عدد اولي
d|p₁×p...×p_n ⇒ ∃i∈{1;2;...;n}: d=p_i

3- المبرهنة الاساسية للحسابيات

3.1 مبرهنة

ليكن n عددا صحيحا ≥2
يوجد p₁ ; p₂ ; ...; p_m اعداد صحيحة اولية ومختلفة مثنى مثنى ووحيدة
و a₁ ; a₂ ; ...; a_m اعدادا طبيعية وغير منعدمة
بحيث n=a₁^p₁.a₂^p₂ ... a_m^p_m

ملاحظة

اذا كان n عددا صحيحا سالبا فانه يكفي ضرب هذا العدد في 1-
اذا كان n∈ℤ\{-1;0;1}, n=±a₁^p₁.a₂^p₂....a_m^p_m
هذه الكتابة تسمى تفكيك اولي ل n

امثلة

73500=2².3.5³.7²
17550=2.3³.5².13

3.2 مبرهنة

ليكن x و y عددين طبيعيين
x= a₁^p₁.a₂^p₂....a_m^p_m
y=a₁^q₁.a₂^q₂ ...a_m^q_m
a_i اعداد اولية ومختلفة مثنى مثنى و pi و qi حيث 1≤i≤m هي اعداد طبيعية
يمكن كتابة x و y بشكل آخر

x=

m ∏aipi i=1

;

y=

m ∏aiqi i=1

pgcd(x;y)=x∧y=	m ∏aiinf(pi;qi) i=1
ppcm(x;y)=x∨y=	m ∏aisup(pi;qi) i=1
(x∧y).(x∨y)=	m ∏aipi+qi i=1

ملاحظة

x و y ليس لهما بالضرورة نفس عدد العوامل الاولية. العوامل الناقصة a_k يتم استكمالها ب a°_k=1

امثلة

ليكن x=3510 و y=1575 عددين صحيحين
1) حدد x∧y و x∨y
2) تحقق ان x.y=(x∧y).(x∨y)

تصحيح

1) لدينا : x=2.3³.5.7°.11°.13
و y=2°.3².5².7.11°.13° اذن
x∧y=2^inf(1;0).3^inf(3;2).5^inf(1;2)
. 7^inf(0;1).11^inf(0+0).13^inf(1;0)
=2⁰.3².5¹.7⁰.11⁰.13⁰
=1.9.5.1.1 =45
x∨y=2^sup(1;0).3^sup(3;2).5^sup(1;2)
. 7^sup(0;1).11^sup(0+0).13^sup(1;0)
=2¹.3³ .5².7¹ .11⁰.13¹ = 2.27.25.7.13 = 122850

2) x.y= 45.122850 = 5528250
وايضا x.y= 3550.1575 = 5528250 نحصل على نفس النتيجة :)

تمرين

1. انجز القسمة الاقليدية للعدين 1904 و 1232
2. استنتج 1904∧1232 و 1904∨1232

3.3 مبرهنة

ليكن n=a₁^p₁.a₂^p₂....a_m^p_m تفكيك عدد صحيح غير منعدم n على شكل جذاء عوامل اولية
عدد قواسم الموجبة للعدد n هو
(1+p1)(1+p2)...(1+pm)

مثال

ليكن n=90=2.3².5
قواسم العدد n الموجبة هي 1; 2; 3; 5; 6; 9; 10; 15; 18; 30; 45; 90 اذن توجد 12 قاسما موجبا للعدد 90.
هذه النتيجة تحقق المبرهنة
(1+1)(1+2)(1+1)=12