7- المجموعة Z/nZ

7.1 المجموعة Z/nZ حيث n∈IN*

7.1.1 تعريف

ليكن n∈IN* صنف تكافؤ للتوافق بترديد n في Z, هي مجموعة الاعداد النسبية التي لها نفس الباق r في القسمة الاقليدية على n .
هذا الصنف نرمز له ب : r={x∈Z / x ≡ r[n]}
مجموعة اصناف التكافؤ بترديد n في ℤ, هي ℤ/nℤ
ℤ/nℤ = {0 ; 1 ; 2 ; ... ; n-1} ; n ≥ 2
اذن : ℤ = 0 ∪ 1 ∪ 2 ∪ ... ∪ n-1. ( n ≥ 2)

7.1.2 مثال

نضع n=3
مجموعة اصناف التكافؤ بترديد 3 في Z هي Z/3Z ={0 ; 1 ; 2}
1={x∈Z/ x≡1[3]}

7.2 العمليات في Z/nZ وخاصياتها

7.2.1 العمليات في Z/nZ

انسجام التوافق في Z مع الجمع والضرب
n∈IN*; (x;y)∈ℤ²; (x';y')∈ℤ²
x≡y[n] ; x'≡y'[n] ⇒ x+x' ≡ y+y'[n]
x≡y[n] ; x'≡y'[n] ⇒ x-x' ≡ y-y'[n]
x≡y[n] ⇔ x+x' ≡ y+x'[n]
x≡y[n] ; x'≡y'[n] ⇒ xx'≡yy'[n]

ملاحظة :

العكس غير صحيح
مثال مضاد 3.5≡3.4[3] لكن 5≢4[3]
x≡y[n] ⇒ x^p≡y^p[n] ; p∈IN*

7.2.2 خاصيات

ليكن n∈IN*
x ; y صنفان في Z/nZ
x + y = x + y
x . y = x . y

تمارين

حل في ℤ/9ℤ المعادلة : 3.x=3
تصحيح:

x	0	1	2	3	4	5	6	7	8
3x	0	3	6	0	3	6	0	3	6

اذن S={1;4;7}

7.3 المجموعة Z/pZ حيث p عددا اوليا

7.3.1 تعريف:

ليكن x∈Z/pZ
نقول ان x يقبل مقلوبا اذا وجد عنصر x' في Z/pZ بحيث x.x'=1

7.3.2 امثلة

3 عنصرا من Z/5Z
وليكن x عنصرا من Z/5Z بحيث 3=1 نبحث عن x ان وجد
x.3=1 ⇔ 3x≡1[5]
يمكن ملاحظة x=2 لكن نبحث عنه بواسطة التوافق بترديد 5 باستعمال مبرهنة اقليدس
5=1.3+2 ; 3=1.2+1
اذن 1=3-1.2=3-1.(5-1.3)=2.3-1.5

ليكن 1≡2.3[5] اذن x≡2.3x[5]
وبما ان 3x≡1[5] اي 2.3x≡2[5] اذن x≡2[5]
وبالتالي فان 2 هو مقلوب ل 3.

7.3.3 خاصية

ليكن p عدد اولي
∀x∈Z*: ∃x'∈Z , x.x'≡1[p]

7.3.4 خاصية

ليكن p عدد اولي
∀(x;x')∈Z/pZ: x.x'=0 ⇒ x=0 او x'=0

برهان

x.x'=0 ⇒ x.x'=0⇒ x.x'≡0[p]
⇒ p|x.x' ⇒ p|x او p|x' ( اولي p)
⇒ x≡0[p] او x'≡0[p]
⇒ x=0 او x'=0

ملاحظة

اذا كان p ليس اوليا اي عددا مركبا فان الخاصية السابقة غير صحيحة
مثال مضاد : ناخذ عددا مركبا p=15=3.5
لدينا 3.5=0 ولكن 3≠0 و 5≠0

تمرين 1

ليكن n∈IN باستعمال التوافق بين ان n(n+1) عددا زوجيا

تصحيح

يمكن انجاز هذا السؤال بفصل الحالات (اذا كان n زوجيا والحالة اذا كان n فرديا)
سنقوم بنفس الطريقة ولكن باستعمال التوافق بترديد 2
ℤ/2ℤ={0 ; 1}
للتذكير ℤ=0∪1, 0={x∈IN/ x=2k; k∈IN} وهذه بالضبط مجموعة الاعداد الزوجية
و 1={x∈IN / x=1+2k; k∈IN} مجموعة الاعداد الفردية
نعود الى السؤال للبرهنة على ان n(n+1) زوجيا يكفي ان نبين ان 2|n(n+1) اي n(n+1)≡0[2]
لدينا n∈IN اذن اذا كان n∈0 فان 0.(0+1)=0 عدد زوجي
واذا كان n∈1 فان 1.(1+1)=2 هو ايضا عدد زوجي
وبالتالي ∀n∈IN: n(n+1) عدد زوجي .

تمرين 2

حل في Z المعادلة 5x≡10[37]
تصحيح: 5∧37=1 يمكن القسمة على 5 ولكن نبحث عن مقلوب للعدد 5 بترديد 37 اي نبحث عن u بحيث 5.u≡1[37]
باستعمال خوارزمية اقليدس
37=7.5+2
5=2.2+1 اذن 1=5-2.2=5-2.(37-7.5)=15.5-2.37
اذن 15.5≡1[37]
لدينا من جهة 15.5.x=1.x[37] ومن جهة اخرى 15.5.x=15.10[37]
وباستعمال العلاقة المتعدية فان x=150[37]
ونعلم ان 150>37 اذن يمكن الاختزال
150=4.37+2 اذن x≡2[37] وبالتالي S={2+37k; k∈Z}

8- مبرهنة فيرما (فيرما الصغرى)

8.1 مبرهنة

ليكن p عددا اوليا موجبا
∀ a∈ℤ: a^p≡a[p]

8.2 مبرهنة (فيرما الصغرى)

ليكن p عددا اوليا موجبا
∀ a∈ℤ*, a∧p=1⇒ a^p-1≡1[p].

امثلة

3 عدد اولي و 8∧3=1 اذن حسب مبرهنة فيرما الصغرى فان 8²≡1[3]
19 عدد اولي و 19∧15=1 اذن حسب مبرهنة فيرما الصغرى فان 15¹⁸≡1[19].