4- الموافقة بترديد n والمجموعة ℤ/nℤ

4.1 الموافقة بترديد n

4.1.1 تعريف

ليكن (a;b)∈ ℤ² و n∈IN*
نقول ان : a يوافق b بترديد n ونكتب a≡b [n] اذا كان n يقسم b-a
وبتعبير آخر
a≡b [n] ⇔ n | b-a
⇔ ∃k∈ℤ, b=kn+a

امثلة

17 ≡ 8[3] لان 3|17-8
13 ≡ 9[2] لان 2|13-9

4.1.2 خاصيات

1) الانعكاسية:
∀n∈IN*; ∀a∈ℤ a ≡ a[n]
2) التماثلية:
∀n∈IN*; ∀(a ; b)∈ℤ²
a≡b[n] ⇔ b≡a[n]
3) المتعدية:
∀n∈IN*; ∀a;b;c∈ℤ:
a≡b[n] ; b≡c[n] ⇒ a≡c[n]

4.1.3 تعريف:

الموافقة بترديد n هو:
انعكاسي وتماثلي ومتعدي
نقول ان التوافق بترديد n هو علاقة تكافؤ

4.1.4 خاصية

n∈IN* ; (a;b)∈Z²
a ≡ b[n] يكافئ a و b لهما نفس الباقي في القسمة الاقلدية على n.

برهان

لدينا a=nq+r حيث 0≤r < n
b=nq'+r' حيث 0≤r' < n
a≡b[n] ⇔ ∃k∈ℤ b-a=kn
⇔ n(q'-q)+(r'-r)=kn
⇔ r'-r =(k+q-q')n
⇔ n | (r'-r) ⇔ r' = r
لان -n < -r ≤ 0 و 0 ≤ r' < n
او |r'-r| < n وبما ان n | r'-r فان r=r'

ملاحظة

ليكن (a;b)∈ℤ² ; n∈IN*
ac≡bc[n] ⇏ a≡b[n]

مثال مضاد

3.5≡3.4[3] لكن 5≢4[3]

تمرين

ليكن a=137 ; b=123 ; n=7
بين ان 137 ≡123[7]

تصحيح

لدينا 137=19.7+4 ; 0≤r=4< 7
و 123=17.7+4 ; 0≤r'=4< 7
اذن a و b لهما نفس الباقي في القسمة الاقلدية على 3
وبالتالي 137≡123[7]
وبالاضافة الى ذلك فان 137≡123≡4[7]

4.1.5 مقلوب عنصر بالموافقة بترديد n

تعريف

ليكن (a;n)∈ℤ*²
a يقبل مقلوبا بالموافقة بترديد n اذا وجد عدد صحيح b بحيث a.b≡1[n]

مثال

3.7≡1[10] اذن 3 هو مقلوب للعدد 7 بترديد 10

مثال

نضع n=17 اوجد مقلوبا للعدد 4

تصحيح

نرمز لمقلوب 4 ب x
4.x≡1[17] يكافئ E: 4x-17k=1; k∈Z
17=4.4+1 يكافئ 17-4.4=4.(-4)-17(-1)=1
(-4;-1) حل خاص للمعادلة E اذن يكفي اخذ x=-4 الذي هو بالفعل مقلوبا ل 4 بالتوافق بترديد 17

تمرين

بين انه 7 | 594²⁰

4.2 المجموعة Z/nZ

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

تقديم

ليكن n∈IN*
(∀x∈ℤ)(∃(q;r)∈ℤ×IN): x=nq+r
حيث 0≤r < n
يعني ان x≡r[n]
اذن r=0 او r=1 او r=2 او .. او r=n-1
بتعبير آخر r∈{0;1;2;..; n-1}
نأخذ مثالا n=3
اذن r∈{0;1;2}
x≡0[3] ⇔ 3|x
⇔(∃k∈ℤ):x=3k
اذن x∈{p∈Z / p=3k, k∈ℤ} نرمز لهذه المجموعة ب 0
x≡1[3] ⇔ 3|(x-1)
اذن x ∈{p∈ℤ / p=3k+1, k∈ℤ} نرمز لهذه المجموعة ب 1
x≡2[3] ⇔ 3|(x-2)
اذن x∈{p∈ℤ / p=3k+2, k∈ℤ} نرمز لهذه المجموعة ب 2

هذه المجموعات تسمى اصناف تكافؤ للموافقة بترديد 3 في ℤ
هي كلها منفصلة مثنى مثنى واتحادها هو المجموعة ℤ=0∪1∪2, مجموعة الاصناف {0;1; 2} نرمز لها ب ℤ/3ℤ; ℤ/3ℤ={0;1; 2}

مثال

نضع n=4 اذن ℤ= 0∪1 ∪ 2 ∪ 3
0 = {x∈Z/ x=4k, k∈Z}
1 = {x∈Z/ x=4k+1, k∈Z}
2 = {x∈Z/ x=4k+2, k∈Z}
3 = {x∈Z/ x=4k+3, k∈Z}

ملاحظة

(4= 0; 5= 1 ...)

تعريف

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

مثال

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

4.2.2 العمليات في 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]
x≡y[n] ⇒ xx'≡yx'[n]

ملاحظة :

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

مثال

10≡-4[7] و 37≡2[7]
اذن 10+37≡-4+2[7] اي 47≡-2[7]
و 10.37≡-4.2[7] ومنه فان 370≡-8[7]

تدكير

ليكن n∈IN*; (x;x')∈ℤ² ; (u;u')∈ℤ²
x≡u[n]⇒x∈ū و x'≡u'[n] ⇒ x'∈ū'
يمكن كتابة x+x'∈ū+ū'
وبما ان x+x'≡u+u'[n] فان x+x'∈u+u'

خاصيات

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

امثلة

نضع n=5
1 + 3 = 1 + 3 = 4
2 . 3 = 2 . 3 = 6 = 1
نضع n=7
4 + 5 = 9 = 2
5 . 2 = 10 = 3