1-محاسبات مدولار

توسط علی رضا نقش نیلچی | چهارشنبه نوزدهم مرداد ۱۴۰۱ | 2:25

از ویکیپدیا، دانشنامه آزاد

این مقاله در مورد نماد (mod n ) است. برای عملیات باینری mod( a,n ) به عملیات مدولو مراجعه کنید .

زمان سنجی در این ساعت از مدول حسابی 12 استفاده می کند. با افزودن 4 ساعت به ساعت 9 ساعت 1 به دست می آید، زیرا 13 با 1 مدول 12 مطابقت دارد.

در ریاضیات ، محاسبات مدولار یک سیستم حسابی برای اعداد صحیح است ، که در آن اعداد با رسیدن به مقدار معینی که مدول نامیده می‌شود، در اطراف خود قرار می‌گیرند. رویکرد مدرن به حساب مدولار توسط کارل فردریش گاوس در کتاب Disquisitiones Arithmeticae که در سال 1801 منتشر شد، توسعه یافت.

یک کاربرد آشنا از محاسبات مدولار در ساعت 12 ساعته است که در آن روز به دو دوره 12 ساعته تقسیم می شود. اگر الان ساعت 7:00 است، 8 ساعت بعد ساعت 3:00 خواهد بود. جمع ساده منجر به 7 + 8 = 15 می شود ، اما ساعت ها هر 12 ساعت به دور خود می پیچند. از آنجایی که عدد ساعت با رسیدن به 12 از صفر شروع می شود، این مدول حسابی 12 است. از نظر تعریف زیر، 15 مطابق با 3 مدول 12 است، بنابراین "15:00" در ساعت 24 ساعته "3" نمایش داده می شود. :00 اینچ در یک ساعت 12 ساعته.

فهرست

همخوانی [ ویرایش ]

با توجه به یک عدد صحیح n > 1 که مدول نامیده می شود ، به دو عدد صحیح a و b گفته می شود که مدول n متجانس هستند، اگر n مقسوم علیه تفاوت آنها باشد (یعنی اگر یک عدد صحیح k وجود داشته باشد به طوری که a - b = kn باشد ). .

مدول همگامی n یک رابطه هم ارزی است، به این معنی که یک رابطه هم ارزی است که با عملیات جمع ، تفریق و ضرب سازگار است . مدول همخوانی n نشان داده می شود:

$a\equiv b{\pmod {n}}.$

پرانتز به این معنی است که (mod n ) برای کل معادله اعمال می شود، نه فقط در سمت راست (اینجا، b ). این نماد نباید با علامت b mod n (بدون پرانتز) که به عملیات مدول اشاره دارد، اشتباه گرفته شود . در واقع، b mod n عدد صحیح منحصر به فرد a را نشان می دهد به طوری که 0 ≤ a < n و $a\equiv b\;({\text{mod}}\;n)$ (یعنی باقیمانده $ب$ وقتی تقسیم بر $n$ ).

رابطه تطابق ممکن است به صورت بازنویسی شود

$a=kn+b,$

رابطه آن را با تقسیم اقلیدسی به صراحت نشان می دهد . با این حال، b در اینجا لازم نیست باقیمانده تقسیم a بر n باشد. در عوض، چیزی که عبارت a ≡ b (mod n ) بیان می کند این است که a و b وقتی بر n تقسیم می شوند باقیمانده یکسانی دارند . به این معنا که،

$a=pn+r،$

$b=qn+r،$

که در آن 0 ≤ r < n باقیمانده مشترک است. با کم کردن این دو عبارت، رابطه قبلی را بازیابی می کنیم:

$ab=kn,$

با تنظیم k = p − q .

مثالها [ ویرایش ]

در مدول 12 می توان ادعا کرد که:

$38\equiv 14{\pmod {12}}$

زیرا 38 − 14 = 24 ، که مضرب 12 است. راه دیگر برای بیان این است که بگوییم هر دو 38 و 14 با تقسیم بر 12 باقیمانده 2 مشابهی دارند.

تعریف همخوانی در مورد مقادیر منفی نیز صدق می کند. مثلا:

${\begin{aligned}2&\equiv -3{\pmod {5}}\\-8&\equiv 7{\pmod {5}}\\-3&\equiv -8{\pmod {5}} .\end{تراز شده}}$

خواص [ ویرایش ]

رابطه هم ارزی تمام شرایط یک رابطه هم ارزی را برآورده می کند :

بازتاب: a ≡ a (mod n )
تقارن: a ≡ b (mod n ) اگر b ≡ a (mod n ) برای همه a , b و n .
گذرا: اگر a ≡ b (mod n ) و b ≡ c (mod n ) , آنگاه a ≡ c ( mod n )

اگر a 1 ≡ b 1 (mod n ) و a 2 ≡ b 2 (mod n ) و یا a ≡ b (mod n ) ، آنگاه: [1]

a + k ≡ b + k (mod n ) برای هر عدد صحیح k (سازگاری با ترجمه)
ka ≡ kb (mod n ) برای هر عدد صحیح k (سازگاری با مقیاس بندی)
ka ≡ kb (mod kn ) برای هر عدد صحیح k
a 1 + a 2 ≡ b 1 + b 2 (mod n ) (سازگاری با جمع)
a 1 – a 2 ≡ b 1 – b 2 (mod n ) (سازگاری با تفریق)
a 1 a 2 ≡ b 1 b 2 (mod n ) (سازگاری با ضرب)
a k ≡ b k (mod n ) برای هر عدد صحیح غیر منفی k (سازگاری با توان)
p ( a ) ≡ p ( b ) (mod n ) ، برای هر چند جمله‌ای p ( x ) با ضرایب صحیح (سازگاری با ارزیابی چند جمله‌ای)

اگر a ≡ b (mod n ) ، آنگاه به طور کلی نادرست است که k a ≡ k b (mod n ) . با این حال، موارد زیر صادق است:

اگر c ≡ d (mod φ ( n ))، که در آن φ تابع تایانت اویلر است ، a c ≡ a d ( mod n ) —به شرطی که a همزمان با n باشد .

برای لغو شرایط رایج، قوانین زیر را داریم:

اگر a + k ≡ b + k (mod n ) ، جایی که k هر عدد صحیحی است، a ≡ b (mod n )
اگر ka ≡ kb (mod n ) و k با n همزمان اول باشد ، a ≡ b (mod n )
اگر ka ≡ kb (mod kn ) و k ≠ 0 , آنگاه a ≡ b (mod n )

معکوس ضربی مدولار با قوانین زیر تعریف می شود:

وجود: یک عدد صحیح با -1 وجود دارد به طوری که aa -1 ≡ 1 (mod n ) اگر و فقط اگر a هم اول با n باشد وجود دارد. این عدد صحیح a –1 ، معکوس ضربی مدولار یک مدول n نامیده می شود .
اگر a ≡ b (mod n ) و a –1 وجود داشته باشد، a –1 ≡ b –1 (mod n ) (سازگاری با معکوس ضربی، و اگر a = b ، مدول یکتایی n ) وجود دارد.
اگر ax ≡ b (mod n ) و a همزمان با n باشد ، آنگاه راه حل این همخوانی خطی با x ≡ a -1 b (mod n ) به دست می آید.

معکوس ضربی x ≡ a –1 (mod n ) را می توان با حل معادله بزوت به طور موثر محاسبه کرد. $ax+ny=1$ برای $x، y$ - با استفاده از الگوریتم اقلیدسی توسعه یافته .

به طور خاص، اگر p یک عدد اول باشد، a برای هر a هم‌آغاز با p است به طوری که 0 < a < p ; بنابراین یک معکوس ضربی برای همه a وجود دارد که با مدول صفر p مطابقت ندارد.

برخی از ویژگی های پیشرفته تر روابط همخوانی به شرح زیر است:

قضیه کوچک فرما : اگر p اول باشد و a را تقسیم نکند ، a p – 1 ≡ 1 (mod p ) .
قضیه اویلر : اگر a و n هم اول باشند، آنگاه a φ ( n ) ≡ 1 ( mod n ) که φ تابع اویلر است.
یک نتیجه ساده از قضیه کوچک فرما این است که اگر p اول باشد، a −1 ≡ a p− 2 (mod p ) معکوس ضربی 0 < a < p است. به طور کلی تر، از قضیه اویلر، اگر a و n هم اول باشند، a −1 ≡ a φ ( n ) − 1 (mod n ) .
نتیجه ساده دیگر این است که اگر a ≡ b (mod φ ( n ))، که در آن φ تابع تاینت اویلر است، آنگاه k a ≡ k b (mod n ) ارائه شده k با n همخوان است .
قضیه ویلسون : p اول است اگر و فقط اگر ( p − 1)! ≡ −1 (mod p ) .
قضیه باقیمانده چینی : برای هر a , b و هم اول m , n , یک x یکتا (mod mn ) وجود دارد به طوری که x ≡ a (mod m ) و x ≡ b ( mod n ) . در واقع، x ≡ bm n –1 m + an m –1 n (mod mn ) که در آن m n -1 معکوس m استمدول n و n m -1 معکوس n مدول m است.
قضیه لاگرانژ : همخوانی f ( x ) ≡ 0 (mod p ) , که در آن p اول است و f ( x ) = a 0 x n + ... + a n چند جمله ای با ضرایب صحیح است به طوری که a 0 ≠ 0 ( mod p ) ، حداکثر n ریشه دارد.
مدول ریشه اولیه n : یک عدد g یک مدول ریشه ابتدایی n است اگر برای هر عدد صحیح یک هم اول به n یک عدد صحیح k وجود داشته باشد به طوری که g k ≡ a (mod n ) باشد. یک مدول ریشه اولیه n وجود دارد اگر و فقط اگر n برابر با 2، 4، pk یا 2 pk باشد ، که در آن p یک عدد اول فرد و k یک عدد صحیح مثبت است. اگر یک مدول ریشه اولیه n وجود داشته باشد، دقیقاً وجود داردφ ( φ ( n )) چنین ریشه های ابتدایی، که در آن φ تابع اویلر است.
باقیمانده درجه دوم : یک عدد صحیح a یک مدول باقیمانده درجه دوم n است، اگر یک عدد صحیح x وجود داشته باشد به طوری که x 2 ≡ a (mod n ) وجود داشته باشد. معیار اویلر بیان می کند که اگر p یک عدد اول فرد باشد و a مضرب p نباشد ، a یک مدول باقیمانده درجه دوم p است اگر و فقط اگر

$a^{(p-1)/2}\equiv 1{\pmod {p}}.$

مشخصات وب

در این وبلاگ به ریاضیات و کاربردهای آن و تحقیقات در آنها پرداخته می شود. مطالب در این وبلاگ ترجمه سطحی و اولیه است و کامل نیست.در صورتی سوال یا نظری در زمینه ریاضیات دارید مطرح نمایید .در صورت امکان به آن می پردازم. من دوست دارم برای یافتن پاسخ به سوالات و حل پروژه های علمی با دیگران همکاری نمایم.در صورتی که شما هم بامن هم عقیده هستید با من تماس بگیرید.
09132003030

ریاضیات

آموزش ریاضی