مقالات

3.1: عملية Modulo


تعريف

دعونا (n ) ( in ) ( mathbb {Z _ +} ).

حدد علاقة " ( equiv )" في ( mathbb {Z} ) بواسطة (a equiv b (mod ، n) ) iff (if and only if) (n mid ab ) للجميع (أ ، ب في mathbb {Z} ).

مثال ( PageIndex {1} ):

افترض (n = 5، ) أن الباقي المحتمل هو (0،1، 2، 3، ) و (4، ) عندما نقسم أي عدد صحيح على (5 ).

هل (6 ، equiv 11 (mod ، 5) )؟ نعم ، لأن (6 ) و (11 ) كلاهما ينتميان إلى نفس فئة المطابقة / البقايا (1 ). وهذا يعني عندما يتم تقسيم (6 ) و (11 ) على (5 ) والباقي هو (1. )

هل (7 equiv 15 (mod ، 5) )؟ لا ، لأن (7 ) و (15 ) لا ينتميان إلى نفس فئة المطابقة / البقايا. السبعة بها باقي (2، ) بينما (15 ) بها باقي (0، ) وبالتالي فإن (7 ) لا يتوافق مع (15 (mod ، 5) ). هذا هو (7 لا يكافئ 15 (mod ، 5) ).

مثال ( PageIndex {2} ): حساب الساعة

ابحث عن (18:00 ) ، هذا هو (18 (mod ، 12) ).

المحلول

(18 وحدة نمطية (12) equiv 6 ). 6 م.

ملكيات

دعونا (n in mathbb {Z _ +} ). ثم

النظرية 1:

يُقال أن عددين صحيحين (أ ) و (ب ) متطابقان (n ) ، (a equiv b (mod ، n) ) ، إذا كان كل ما يلي صحيحًا:

أ) (م منتصف (أ-ب). )

ب) يكون لكل من (أ ) و (ب ) نفس الباقي عند القسمة على (n. )

ج) (a-b = kn ) ، لبعض (k in mathbb {Z} ).

ملاحظة: البقايا المحتملة لـ (n ) هي (0، ...، n-1. )

خاصية انعكاسية

النظرية 2:

العلاقة " ( equiv )" فوق ( mathbb {Z} ) انعكاسية.

دليل - إثبات: دعونا (a in mathbb {Z} ).

ثم (a-a = 0 (n) ) و (0 in mathbb {Z} ).

وبالتالي (a equiv a (mod ، n) ).

وبالتالي فإن معيار التطابق هو انعكاسي.

خاصية متماثلة

النظرية 3:

العلاقة " ( equiv )" فوق ( mathbb {Z} ) متماثلة.

دليل - إثبات: دعونا (a، b in mathbb {Z} ) بحيث (a equiv b ) (mod n).

ثم (a-b = kn، ) لبعض (k in mathbb {Z} ).

الآن (b-a = (-k) n ) و (- k in mathbb {Z} ).

ومن ثم (b equiv a (mod ، n) ).

وبالتالي فإن العلاقة متماثلة.

خاصية غير متماثلة

هل العلاقة " ( equiv )" فوق ( mathbb {Z} ) غير متماثلة؟

مكافحة المثال: (n ) تم إصلاحه

اختر: (أ = ن + 1 ، ب = 2 ن + 1 ) ، ثم

(a equiv b (mod ، n) ) و (b equiv a (mod ، n) )

لكن (أ ني ب )

وبالتالي فإن العلاقة " ( equiv )" في ( mathbb {Z} ) ليست غير متماثلة.

خاصية متعدية

النظرية 4:

العلاقة " ( equiv )" فوق ( mathbb {Z} ) متعدية.

دليل - إثبات: دعونا (a، b، c in ) ( mathbb {Z} ) ، مثل (a equiv b (mod n) ) و (b equiv c (mod n). )

ثم (a = b + kn، k in ) ( mathbb {Z} ) و (b = c + hn، h in ) ( mathbb {Z} ).

سنبين أن (a equiv c (mod ، n) ).

ضع في اعتبارك (a = b + kn = (c + hn) + kn = c + (hn + kn) = c + (h + k) n، h + k in ) ( mathbb {Z} ).

وبالتالي (a equiv c (mod ، n) ).

وبالتالي فإن نموذج التطابق (n ) متعد.

النظرية 5:

العلاقة " ( equiv )" على ( mathbb {Z} ) هي علاقة تكافؤ.

فئات مودولو

يترك . العلاقة ( equiv ) على بواسطة (a equiv b ) إذا وفقط إذا ، هي علاقة تكافؤ. فئات لديها فئات التكافؤ التالية:

.

مثال على كتابة فصول معادلة:

الجوانب الحسابية:

البحث عن "mod 5"

٪٪ python3print ("عدد صحيح mod 5") لـ i في النطاق (30): print (i، ""، i٪ 5)

الرمز ( PageIndex {1} ) (بايثون):

٪٪ بيثون 3

هناك فرق بين المعامل والباقي. فمثلا:

-21 mod 4 هي 3 لأن -21 + 4 x 6 هي 3.

لكن -21 مقسومة على 4 تعطي -5 مع باقي -1.

بالنسبة للقيم الموجبة ، لا يوجد فرق.

في C ،٪ هو بقية 1 .

. نتيجة العامل / هي الحاصل الجبري مع تجاهل أي جزء كسري. (يسمى هذا غالبًا & quottruncation نحو الصفر & quot.) C11dr §6.5.5 6

يجب أن يكون لمعاملات العامل٪ نوع عدد صحيح. C11dr §6.5.52

نتيجة العامل / هي حاصل قسمة المعامل الأول على الثاني نتيجة عامل التشغيل٪ هو بقية . C11dr § 6.5.5 5

ما الفرق بين "mod" و "باقي"؟

لا يُعرِّف C & quotmod & quot ، مثل دالة معامل العدد الصحيح المستخدمة في القسمة الإقليدية أو أي طريقة أخرى.
& quotEuclidean mod & quot يختلف عن عملية C a٪ b عندما تكون a سالبة.

& quotMod & quot أو modulo كتقسيم إقليدي

ملاحظة حول النقطة العائمة: double fmod (double x، double y) ، على الرغم من تسميتها & quotfmod & quot ، إلا أنها تختلف عن القسمة الإقليدية & quotmod & quot ، ولكنها تشبه باقي العدد الصحيح C:

تحسب دوال fmod باقي النقطة العائمة من x / y. C11dr §7.12.10.1 2

توضيح: يحتوي C أيضًا على دالة اسمية مزدوجة modf (قيمة مزدوجة ، double * iptr) والتي تقسم قيمة الوسيطة إلى أجزاء متكاملة وجزئية ، كل منها له نفس النوع وعلامة الوسيطة. هذا لا علاقة له بمناقشة & quotmod & quot هنا باستثناء تشابه الاسم.

بالنسبة لأولئك الذين يريدون وظائف مناسبة في جميع الحالات ، فإن modulo_Euclidean () المحسنة التي 1) تكتشف mod (x ، 0) و 2) نتيجة UB جيدة ولا توجد مع modulo_Euclidean2 (INT_MIN، -1). مستوحى من 4 تطبيقات مختلفة للنمط مع سلوك محدد بالكامل.

1 قبل C99 ، كان تعريف C لـ٪ لا يزال هو بقية من القسمة ، ولكن بعد ذلك / سمحت للحاصلات السالبة بالتقريب بدلاً من & quottruncation نحو الصفر & quot. انظر لماذا تحصل على قيم مختلفة لقسمة الأعداد الصحيحة في C89 ؟. وهكذا مع بعض التجميعات قبل C99 ، يمكن أن يعمل كود ٪ تمامًا مثل القسم الإقليدي & quotmod & quot. سيعمل modulo_Euclidean () أعلاه مع باقي المدرسة القديمة البديلة أيضًا.

في C و C ++ والعديد من اللغات ، فإن النسبة المئوية هي الباقي وليس عامل المعامل.

على سبيل المثال في العملية -21 / 4 يكون الجزء الصحيح هو -5 والجزء العشري هو -.25. الباقي هو الجزء الكسري في المقسوم عليه ، لذا فإن الباقي هو -1. يستخدم JavaScript عامل التشغيل المتبقي ويؤكد ذلك

عامل المعامل هو كما لو كان لديك & quotclock & quot. تخيل دائرة بقيمها 0 و 1 و 2 و 3 عند موضع الساعة 12 والساعة 3 والساعة 6 والساعة 9 على التوالي. إن التدرج في خارج القسمة على مدار الساعة على مدار الساعة يوجهنا إلى نتيجة عملية المقياس ، أو ، في مثالنا ، حاصل قسمة سالب ، عكس اتجاه عقارب الساعة ، نحصل على 3.

ملحوظة: المعامل هو دائمًا نفس علامة المقسوم عليه والباقي هو نفس علامة حاصل القسمة. إضافة المقسوم عليه والباقي عندما يكون أحدهما على الأقل سالبًا ينتج عنه المعامل.

ستكون علامة الباقي هي نفس علامة القسمة وستكون علامة المقياس هي نفسها المقسوم عليه.

الباقي هو ببساطة الجزء المتبقي بعد القسمة الحسابية بين رقمين صحيحين بينما المعامل هو مجموع الباقي والمقسوم عليه عندما يتم التوقيع عليهما بشكل معاكس والجزء المتبقي بعد القسمة الحسابية عندما يكون كل من الباقي والمقسوم عليهما من نفس العلامة.

مثال على الباقي:

10٪ 3 = 1 [هنا قابل للقسمة هو 10 والذي يتم توقيعه بشكل إيجابي ، لذا سيتم أيضًا توقيع النتيجة بشكل إيجابي]

-10٪ 3 = -1 [هنا القسمة هي -10 والتي تم توقيعها سلبًا ، لذا سيتم أيضًا توقيع النتيجة سلبًا]

10٪ -3 = 1 [هنا قابل للقسمة هو 10 والذي يتم توقيعه بشكل إيجابي ، لذا سيتم أيضًا توقيع النتيجة بشكل إيجابي]

-10٪ -3 = -1 [هنا القسمة هي -10 والتي تم توقيعها سلبًا ، لذا سيتم أيضًا توقيع النتيجة سلبًا]

مثال على المعامل:

5٪ 3 = 2 [هنا القسمة هي 5 التي يتم توقيعها بشكل إيجابي ، لذا سيتم أيضًا توقيع الباقي بشكل إيجابي ويتم أيضًا توقيع القاسم بشكل إيجابي. نظرًا لأن كل من الباقي والمقسوم عليهما من نفس العلامة ، فستكون النتيجة مماثلة للباقي]

-5٪ 3 = 1 [هنا القسمة هي -5 والتي يتم توقيعها سلبًا ، لذلك سيتم أيضًا توقيع الباقي بشكل سلبي ويتم توقيع القاسم بشكل إيجابي. بما أن كلا من الباقي والمقسوم عليه إشارة معاكسة ، فإن النتيجة ستكون مجموع الباقي والمقسوم عليه -2 + 3 = 1]

5٪ -3 = -1 [هنا القسمة هي 5 والتي يتم توقيعها بشكل إيجابي ، لذلك سيتم أيضًا توقيع الباقي بشكل إيجابي ويتم توقيع القاسم سلبًا. بما أن كلا من الباقي والمقسوم عليه إشارة معاكسة ، فإن النتيجة ستكون مجموع الباقي والمقسوم عليه 2 + -3 = -1]

-5٪ -3 = -2 [هنا القسمة هي -5 والتي يتم توقيعها سلبًا ، لذلك سيتم أيضًا توقيع الباقي بشكل سلبي ويتم أيضًا توقيع القاسم سلبًا. نظرًا لأن كل من الباقي والمقسوم عليهما من نفس العلامة ، فستكون النتيجة مماثلة للباقي]


محتويات

نظرا لعدد صحيح ن & GT 1 ، تسمى أ معام، ويقال أن يكون تتطابق modulo n ، إذا كان n هو قاسم الاختلاف بينهما (أي إذا كان هناك عدد صحيح ك مثل ذلك أب = كن ).

نموذج التطابق n هو علاقة تطابق ، بمعنى أنها علاقة تكافؤ متوافقة مع عمليات الجمع والطرح والضرب. يُشار إلى نموذج التطابق n:

الأقواس تعني أن (mod ن) ينطبق على المعادلة بأكملها ، وليس فقط على الجانب الأيمن (هنا ب). يجب عدم الخلط بين هذا الترميز والتدوين ب عصري ن (بدون أقواس) ، والتي تشير إلى عملية modulo. في الواقع، ب عصري ن يشير إلى العدد الصحيح الفريد بحيث يكون 0 ≤ أ & lt ن و a ≡ b (mod n) > n)> (أي ما تبقى من b < displaystyle b> عند القسمة على n < displaystyle n> [1]).

يمكن إعادة كتابة علاقة التطابق كـ

يظهر صراحة علاقته بالتقسيم الإقليدي. ومع ذلك ، فإن ب هنا لا داعي لبقية تقسيم أ بواسطة ن. بدلا من ذلك ، ما البيان أب (عصري ن) يؤكد ذلك أ و ب لها نفس الباقي عند القسمة على ن . هذا هو،

حيث 0 ≤ ص & lt ن هو الباقي المشترك. بطرح هذين التعبيرين ، نستعيد العلاقة السابقة:

عن طريق الإعداد ك = صف.

أمثلة تحرير

في المعامل 12 ، يمكن تأكيد ما يلي:

لأن 38-14 = 24 ، وهو مضاعف 12. طريقة أخرى للتعبير عن ذلك هي القول بأن كلا من 38 و 14 لهما نفس الباقي 2 ، عند القسمة على 12.

ينطبق تعريف التطابق أيضًا على القيم السالبة. فمثلا:

علاقة التطابق تفي بجميع شروط علاقة التكافؤ:

  • الانعكاسية: أأ (عصري ن)
  • تناظر: أب (عصري ن) لو بأ (عصري ن) للجميع أ , ب ، و ن .
  • انتقالية: إذا أب (عصري ن) و بج (عصري ن) ، من ثم أج (عصري ن)

لو أ1ب1 (عصري ن) و أ2ب2 (عصري ن)، أو إذا أب (عصري ن)، من ثم:

  • أ + كب + ك (عصري ن) لأي عدد صحيح ك (التوافق مع الترجمة)
  • ك أك ب (عصري ن) لأي عدد صحيح ك (التوافق مع القياس)
  • أ1 + أ2ب1 + ب2 (عصري ن) (التوافق مع الإضافة)
  • أ1أ2ب1ب2 (عصري ن) (التوافق مع الطرح)
  • أ1أ2ب1ب2 (عصري ن) (التوافق مع الضرب)
  • أكبك (عصري ن) لأي عدد صحيح غير سالب ك (التوافق مع الأس)
  • ص(أ) ≡ ص(ب) (عصري ن) ، لأي كثير حدودص(x) مع معاملات عدد صحيح (التوافق مع تقييم متعدد الحدود)

لو أب (عصري ن) ، فمن الخطأ عمومًا أن ك أك ب (عصري ن). ومع ذلك ، فإن ما يلي صحيح:

  • لو جد (عصري φ(ن))، أين φ هي دالة أويلر الكلية ، إذن أجأد (عصري ن) -بشرط أ مع حقوق النشر ن .

لإلغاء المصطلحات العامة ، لدينا القواعد التالية:

  • لو أ + كب + ك (عصري ن) ، أين ك هو أي عدد صحيح ، إذن أب (عصري ن)
  • لو ك أك ب (عصري ن) و ك مع حقوق النشر ن ، من ثم أب (عصري ن)
  • لو ك أك ب (عصري كن) ، من ثم أب (عصري ن)

يتم تعريف المعكوس الضربي النمطي بالقواعد التالية:

  • الوجود: يوجد عدد صحيح يرمز له أ –1 من هذا القبيل أأ –1 1 (نموذجي ن) إذا وفقط إذا أ مع حقوق النشر ن . هذا العدد الصحيح أ -1 يسمى أ معكوس مضاعف نمطي من modulo ن .
  • لو أب (عصري ن) و أ - 1 موجود إذن أ –1 ≡ ب –1 (نموذجي ن) (التوافق مع المقلوب الضربي ، وإذا أ = ب ، نموذج فريد ن )
  • لو فأسب (عصري ن) و أ هي جريمة ن ، ثم يتم إعطاء حل هذا التطابق الخطي بواسطة xأ –1 ب (عصري ن)

المعكوس الضربي xأ –1 (نموذجي ن) يمكن حسابها بكفاءة عن طريق حل معادلة بزوت أ س + ن ص = 1 لـ x، y - باستخدام الخوارزمية الإقليدية الموسعة.

على وجه الخصوص ، إذا ص هو عدد أولي ، إذن أ مع حقوق النشر ص لكل أ مثل هذا 0 العلامة & lt أ & lt ص وبالتالي يوجد معكوس ضربي للجميع أ هذا لا يتوافق مع الصفر modulo ص .

فيما يلي بعض الخصائص الأكثر تقدمًا لعلاقات التطابق:

    : لو ص عدد أولي ولا يقسم أ ، من ثم أص - 1 1 (تعديل ص). : لو أ و ن هي جريمة جماعية ، إذن أφ(ن) ≡ 1 (تعديل ن) ، أين φ هي دالة أويلر الكلية
  • إحدى النتائج البسيطة لنظرية فيرما الصغيرة هي أنه إذا ص هو عدد أولي ، إذن أ −1 ≡ أص - 2 (تعديل ص) هو المعكوس الضربي لـ 0 & lt أ & lt ص . بشكل عام ، من نظرية أويلر ، إذا أ و ن هي جريمة جماعية ، إذن أ −1 ≡ أφ(ن) - 1 (تعديل ن) .
  • نتيجة بسيطة أخرى هي أنه إذا أب (عصري φ(ن))، أين φ هي دالة أويلر الكلية ، إذن كأكب (عصري ن) متاح ك مع حقوق النشر ن . : ص هو عدد أولي إذا وفقط إذا (ص - 1)! ≡ −1 (تعديل ص). : لأي أ , ب والجريمة م , ن ، يوجد ملف فريد x (عصري مليون) مثل ذلك xأ (عصري م) و xب (عصري ن). في الحقيقة، xبي امن –1 م + أم –1 ن (عصري مليون) أين من −1 هو معكوس م مودولو ن و نم −1 هو معكوس ن مودولو م . : التطابق F (x) ≡ 0 (تعديل ص) ، أين ص هو عدد أولي و F (x) = أ0xن + . + أن هو كثير الحدود مع معاملات عدد صحيح مثل ذلك أ0 ≠ 0 (تعديل ص) ، على الأكثر ن الجذور. : رقم ز هو نموذج جذر بدائي ن إذا ، لكل عدد صحيح أ ل ن ، هناك عدد صحيح ك مثل ذلك زكأ (عصري ن). نموذج جذر بدائي ن موجود إذا وفقط إذا ن يساوي 2 ، 4 صك أو 2صك ، أين ص هو عدد أولي فردي و ك هو عدد صحيح موجب. إذا كان نموذج الجذر البدائي ن موجود ، ثم هناك بالضبط φ(φ(ن)) هذه الجذور البدائية ، أين φ هي دالة أويلر الكلية. : عدد صحيح أ هو مقياس بقايا تربيعية ن ، إذا كان هناك عدد صحيح x مثل ذلك x 2 ≡ أ (عصري ن). معيار أويلر يؤكد ذلك ، إذا ص عدد أولي فردي ، و a ليس من مضاعفات p إذن أ هو مقياس بقايا تربيعية ص إذا وفقط إذا

مثل أي علاقة تطابق ، نموذج التطابق ن هي علاقة تكافؤ ، وفئة التكافؤ للعدد الصحيح أ ، التي يرمز إليها أ ن ، هل المجموعة <... ، أ − 2ن, أن, أ, أ + ن, أ + 2ن،…>. تتكون هذه المجموعة من جميع الأعداد الصحيحة المتطابقة ل أ مودولو ن ، يسمى فئة التطابق, فئة المخلفات، أو ببساطة بقايا من العدد الصحيح أ مودولو ن . عندما يكون المعامل ن معروف من السياق ، يمكن أيضًا الإشارة إلى تلك البقايا [أ] .

كل modulo فئة بقايا ن يمكن تمثيلها من قبل أي عضو من أعضائها ، على الرغم من أننا عادة ما نمثل كل فئة متبقية بواسطة أصغر عدد صحيح غير سالب ينتمي إلى تلك الفئة [2] (لأن هذا هو الباقي الصحيح الذي ينتج عن القسمة). أي عضوين من فئات مختلفة من المخلفات modulo ن هي modulo غير متناسقة ن . علاوة على ذلك ، ينتمي كل عدد صحيح إلى وحدة فئة بقايا واحدة فقط ن . [3]

مجموعة الأعداد الصحيحة <0 ، 1 ، 2 ، ... ، ن - 1> يسمى أقل وحدة نظام بقايا ن. أي مجموعة من ن أعداد صحيحة ، لا اثنان منها متطابقتان modulo ن ، يسمى أ نموذج نظام المخلفات الكامل ن.

نظام المخلفات الأقل هو نظام كامل للبقايا ، ونظام المخلفات الكامل هو ببساطة مجموعة تحتوي على ممثل واحد بدقة لكل وحدة فئة من البقايا ن . [4] على سبيل المثال. أقل نموذج لنظام المخلفات 4 هو <0 ، 1 ، 2 ، 3>. تتضمن بعض أنظمة المخلفات الكاملة الأخرى النموذج 4 ما يلي:

بعض المجموعات التي هي ليس النموذج 4 لأنظمة المخلفات الكاملة:

  • <−5، 0، 6، 22> ، نظرًا لأن 6 مطابق لـ 22 modulo 4.
  • <5 ، 15> ، نظرًا لأن النموذج 4 لنظام المخلفات الكامل يجب أن يحتوي بالضبط على 4 فئات متبقية غير متطابقة.

نظم المخلفات المخفضة تحرير

بالنظر إلى دالة أويلر الكلية φ (ن) ، أي مجموعة من φ (ن) الأعداد الصحيحة نسبيًا ن ويتعارض بشكل متبادل تحت المعامل ن يسمى أ نظام نظام المخلفات المخفّض ن. [5] المجموعة <5 ، 15> أعلاه ، على سبيل المثال ، هي مثال لنظام نظام المخلفات المختزل 4.

تم تحديد المجموعة لـ ن & gt 0 كـ:

نحدد الجمع والطرح والضرب على Z / n Z / n mathbb > بالقواعد التالية:

التحقق من أن هذا تعريف صحيح يستخدم الخصائص المقدمة من قبل.

كما في حساب 24 ساعة.

المجموعة الفرعية المضاعفة للأعداد الصحيحة modulo ن يُرمز إليه بـ (Z / n Z) × / n mathbb ) ^ <مرات >>. يتكون هذا من ¯ n _> (أين أ هي جريمة ن) ، وهي بالتحديد الفئات التي تمتلك معكوسًا مضاعفًا. هذا يشكل مجموعة تبادلية تحت الضرب ، بالترتيب φ (n) .

في الرياضيات النظرية ، يعد الحساب النمطي أحد أسس نظرية الأعداد ، حيث يتطرق إلى كل جانب من جوانب دراستها تقريبًا ، ويستخدم أيضًا على نطاق واسع في نظرية المجموعة ، ونظرية الحلقة ، ونظرية العقدة ، والجبر المجرد. في الرياضيات التطبيقية ، يتم استخدامه في الجبر الحاسوبي والتشفير وعلوم الكمبيوتر والكيمياء والفنون البصرية والموسيقية.

تطبيق عملي للغاية هو حساب المجموع الاختباري داخل معرفات الرقم التسلسلي. على سبيل المثال ، يستخدم الرقم القياسي الدولي للكتاب (ISBN) أسلوب الحساب 11 (لرقم ISBN المكون من 10 أرقام) أو النموذج 10 (لرقم ISBN المكون من 13 رقمًا) لاكتشاف الأخطاء. وبالمثل ، فإن أرقام الحسابات المصرفية الدولية (IBANs) ، على سبيل المثال ، تستفيد من المعادلة 97 الحسابية لاكتشاف أخطاء إدخال المستخدم في أرقام الحسابات المصرفية. في الكيمياء ، الرقم الأخير من رقم تسجيل CAS (رقم تعريف فريد لكل مركب كيميائي) هو رقم تحقق ، يتم حسابه بأخذ الرقم الأخير من أول جزأين من رقم تسجيل CAS مرات 1 ، الرقم السابق مضروبًا في 2 ، الرقم السابق مضروبًا في 3 وما إلى ذلك ، مع إضافة كل ذلك وحساب مقياس الجمع 10.

في علم التشفير ، يدعم الحساب المعياري بشكل مباشر أنظمة المفاتيح العامة مثل RSA و Diffie-Hellman ، ويوفر مجالات محدودة تكمن وراء المنحنيات الناقصية ، ويستخدم في مجموعة متنوعة من خوارزميات المفاتيح المتماثلة بما في ذلك معيار التشفير المتقدم (AES) ، وخوارزمية تشفير البيانات الدولية ( IDEA) و RC4. يستخدم RSA و Diffie-Hellman الأس المعياري.

في جبر الكمبيوتر ، يشيع استخدام الحساب النمطي للحد من حجم معاملات الأعداد الصحيحة في الحسابات والبيانات الوسيطة. يتم استخدامه في عامل متعدد الحدود ، وهي مشكلة تستخدم فيها جميع الخوارزميات الفعالة المعروفة الحساب المعياري. يتم استخدامه من قبل أكثر التطبيقات كفاءة للمقسوم المشترك الأكبر متعدد الحدود والجبر الخطي الدقيق وخوارزميات أساس Gröbner على الأعداد الصحيحة والأرقام المنطقية. كما تم نشره على Fidonet في الثمانينيات وأرشفته في Rosetta Code ، تم استخدام الحساب المعياري لدحض تخمين أويلر لمجموع القوى على كمبيوتر Sinclair QL الصغير باستخدام ربع الدقة الصحيحة التي استخدمها الكمبيوتر الفائق CDC 6600 لدحض ذلك قبل عقدين من الزمن عبر بحث القوة الغاشمة. [9]

في علوم الكمبيوتر ، غالبًا ما يتم تطبيق الحساب النمطي في عمليات البت والعمليات الأخرى التي تتضمن هياكل بيانات دورية ذات عرض ثابت. عملية modulo ، كما تم تنفيذها في العديد من لغات البرمجة والآلات الحاسبة ، هي تطبيق حسابي معياري يستخدم غالبًا في هذا السياق. يجمع العامل المنطقي XOR 2 بت ، modulo 2.

في الموسيقى ، يتم استخدام المقياس الحسابي 12 في النظر في نظام المزاج المتساوي ذي الاثني عشر نغمة ، حيث يحدث التكافؤ الأوكتاف والتناغمي (أي أن النغمات في نسبة 1∶2 أو 2∶1 متكافئة ، و C-حاد هو تعتبر نفس D-flat).

توفر طريقة إخراج التسعات فحصًا سريعًا للحسابات الحسابية العشرية التي يتم إجراؤها يدويًا. وهو يعتمد على المقياس الحسابي المعياري 9 ، وعلى وجه التحديد على الخاصية الجوهرية وهي 10 ≡ 1 (نموذج 9).

يتم استخدام المقياس الحسابي 7 في الخوارزميات التي تحدد يوم الأسبوع لتاريخ معين. على وجه الخصوص ، فإن تطابق Zeller وخوارزمية Doomsday يستخدمان بشكل مكثف حساب modulo-7.

بشكل عام ، الحساب النمطي له أيضًا تطبيق في تخصصات مثل القانون (على سبيل المثال ، التقسيم) ، والاقتصاد (على سبيل المثال ، نظرية الألعاب) وغيرها من مجالات العلوم الاجتماعية ، حيث يلعب التقسيم النسبي وتخصيص الموارد جزءًا أساسيًا من التحليل.

نظرًا لأن الحساب النمطي له مجموعة كبيرة من التطبيقات ، فمن المهم معرفة مدى صعوبة حل نظام التطابق. يمكن حل نظام التطابق الخطي في وقت متعدد الحدود باستخدام شكل من أشكال الحذف الغاوسي ، لمزيد من التفاصيل انظر نظرية التطابق الخطي. توجد أيضًا خوارزميات ، مثل تقليل مونتغمري ، للسماح بعمليات حسابية بسيطة ، مثل معامل الضرب والأسي ن ، ليتم إجراؤها بكفاءة على أعداد كبيرة.

يبدو أن بعض العمليات ، مثل العثور على لوغاريتم منفصل أو تطابق تربيعي ، صعبة مثل عامل الأعداد الصحيحة ، وبالتالي فهي نقطة انطلاق لخوارزميات التشفير والتشفير. قد تكون هذه المشاكل NP وسيطة.

حل نظام المعادلات الحسابية المعيارية غير الخطية هو NP الكامل. [10]

فيما يلي ثلاث دالات C سريعة بشكل معقول ، اثنتان لأداء الضرب النمطي وواحد للأسي المعياري على الأعداد الصحيحة غير الموقعة التي لا تزيد عن 63 بت ، دون تجاوز العمليات العابرة.

طريقة حسابية لحساب أ ⋅ ب (تعديل م) >> : [11]

في معماريات الكمبيوتر حيث يتوفر تنسيق دقيق ممتد مع 64 بت على الأقل من الجزء العشري (مثل النوع المزدوج الطويل لمعظم برامج التحويل البرمجي x86 C) ، يكون الروتين التالي [ التوضيح المطلوب ] ، من خلال استخدام الحيلة التي تؤدي ، عن طريق الأجهزة ، إلى أن مضاعفة الفاصلة العائمة تؤدي إلى الاحتفاظ بأهم بتات المنتج ، بينما ينتج عن الضرب الصحيح أقل البتات أهمية: [ بحاجة لمصدر ]

يوجد أدناه دالة C لأداء الأس المعياري ، والذي يستخدم mul_mod تم تنفيذ الوظيفة أعلاه.

طريقة حسابية لحساب أ ب (تعديل م) < pmod >> :

ومع ذلك ، لكي تعمل جميع الإجراءات المذكورة أعلاه ، م يجب ألا يتجاوز 63 بت.


قابل للقسمة

سنشرح هنا معنى 1 mod 3 ونوضح كيفية حسابه. 1 mod 3 هو اختصار لـ 1 modulo 3 ويمكن أن يُطلق عليه أيضًا 1 modulus 3.

Modulo هي عملية إيجاد الباقي عند قسمة رقمين. لذلك ، عندما تسأل "ما هو 1 mod 3؟" أنت تسأل "ما هو الباقي عندما تقسم 1 على 3؟".

سنوضح لك طريقتين لإيجاد 1 mod 3 (1 modulo 3). للتمييز بين أساليبنا ، سوف نسميها "طريقة Modulo" و "طريقة المعامل".


قبل أن نكمل ، نذكرك بما تسمى الأجزاء المختلفة من مشكلة القسمة حتى تتمكن من المتابعة: التوزيعات / المقسوم عليها = الحاصل وفي هذه الحالة 1 هو العائد ، 3 هو القاسم ، والإجابة تسمى الحاصل .

علاوة على ذلك ، فإن حاصل القسمة x.y يتكون من جزأين: الجزء الكامل x على يسار الفاصلة العشرية ، و y على يمين العلامة العشرية هو الجزء الكسري.

طريقة مودولو
للعثور على 1 mod 3 باستخدام طريقة Modulo ، نقسم أولاً العائد (1) على المقسوم (3).

ثانيًا ، نضرب الجزء الكامل من حاصل القسمة في الخطوة السابقة في القاسم (3).

ثم أخيرًا ، نطرح الإجابة في الخطوة الثانية من العائد (1) للحصول على الإجابة. إليك الرياضيات لتوضيح كيفية الحصول على 1 mod 3 باستخدام طريقة Modulo الخاصة بنا:

1 / 3 = 0.333333
0 × 3 = 0
1 - 0 = 1

وبالتالي ، فإن الإجابة على السؤال "ما هو 1 mod 3؟" يكون 1.


طريقة المعامل
لإيجاد 1 mod 3 باستخدام طريقة المعامل ، نجد أولاً المضاعف الأكبر للمقسوم عليه (3) الذي يساوي أو أقل من العائد (1).

بعد ذلك ، نطرح أكبر مضاعف للمقسوم عليه من المقسوم لنحصل على الإجابة على 1 معامل 3 (1 mod 3):

مضاعفات 3 هي 0 ، 3 ، 6 ، 9 ، إلخ. والمضاعف الأعلى لـ 3 يساوي أو أقل من 1 هو 0. لذلك ، للحصول على الإجابة:

وهكذا ، مرة أخرى ، الجواب على "ما هو 1 mod 3؟" يكون 1.

Modulo حاسبة
هل لديك مشكلة "تعديل" أخرى تحتاج إلى حل؟ إذا كان الأمر كذلك ، يرجى إدخاله هنا.


ما هو 1 mod 4؟
اذهب هنا للحصول على Modulo للمشكلة التالية في كتاب حل الرياضيات الخاص بنا.


كثيرا ما تستخدم Miniwebtools:

إذا كنت تحب Modulo Calculator ، فيرجى التفكير في إضافة رابط لهذه الأداة عن طريق نسخ / لصق الكود التالي:

قدم لنا معروفًا وأجب عن 3 أسئلة سريعة

شكرا لك لمشاركتك في بحثنا. ستساعدنا مدخلاتك على تحسين خدماتنا.

دعم MINIWEBTOOL

ننفق الكثير من الوقت والمال كل عام حتى تتمكن من الوصول مجانًا إلى مئات الأدوات والآلات الحاسبة. أصبح هذا ممكنا فقط بفضل الإعلان على موقعنا.

الرجاء مساعدتنا في الاستمرار في تزويدك بأدوات مجانية عالية الجودة عبر الإنترنت عن طريق التخلص من أداة منع الإعلانات أو الاشتراك في الإصدار المميز الخالي من الإعلانات بنسبة 100٪. للحصول على إرشادات حول كيفية تعطيل مانع الإعلانات ، انقر هنا.


الحساب المعياري

الحساب النمطي هو ، بشكل عام ، نظام حسابي للأعداد الصحيحة ، حيث الأرقام والالتفاف حول & اقتباس عدد معين. دعونا نلخص ما تعلمناه حول التمثيلات المختلفة لعمليات النموذج - كل هذه العبارات أدناه مكافئة:

  • أ & # x2261 ب (عصري ج)
  • A mod C = B mod C
  • ج | (أ - ب)
  • A = B + K * C حيث K عدد صحيح

يمكننا أيضًا إجراء حسابات على عمليات modulo.

1. الجمع والطرح المعياري

(A + B) mod C = (A mod C + B mod C) mod C

(A - B) mod C = (A mod C - B mod C) mod C

لذا ، فإن مقياس مجموع رقمين يساوي مجموع مقياس هذين الرقمين المحسوب بشكل منفصل ، ثم يضرب في المقسوم عليه. تتم المرحلة الأولى للتخلص من حاصل القسمة ، ثم يتم استخدام عملية التعديل مرة أخرى. ألق نظرة على المثال:

(11 + 7) mod 4 = (11 mod 4 + 7 mod 4) mod 4

الجزء الأيسر من المعادلة: (11 + 7) تعديل 4 = 18 تعديل 4 = 2

الجزء الأيمن من المعادلة: (11 mod 4 + 7 mod 4) mod 4 = (3 + 3) mod 4 = 6 mod 4 = 2

بشكل تناظري ، الحسابات هي نفسها للطرح.

2. الضرب النمطي

(A * B) mod C = (A mod C * B mod C) mod C

قد تكون هذه المعادلة مفيدة عند التعامل مع الأعداد الكبيرة ، ونحن لا نعرف نمط هذا العدد الكبير على الفور. دع & aposs يلقي نظرة على نفس المثال (A = 11 ، B = 7 ، C = 4) - هل يمكنك العثور على نتيجة 77 mod 4 على الفور؟ 11 mod 4 و 7 mod 4 أسهل في الحساب:

(11 * 7) تعديل 4 = (11 وحدة نمطية 4 * 7 تعديل 4) تعديل 4

الجزء الأيسر من المعادلة: (11 * 7) تعديل 4 = 77 تعديل 4 = 1

الجزء الأيمن من المعادلة: (11 mod 4 * 7 mod 4) mod 4 = (3 * 3) mod 4 = 9 mod 4 = 1

A ^ B mod C = ((A mod C) ^ B) mod C

هذه الصيغة مفيدة أكثر عند التعامل مع الأعداد الكبيرة. ضع في اعتبارك نفس المثال:

(11 ^ 7) تعديل 4 = ((11 نموذجًا 4) ^ 7) تعديل 4

الجزء الأيسر من المعادلة: (11 ^ 7) تعديل 4 = 19487171 تعديل 4 = 3

الجزء الأيمن من المعادلة: ((11 mod 4) ^ 7) mod 4 = (3 ^ 7) mod 4 = 2187 mod 4 = 3

قد لا تكون فائدة هذه الصيغة واضحة جدًا في هذا المثال ، لأننا ما زلنا بحاجة إلى استخدام الآلة الحاسبة للعثور على نتيجة الأس (على افتراض أنك لا تعرف نتيجة 3 ^ 7 على الفور). لذا ألقِ نظرة على مشكلة أخرى: نريد حساب A ^ B mod C لقيم B الكبيرة - مثل ، على سبيل المثال 100. للأسف ، يمكن للآلة الحاسبة الخاصة بنا أن تتعامل مع أرقام كبيرة مثل هذا بسبب الفائض - فقط الأرقام حتى 2 ^ 60 يمكن الاحتفاظ بها. ومع ذلك ، يمكنك استخدام خصائص الضرب للتغلب على هذه المشكلة:

2 ^ 100 mod 3 = (2 ^ 50 mod 3 * 2 ^ 50 mod 3) mod 3

2 ^ 100 وحدة نمطية 3 = (1 * 1) تعديل 3 = 1

توجد طرق الأس المعيارية الأسرع لبعض الحالات المحددة (إذا كانت B هي قوة 2). إذا كنت ترغب في القراءة عنها وممارسة الحساب المعياري ، فاطلع على برنامج تعليمي رائع من Khan Academy يسمى ما هو الحساب المعياري؟


عملية modulo هي طريقة لتحديد ما تبقى من عملية القسمة. تُرجع عملية Modulo باقي العدد الصحيح بدلاً من مجرد إرجاع نتيجة القسمة.

  1. اختر ال الرقم الأولي (توزيعات ارباح)
  2. اختر ال المقسوم عليه
  3. قسّم رقمًا على الآخر وأسقط الرقم بعد النقطة (الجزء الكسري)
  4. اضرب المقسوم عليه بالنتيجة بعد التقسيم السابق
  5. اطرح هذا الرقم من الرقم الأولي ونتيجة لعملية modulo
  • الرقم الأولي - 25
  • المقسوم عليه - 7
  • 25 / 7 = 3.5714
  • 7 * 3 = 21
  • 25 - 21 = 4

لذلك ، نتيجة 25 وحدة تركيبية 7 العملية تساوي 4.


عملية Modulo

عملية Modulo هي عملية مهمة للبرمجة. عادة ما يتم تمثيل هذه العملية باسم أو MOD. نلتقي بهذه العملية عندما يكون النطاق الرقمي لمشكلة ما كبيرًا ونحتاج إلى إرجاع النتيجة الحقيقية بعض القيمة MOD لتجنب تجاوز الفائض عند إجراء حساب صحيح. في بعض الحالات ، تؤدي عملية modulo إلى فوز & apost بتغيير النتيجة النهائية. تستخدم بعض خوارزميات التشفير modulo بكثافة. لذا فإن الشخصيات وقواعد التشغيل في modulo مهمة للغاية.

في هذا الفصل ، سنتحدث بشكل أساسي عن قواعد تشغيل modulo.


تعليقات القراء

عندما بدأت البرمجة لأول مرة ، اعتقدت أن مشغل MOD هو الشيء الأكثر روعة وروعة وإثارة للاهتمام. ما زلت أحبه حتى يومنا هذا. شكرا للكتابة عنها تحصل أيضًا على نقاط براوني إضافية لإضافة المزيد من الرياضيات. :-)

نعم ، مشغل mod رائع تمامًا :) إنه أحد المشغلين المفضلين لدي (والذي قد يكون أفضل شيء أقوله طوال اليوم).

هاها. يمكنك أن تكون غريب الأطوار ، هذا جيد. أنا غريب الأطوار طوال اليوم ، كل يوم ، على الأرجح ، لكن الأمر أصبح سيئًا للغاية معي ، لدرجة أنني لم أعد ألاحظ ذلك حقًا ، ولم أتعرف عليه عندما أكون كذلك.

إذا قمت بالتحرك من -6 إلى 6 ، فبدلاً من 1 إلى 15 ، ستلاحظ أن٪ هو في الواقع عامل تشغيل متبقي ، وليس نمطًا حقيقيًا. في الوضع الحقيقي ، -5٪ 3 سيكون 1 ، وليس -2.

يمكن أن يحدث فرقًا إذا كنت تحاول إنشاء رقم عشوائي داخل نطاق. لنفترض أنك تريد إنشاء رقم عشوائي في النطاق من 0 إلى 59 ، لتمثيل عدد الثواني التي يجب انتظارها قبل القيام بشيء ما. عادة ، 60٪ يفعلون ذلك بشكل جيد. ولكن إذا كان المعامل الأول سالبًا بطريقة أو بأخرى ، فستحصل بدلاً من ذلك على رقم في النطاق من -59 إلى 0.

مجرد شيء احترس منه.

قد يكون هذا مرئيًا أكثر قليلاً. التحول إلى رمز لخط أحادي.

  • الباقي مقابل المعادلة الحقيقية:
  • i 3 i٪ 3 صحيح أنا mod 3
  • -6 -2 0 0
  • -5 -1 -2 1
  • -4 -1 -1 2
  • -3 -1 0 0
  • -2 0 -2 1
  • -1 0 -1 2
  • 0 0 0 0
  • 1 0 1 1
  • 2 0 2 2
  • 3 1 0 0
  • 4 1 1 1
  • 5 1 2 2
  • 6 2 0 0

يمكنك أن تأخذ حاصل قسمة عدد صحيح مضروبًا في المقسوم وتضيف الباقي للحصول على المقسوم على جانبي 0.

لا يمكنك فعل ذلك باستخدام modulo حقيقي.

عفوًا. أتمنى أن تسمح مسبقًا بالإضافة إلى الكود.

Ben ، لقد نسيت أن أذكر أنني أحب المشغلين الآخرين أيضًا. إنه فقط في الوقت الذي وصلت فيه إلى مشغل التصميم ، كنت قد استخدمت الآخرين كثيرًا ، لقد سئمت منهم للتو. كانوا نوعًا ما مثل الأخبار القديمة في تلك المرحلة. لكن ما زلت أحبهم. مجرد التفكير في المود هو رائع للغاية. (ويمكن أن يكون مفيدًا لكثير من الحلول لمشاكل مختلفة لا يمكنك حلها بسهولة بطرق أخرى).

نستخدم MOD لوضع الأشياء في صف ، بعرض ثلاثة أعمدة. وبالتالي ، إذا كان هناك ثمانية عناصر ، فإن الناتج يبدو كما يلي:
1 2 3
4 5 6
7 8
هل هذا ما دفع بهذا المنصب يا بن؟

من المضحك أن تذكر ذلك - لم أفكر أبدًا في الأرقام السلبية. أعلم أن هذا يبدو غريبًا ، لكن لا يمكنني حتى أن أتذكر آخر مرة اضطررت فيها حقًا إلى التعامل مع الأرقام السالبة. . أنا متأكد من أن هذه فكرة سخيفة - أنا متأكد من أنني استخدمها طوال الوقت :)

هذا هو نوع الموقف الذي بدأت فيه حقًا في استخدام MOD لأول مرة على أساس منتظم. عندما كنت أستخدم علامات الجدول لوضع الأشياء ، على وجه الخصوص ، أتذكر أنني اعتدت استخدام مشغل MOD لتحديد المكان الذي يجب أن أضيف فيه علامات الإغلاق / الفتح TR.

هناك طريقة أخرى مفيدة بشكل خاص لاستخدام عامل التشغيل MOD وهي تقسيم العناصر إلى عدد عشوائي من الأعمدة. لنفترض أن لديك عددًا غير معروف من العناصر وتريد عرضها في ثلاثة أعمدة متساوية بشكل معقول ، فستقسم عدد العناصر على عدد الأعمدة ، وتقريبها لأعلى أو لأسفل (لذلك أنت تعمل مع عدد صحيح) ، وتبدأ عمود جديد عندما يكون MODULUS الخاص بك صفرًا.

أعتقد أن تقسيم الأعمدة والصفوف كان في الواقع من أول الأشياء التي استخدمتها في الإنتاج. أتذكر بشكل غامض وجود رمز مثل:

  • & lttr & GT
  • & ltcfloop query = & quotfoo & quot & gt
  • & lttd & gt .. & lt / td & gt
  • & ltcfif! (foo.currentRow mod 3) & GT
  • & lt! - ابدأ صفًا جديدًا. - & GT
  • & lt / tr & gt & lttr & gt
  • & lt / cfif & gt
  • & lt / cfloop & gt
  • & lt / tr & gt

@ بن
هذا ما سيبدو عليه الرمز. كنت أفكر ، على سبيل المثال ، في ثلاثة عناصر DIV عائمة لليسار مع قوائم غير مرتبة تحتوي على العناصر التي تريد عرضها. في هذه الحالة ، لا يكون قاسم معاملك ثابتًا ، ولكن يتم حسابه بناءً على عدد السجلات.

أفترض أنه يمكنك أيضًا القيام بهذا النوع من الأشياء باستخدام المقالات الإخبارية أو الإعلانات المبوبة استنادًا إلى عدد & quotinches & quot لكل مقال أو بعض الوحدات التعسفية الأخرى لقياس الطول ، وبالتالي محاكاة التخطيط العمودي للصحيفة.

ماذا عن تسلسل مثل هذا؟
كيف يمكنك أن تذهب نحو ذلك؟
45678123
أو
891234567


محتويات

ال جزء لا يتجزأ أو جزء صحيح من رقم (طرف كامل في الأصل) تم تعريفه لأول مرة في عام 1798 من قبل Adrien-Marie Legendre في إثباته لصيغة Legendre.

قدم كارل فريدريش جاوس تدوين الأقواس المربعة [x] < displaystyle [x]> في برهانه الثالث على المعاملة بالمثل من الدرجة الثانية (1808). [3] ظل هذا هو المعيار [4] في الرياضيات حتى قدم كينيث إي. إيفرسون في كتابه عام 1962 لغة برمجة، والأسماء "floor" و "السقف" والرموز المقابلة لها ⌊ x ⌋ < displaystyle lfloor x rfloor> و ⌈ x ⌉ < displaystyle lceil x rceil>. [5] [6] يتم استخدام كلا الترميزين الآن في الرياضيات ، [7] على الرغم من أنه سيتم اتباع تدوين إيفرسون في هذه المقالة.

أمثلة تحرير

تحرير التنضيد

عادةً ما يتم كتابة وظائف الأرضية والسقف بأقواس مربعة على اليسار واليمين ، حيث تكون الأعمدة العلوية (لوظيفة الأرضية) أو السفلية (لوظيفة السقف) مفقودة (⌊ ⌋ للأرضية و ⌈ ⌉ للسقف). يتم توفير هذه الأحرف في Unicode:

  • U + 2308 ⌈ السقف الأيسر (HTML & amp # 8968 · & ampLeftCeiling & ampLeftCeiling)
  • U + 2309 ⌉ السقف الأيمن (HTML & amp # 8969 · & amprceil و ampRightCeiling)
  • U + 230A ⌊ LEFT FLOOR (HTML & amp # 8970 · & ampLeftFloor و & amplefloor)
  • U + 230B ⌋ الطابق الأيمن (HTML & amp # 8971 · & amprfloor و ampRightFloor)

بالنظر إلى الأعداد الحقيقية x و ذ، الأعداد الصحيحة ك, م, ن ومجموعة الأعداد الصحيحة Z > , floor and ceiling may be defined by the equations

Since there is exactly one integer in a half-open interval of length one, for any real number x, there are unique integers م و ن satisfying the equation

Equivalences Edit

These formulas can be used to simplify expressions involving floors and ceilings. [11]

In the language of order theory, the floor function is a residuated mapping, that is, part of a Galois connection: it is the upper adjoint of the function that embeds the integers into the reals.

These formulas show how adding integers to the arguments affects the functions:

The above are never true if ن is not an integer however, for every x and y , the following inequalities hold:

Relations among the functions Edit

It is clear from the definitions that

In fact, for integers ن, both floor and ceiling functions are the identity:

Negating the argument switches floor and ceiling and changes the sign:

Negating the argument complements the fractional part:

The floor, ceiling, and fractional part functions are idempotent:

The result of nested floor or ceiling functions is the innermost function:

due to the identity property for integers.

Quotients Edit

لو م و ن are integers and ن ≠ 0,

لو ن is a positive integer [12]

إلى عن على م = 2 these imply

More generally, [14] for positive م (See Hermite's identity)

The following can be used to convert floors to ceilings and vice versa (م positive) [15]

للجميع م و ن strictly positive integers: [16] [ أفضل مصدر مطلوب ]

which, for positive and coprime م و ن, reduces to

Since the right-hand side of the general case is symmetrical in م و ن, this implies that

بشكل عام ، إذا م و ن are positive,

This is sometimes called a reciprocity law. [17]

Nested divisions Edit

For positive integer ن, and arbitrary real numbers م,x: [18]

Continuity and series expansions Edit

Since none of the functions discussed in this article are continuous, none of them have a power series expansion. Since floor and ceiling are not periodic, they do not have uniformly convergent Fourier series expansions. The fractional part function has Fourier series expansion [19]

At points of discontinuity, a Fourier series converges to a value that is the average of its limits on the left and the right, unlike the floor, ceiling and fractional part functions: for ذ fixed and x a multiple of ذ the Fourier series given converges to ذ/2, rather than to x عصري ذ = 0. At points of continuity the series converges to the true value.

Using the formula floor(x) = x − يعطي

Mod operator Edit

For an integer x and a positive integer ذ, the modulo operation, denoted by x عصري ذ, gives the value of the remainder when x is divided by ذ. This definition can be extended to real x و ذ, ذ ≠ 0, by the formula

Then it follows from the definition of floor function that this extended operation satisfies many natural properties. على وجه الخصوص ، x عصري ذ is always between 0 and ذ, i.e.,

and if ذ is negative,

Quadratic reciprocity Edit

Gauss's third proof of quadratic reciprocity, as modified by Eisenstein, has two basic steps. [20] [21]

يترك ص و ف be distinct positive odd prime numbers, and let

First, Gauss's lemma is used to show that the Legendre symbols are given by

The second step is to use a geometric argument to show that

Combining these formulas gives quadratic reciprocity in the form

There are formulas that use floor to express the quadratic character of small numbers mod odd primes ص: [22]

Rounding Edit

Number of digits Edit

The number of digits in base ب of a positive integer ك يكون

Factors of factorials Edit

يترك ن be a positive integer and ص a positive prime number. The exponent of the highest power of ص that divides ن! is given by a version of Legendre's formula [23]

Beatty sequence Edit

The Beatty sequence shows how every positive irrational number gives rise to a partition of the natural numbers into two sequences via the floor function. [24]

Euler's constant (γ) Edit

There are formulas for Euler's constant γ = 0.57721 56649 . that involve the floor and ceiling, e.g. [25]

Riemann zeta function (ζ) Edit

The fractional part function also shows up in integral representations of the Riemann zeta function. It is straightforward to prove (using integration by parts) [26] that if ϕ ( x ) is any function with a continuous derivative in the closed interval [أ, ب],

Letting ϕ ( n ) = n − s ^<-s>> for real part of س greater than 1 and letting أ و ب be integers, and letting ب approach infinity gives

This formula is valid for all س with real part greater than −1, (except س = 1, where there is a pole) and combined with the Fourier expansion for <x> can be used to extend the zeta function to the entire complex plane and to prove its functional equation. [27]

إلى عن على س = σ + هو - هي in the critical strip 0 < σ < 1,

In 1947 van der Pol used this representation to construct an analogue computer for finding roots of the zeta function. [28]

Formulas for prime numbers Edit

One may also give formulas for producing the prime numbers. For example, let صن كن ال ن-th prime, and for any integer ص > 1, define the real number α by the sum

A similar result is that there is a number θ = 1.3064. (Mills' constant) with the property that

There is also a number ω = 1.9287800. with the property that

Let π (x) be the number of primes less than or equal to x. It is a straightforward deduction from Wilson's theorem that [32]

None of the formulas in this section are of any practical use. [34] [35]

Solved problems Edit

Ramanujan submitted these problems to the Journal of the Indian Mathematical Society. [36]

لو ن is a positive integer, prove that

Unsolved problem Edit

The study of Waring's problem has led to an unsolved problem:

Are there any positive integers ك ≥ 6 such that [37]

Mahler [38] has proved there can only be a finite number of such ك none are known.

In most programming languages, the simplest method to convert a floating point number to an integer does not do floor or ceiling, but truncation. The reason for this is historical, as the first machines used ones' complement and truncation was simpler to implement (floor is simpler in two's complement). FORTRAN was defined to require this behavior and thus almost all processors implement conversion this way. Some consider this to be an unfortunate historical design decision that has led to bugs handling negative offsets and graphics on the negative side of the origin. [ بحاجة لمصدر ]

Many programming languages (including C, C++, [39] [40] C#, [41] [42] Java, [43] [44] PHP, [45] [46] R, [47] and Python [48] ) provide standard functions for floor and ceiling, usually called floor and ceil , or less commonly ceiling . [49] The language APL uses ⌊x for floor. The J Programming Language, a follow-on to APL that is designed to use standard keyboard symbols, uses <. for floor and >. for ceiling. [50] ALGOL uses entier for floor.

Spreadsheet software Edit

Most spreadsheet programs support some form of a ceiling function. Although the details differ between programs, most implementations support a second parameter—a multiple of which the given number is to be rounded to. For example, ceiling(2, 3) rounds 2 up to the nearest multiple of 3, giving 3. The definition of what "round up" means, however, differs from program to program.

Microsoft Excel used almost exactly the opposite of standard notation, with INT for floor, and FLOOR meaning round-toward-zero, and CEILING meaning round-away-from-zero. [51] This has followed through to the Office Open XML file format. Excel 2010 now follows the standard definition. [52]