محاسبه $ \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 -0600

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

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

نظرات

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

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

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

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

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

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

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

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

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

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

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 -0600

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

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

نظرات

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

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

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

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

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

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

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

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

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

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

2015-07-07 00:16:59 -0600

آرپا 947 ● 13 ● 15 ● 31

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

نظرات

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

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

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

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

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

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

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

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

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

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

آمار پرسش:

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

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

علائم ریاضی:

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

2 پاسخ

پاسخ شما

پیش‌نمایش: