السلام عليكم و رحمة الله تعالى و بركاته.
في هذه المقالة سنشرج ال euler totient أو دالة أويلر.
قد تحتاج أن تكون متعرفا على بعض مفاهيم الرياضيات الأساسية.
المقالة ستكون رياضيات نقية و يمكن أن نبرمج بعض الأشياء.
أويلر من فطاحلة علماء الرياضيات و سمي ب الملك الرياضيين :
سنعرف بعض الأشياء المهمة قبل دخولنا في نواة أو قلب الدرس .
1 - تعريف :العدد b قابل للقسمة على a عندما نحسب b/a فنجد أن نتيجة هي عدد صحيح , ترمز بشكل التالي
a|b و تنطق a هو قاسم ل b.
مثال:
- لنأخد 20/5 النتيجة هي 4 أي عدد صحيح أي العبارة التالية صحيحة 20|5 .
- لنأخد 13/3 النتيجة هي 4.3 (يوجد عمود أفقي فوق الثلاثة) أي أنه عدد ليس بصحيح , عدد عشري أي العبارة التالية صحيحة 13∤3.
2 - تعريف : القاسم المشترك هو قاسم مشترك بين عددين أو أكثر , ليكن a و b عددين صحيحن نسمي c قاسمهما المشترك إذا و فقط إذا c|a و c|b.
مثال : نعرف أن 10/2 النتيجة هي 5 أي 10|2 و 20/2 النتيجة هي 10 أي 20|2 إذا 2 هو قاسم مشترك ل 10 و 20.
مثال : قواسم 20 هي {1,2,4,5,10,20} قواسم 10 هي {1,2,5,10} نبحث عن أكبر عدد مشترك في مجموعة قواسمهما فنجد 10 اي يمكننا كتابة (10 , 20) = 10.
4 - تعريف : الدالة f : X-->Y هي دالة شمولية (surjective) إذا كان من أجل كل عنصرا y في Y يوجد عنصر x في X بحيث تحقق الشرط التالي : f(x) = y.
مثال : لتكن الدالة f:[−1,1]→[-1,1] , f(x)=x^2 الدالة ليس شمولية لأنه توجد قيم في y لن نجد لها x بحيث نحقق العبارة الأتية f(x)= y مثلا لو أخدنا y = -0.5 الدالة تربيع معروف أنها تعطي نتائج موجبة فقط أي مستحيل أن نجد x بحيث f(x) =y حيث y ينتمي للمجال ]1,0-]
تعبير رياضي :
- نأخد نفس الدالة لكن نغير المجال إلى , f:[-1,1]-->[0,1] هذه الدالة شمولية لأنه من أجل كل y ينتمي ل Y أستطيع إيجاد x بحيث f(x) = y .
4 - تعريف : الأعداد الأولية هي أعداد موجبة صحيحة لا تملك أي قاسم غير نفسها و الواحد
مثال: 2,3,5,7 هي أعداد أولية , أي رقم زوجي أكبر من 2 هو عدد أولي .
4' - تعريف : نقول عن العددين a و b أنهما أوليان فيما بينهما إذا و فقط إذا كان قاسمهما المشترك الأكبر هو 1 , 1 = (a,b)
مثال: 6 و 7 أوليان بينهما لأن قاسمهما المشترك الأكبر هو 1 , 6 و 3 عدادن غير أوليان فيما بينهما لأن قاسمهما المشترك الأكبر هو 3 .
5- تعريف : نقول أن العدد الصحيح a متوافق مع العدد الصحيح b بالنسبة للعدد mإذا كان الفرق a−b قابلاً للقسمة على m. يُرمز لذلك بـ:
a≡b [m]
حيث يُطلق على m اسم القاعدة (لست أتذكر ماذا كنا نسميه لكن بالإنجلزية يسمى ب المودول modulus).
مثال : نعرف أن 3-35|4 أي : [4]3≡35 .
ترميز : نستخدم الرمز # لنرمز لعدد العناصر لمجموعة ما ,{1,2}# أي عدد العناصر داخل المجموعة {1,2} وت تساوي في هذا المثال 2
تعريف : دالة أويلر أو دالة فاي φ هي دالة تأخد مدخلا واحدا و هو n و المخرج سيكون عدد الأعداد الموجبة الأصغر من n و أولية مع n.
مثال : لنحسب φ(8) أول شئ سنكتب كل الأعداد لأصغر منه {1,2,3,4,5,6,7} ثم نحذف {2,4,6} لأنهم غير أوليين مع 8 فيبقى لنا {1,3,5,7} أي يتبقى لدينا أربعة أعداد و منه φ(8)=4,
لنحسب φ(7) أول شئ سنكتب كل الأعداد لأصغر منه {1,2,3,4,5,6} ثم نحذف {} لأن كل هذه أعداد أولية مع 7 فيبقى لنا {1,2,3,4,5,6} أي يتبقى لدينا 6 أعداد و منه φ(7)=6.
الفرضية 1 : من أجل أي عدد p أولي فإن φ(p) = p - 1
البرهان : إذا كان p عدد أولي فإن كل الأعداد الأصغر منه ستكون أولية معه لأنه لا يقبل أي قاسم و منه يوجد p-1 عدد أولي مع p .
مثال : حسبنا φ(7) فوجدنها 6.
الفرضية 2 : من أجل عددين أوليين p و q فإن φ(pq) = φ(p)φ(q).
البرهان : أولا حساب φ(pq) :
بما أن جميع الأعداد بين كل مضاعف من p لا تكون قابلة للقسمة على p، وهناك q مضاعفات لp في المجال بين 0 و qp ، نقوم بطرح q من qp. ويتم الأمر نفسه مع جميع مضاعفات q بطرح p، وأخيرًا نضيف 1 للتعويض عن العدد المشترك p*q الذي تم خصمه مرتين في الحسابات و منه :
φ(pq) = pq − q − p + 1
يمكتننا ترتيب العبارة بشكل الأتي منه :
q(p − 1) − (p − 1) =
أي و بإخراج p-1 كعامل مشترك نجد :
(p − 1)(q − 1) =
بإستخدام الفرضية 1 نجد
φ(p)φ(q)=
الفرضية 3 :إذا كان p عددأولي فإن φ(p^r ) = p^r − p^(r−1).
البرهان : بما أن p عدد أولي فإن
φ(p^r ) = #{1, 2, 3, . . . , p^r } − #{p, 2p, . . . , p^r }
حيث تمثل المجموعة الأولى جميع الأعداد التي هي أصغر من p^r أي أعداد أولية مع p و الغير أولية
بينما تمثل المجموعة الثانية كل أعداد التي هي مضاعفة ل p أي لأعداد ال غير أولية مع P
الفرق بينهما سيعطينا مجموعة الأعداد الأولية مع P
إذا لاحظنا سنجد أن عدد عناصر المجموعة الأولى هو p^r
بينما عدد عناصر المجموعة الثانية سيكون غير واضح
لنسترخ p كعامل مشترك سنجد
p*{1,2,3......p^(r-1)}
و منه عدد عناصره هو p^(r-1) و منه و بالتعويض نجد أن :
φ(p^r ) = p^r − p^(r−1).
الفرضية 4 : من أجل عدد n = p1^q1 *p2^q2.....pk^qk حيث p1,p2p3...pk هي أعداد أولية فإن
φ
=n⋅(1−1/p1)⋅(1−1/p2)⋯(1−1/pk).
البرهان :
من الفرضية 1 نجد أن
φ=φ(p1^q1) *φ(p2^q2).....*φ(pk^qk).
و من الفرضية 3 نجد أن :
.φ=(p1^q1 - p1^(q1 - 1))*(p2^q2 - p2^(q2 - 1)).......*(pk^qk - pk^(qk - 1))
نستخرج ال pk^(qk ) كعوامل مشتركة فنجد أن :
.φ=(p1^(q1 ))(1- p1^-1)*(
في هذه المقالة سنشرج ال euler totient أو دالة أويلر.
قد تحتاج أن تكون متعرفا على بعض مفاهيم الرياضيات الأساسية.
المقالة ستكون رياضيات نقية و يمكن أن نبرمج بعض الأشياء.
أويلر من فطاحلة علماء الرياضيات و سمي ب الملك الرياضيين :
سنعرف بعض الأشياء المهمة قبل دخولنا في نواة أو قلب الدرس .
1 - تعريف :العدد b قابل للقسمة على a عندما نحسب b/a فنجد أن نتيجة هي عدد صحيح , ترمز بشكل التالي
a|b و تنطق a هو قاسم ل b.
مثال:
- لنأخد 20/5 النتيجة هي 4 أي عدد صحيح أي العبارة التالية صحيحة 20|5 .
- لنأخد 13/3 النتيجة هي 4.3 (يوجد عمود أفقي فوق الثلاثة) أي أنه عدد ليس بصحيح , عدد عشري أي العبارة التالية صحيحة 13∤3.
2 - تعريف : القاسم المشترك هو قاسم مشترك بين عددين أو أكثر , ليكن a و b عددين صحيحن نسمي c قاسمهما المشترك إذا و فقط إذا c|a و c|b.
مثال : نعرف أن 10/2 النتيجة هي 5 أي 10|2 و 20/2 النتيجة هي 10 أي 20|2 إذا 2 هو قاسم مشترك ل 10 و 20.
3-تعريف : القاسم المشترك الأكبر هو قاسم مشترك بين عدد أو أكثر لكنه يحقق شرط أن يكون أكبر قواسم المشتركة بين عدد و أكثر , ليكن a و b عددين صحيحين قاسمهما المشترك الأكبر هو g نرمز لهذه العبارة ب
(a, b) = g أو (gcd stands for greatest common divisor) gcd(a ,b) = g مثال : قواسم 20 هي {1,2,4,5,10,20} قواسم 10 هي {1,2,5,10} نبحث عن أكبر عدد مشترك في مجموعة قواسمهما فنجد 10 اي يمكننا كتابة (10 , 20) = 10.
4 - تعريف : الدالة f : X-->Y هي دالة شمولية (surjective) إذا كان من أجل كل عنصرا y في Y يوجد عنصر x في X بحيث تحقق الشرط التالي : f(x) = y.
مثال : لتكن الدالة f:[−1,1]→[-1,1] , f(x)=x^2 الدالة ليس شمولية لأنه توجد قيم في y لن نجد لها x بحيث نحقق العبارة الأتية f(x)= y مثلا لو أخدنا y = -0.5 الدالة تربيع معروف أنها تعطي نتائج موجبة فقط أي مستحيل أن نجد x بحيث f(x) =y حيث y ينتمي للمجال ]1,0-]
تعبير رياضي :
كود:
f(x) = y
الهف هو إيجاد
x
بتعبير
y
بحيث تتحقق العبارة التالية
x^2 = y
(x^2)^1/2 = y^1/2
الدالة x^1/2
هي الدالة جذر و
تقبل أعداد موجبة فقط اي
y^1/2
تتحقق فقط من اجل
y >=0- نأخد نفس الدالة لكن نغير المجال إلى , f:[-1,1]-->[0,1] هذه الدالة شمولية لأنه من أجل كل y ينتمي ل Y أستطيع إيجاد x بحيث f(x) = y .
4 - تعريف : الأعداد الأولية هي أعداد موجبة صحيحة لا تملك أي قاسم غير نفسها و الواحد
مثال: 2,3,5,7 هي أعداد أولية , أي رقم زوجي أكبر من 2 هو عدد أولي .
4' - تعريف : نقول عن العددين a و b أنهما أوليان فيما بينهما إذا و فقط إذا كان قاسمهما المشترك الأكبر هو 1 , 1 = (a,b)
مثال: 6 و 7 أوليان بينهما لأن قاسمهما المشترك الأكبر هو 1 , 6 و 3 عدادن غير أوليان فيما بينهما لأن قاسمهما المشترك الأكبر هو 3 .
5- تعريف : نقول أن العدد الصحيح a متوافق مع العدد الصحيح b بالنسبة للعدد mإذا كان الفرق a−b قابلاً للقسمة على m. يُرمز لذلك بـ:
a≡b [m]
حيث يُطلق على m اسم القاعدة (لست أتذكر ماذا كنا نسميه لكن بالإنجلزية يسمى ب المودول modulus).
مثال : نعرف أن 3-35|4 أي : [4]3≡35 .
ترميز : نستخدم الرمز # لنرمز لعدد العناصر لمجموعة ما ,{1,2}# أي عدد العناصر داخل المجموعة {1,2} وت تساوي في هذا المثال 2
تعريف : دالة أويلر أو دالة فاي φ هي دالة تأخد مدخلا واحدا و هو n و المخرج سيكون عدد الأعداد الموجبة الأصغر من n و أولية مع n.
مثال : لنحسب φ(8) أول شئ سنكتب كل الأعداد لأصغر منه {1,2,3,4,5,6,7} ثم نحذف {2,4,6} لأنهم غير أوليين مع 8 فيبقى لنا {1,3,5,7} أي يتبقى لدينا أربعة أعداد و منه φ(8)=4,
لنحسب φ(7) أول شئ سنكتب كل الأعداد لأصغر منه {1,2,3,4,5,6} ثم نحذف {} لأن كل هذه أعداد أولية مع 7 فيبقى لنا {1,2,3,4,5,6} أي يتبقى لدينا 6 أعداد و منه φ(7)=6.
الفرضية 1 : من أجل أي عدد p أولي فإن φ(p) = p - 1
البرهان : إذا كان p عدد أولي فإن كل الأعداد الأصغر منه ستكون أولية معه لأنه لا يقبل أي قاسم و منه يوجد p-1 عدد أولي مع p .
مثال : حسبنا φ(7) فوجدنها 6.
الفرضية 2 : من أجل عددين أوليين p و q فإن φ(pq) = φ(p)φ(q).
البرهان : أولا حساب φ(pq) :
بما أن جميع الأعداد بين كل مضاعف من p لا تكون قابلة للقسمة على p، وهناك q مضاعفات لp في المجال بين 0 و qp ، نقوم بطرح q من qp. ويتم الأمر نفسه مع جميع مضاعفات q بطرح p، وأخيرًا نضيف 1 للتعويض عن العدد المشترك p*q الذي تم خصمه مرتين في الحسابات و منه :
φ(pq) = pq − q − p + 1
يمكتننا ترتيب العبارة بشكل الأتي منه :
q(p − 1) − (p − 1) =
أي و بإخراج p-1 كعامل مشترك نجد :
(p − 1)(q − 1) =
بإستخدام الفرضية 1 نجد
φ(p)φ(q)=
الفرضية 3 :إذا كان p عددأولي فإن φ(p^r ) = p^r − p^(r−1).
البرهان : بما أن p عدد أولي فإن
φ(p^r ) = #{1, 2, 3, . . . , p^r } − #{p, 2p, . . . , p^r }
حيث تمثل المجموعة الأولى جميع الأعداد التي هي أصغر من p^r أي أعداد أولية مع p و الغير أولية
بينما تمثل المجموعة الثانية كل أعداد التي هي مضاعفة ل p أي لأعداد ال غير أولية مع P
الفرق بينهما سيعطينا مجموعة الأعداد الأولية مع P
إذا لاحظنا سنجد أن عدد عناصر المجموعة الأولى هو p^r
بينما عدد عناصر المجموعة الثانية سيكون غير واضح
لنسترخ p كعامل مشترك سنجد
p*{1,2,3......p^(r-1)}
و منه عدد عناصره هو p^(r-1) و منه و بالتعويض نجد أن :
φ(p^r ) = p^r − p^(r−1).
الفرضية 4 : من أجل عدد n = p1^q1 *p2^q2.....pk^qk حيث p1,p2p3...pk هي أعداد أولية فإن
φ
=n⋅(1−1/p1)⋅(1−1/p2)⋯(1−1/pk).البرهان :
من الفرضية 1 نجد أن
φ
=φ(p1^q1) *φ(p2^q2).....*φ(pk^qk).و من الفرضية 3 نجد أن :
.φ
=(p1^q1 - p1^(q1 - 1))*(p2^q2 - p2^(q2 - 1)).......*(pk^qk - pk^(qk - 1))نستخرج ال pk^(qk ) كعوامل مشتركة فنجد أن :
.φ
=(p1^(q1 ))(1- p1^-1)*(