محاسبه $ \left(\frac{a}{b}\right) \space mod \space m $

سلام

مثلا

$$ (a + b) \space mod\space m = (a \space mod\space m + b \space mod\space m) \space mod\space m $$

خوب چنین فرمولی برای ضرب هم درسته و اثبات کردنش ساده هست. ولی جواب این فرمول چی میشه؟

$$ \left(\frac{a}{b}\right) \space mod\space m = chi $$

ممنون می‌شم اگه می‌دونید بگید، و اثبات کنید چرا درسته :heart:

2015-07-06 23:59:30 -0500

توفیقی 1621 ● 17 ● 21 ● 42

پاک‌کردن ویرایش سوال

نظرات

کسی هست امروز به باشگاه زنگ زده باشه؟

2015-07-07 02:28:02 -0500 چشمک

من زنگ زدم گفتن نتایج پنجشنبه ظهر به بعد میاد. چن نفر دیگه ام زنگ زدن همینو گفتن...

2015-07-07 02:37:22 -0500 تتتت

من زنگ میزنم کسی بر نمیداره :|

2015-07-07 02:37:47 -0500 چشمک

اره منم زنگ زدم گفتن پنج شنبه بعد از ظهر به حرفشون اعتباری نیست

2015-07-07 03:22:05 -0500 رصاوووو

بطمظرمن بایدد بخیال شیم یبار هفته بعد بیام شاید تا اون مکقع بیاد تا حالا ده بار حرفشونو عوض کردن

2015-07-07 03:23:24 -0500 رصاوووو

2 پاسخ

نگاه کن ما میخوایم بفهمیم $ \frac{1}{b}$ باقیماندش به m چی میشه $ \frac{1}{b}$ معنیش چیه یعنی این :

$$ \frac{1}{b} * b\space mod \space m =1 $$

خوب حالا دو حالت داریم

1- gcd(b,m)=1

که این جوری

$$ \frac{1}{b}=b^{m-2} $$

یا

$$ \frac{1}{b}=b^{phi(m)-1} $$

یا ...

2- gcd(b,m)!=1

این جوری میخوام اثبات کنم که نداریم همچین چیزی برهان خلف میزنیم که داریم

$$ x * b\space mod \space m =1 $$

$$ b=gcd(b,m)*bb \space m=gcd(m,b) * mm $$

$$ x * bb * gcd(b,m) = mm*gcd(m,b) * k +1 $$

$$ gcd(b,m) * ( x * bb - mm * k ) = 1 $$

از اون جایی که gcd(b,m)>1 و x * bb - mm * k صحیحه بدیهیه که همچین چیزی امکان نداره

2015-07-07 13:07:22 -0500

حمیدرضاه 2979 ● 20 ● 26 ● 52

پاک‌کردن ویرایش پاسخ

نظرات

خیلی کامل و اضافی نوشتم :)

2015-07-07 13:09:10 -0500 حمیدرضاه

ایشالله تو هم طلا شی:)پرچم کاهوییا بالاس.

2015-07-07 13:39:40 -0500 کنکوری

2015-07-07 13:39:55 -0500 کنکوری

کتا ب زرد فاطمی قشنگ توضیح داده...

2015-07-08 01:46:54 -0500 محمد خداداد

$$ (a \times b^{m-2}) \space mod \space m $$

اینجا توضیح داده.

اینجا هم اثبات کرده :)

2015-07-07 00:16:59 -0500

آرپا 947 ● 13 ● 15 ● 31

پاک‌کردن ویرایش پاسخ

نظرات

خوب، الآن طبق اثبات و ... که خوندم، این اثبات، اثبات زیرمسئله‌ای از مسئله‌ی من هست، چون توی این قسمت باید gcd(b, m) = 1 باشه...

2015-07-07 00:50:50 -0500 توفیقی

منم اثباتی که بلدم و شنیدم همین شرطو داره. خب برای مرحله سه چون دلتا عدد اوله جواب میده ولی...

2015-07-07 02:39:38 -0500 تتتت

طبق قضیه کوچک فرما a به توان p-1 به طوری که p اول باشه باقی ماندش به p برابر 1 میشه حالا شما بیا b به توان p-1 رو در a/b ضرب کن باقی مونده به p ثابته دیگه خب ضربشون میشه a در b به توان p-2 مشکل چیه؟

2015-07-07 02:43:55 -0500 احمدرضا

@احمدرضا قضیه‌ی کوچک فرما درسته اگر gcd(b, p) = 1 باشه.

2015-07-07 02:53:42 -0500 توفیقی

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

2015-07-07 02:57:24 -0500 احمدرضا

آمار پرسش:

نکاتی در مورد نوشتن پاسخ:

استفاده از ویرایشگر:

علائم ریاضی:

محاسبه $ \left(\frac{a}{b}\right) \space mod \space m $

2 پاسخ

پاسخ شما

پیش‌نمایش: