خانه ویکی

معکوس پیمانه ای

معکوس پیمانه ای عدد $a$ به پیمانه $m$ ، عددی است مثل $x$ چنان که

به عدد $x$ ، $a^{-1}$ نیز می گویند.

محاسبه معکوس با الگوریتم اقلیدس

معادله زیر را در نظر بگیرید( $x$ و $y$ مجهول هستند ):

این یک معادله دیوفانتی خطی با دو متغیر است. با استفاده از الگوریتم گسترده اقلیدس می توان جواب این معادله را بدست آورد.

int x, y;
int g = extended_euclidean(a, m, x, y);
if (g != 1) {
    cout << "No solution!";
}
else {
    x = (x % m + m) % m;
    cout << x << endl;
}

محاسبه معکوس با قضیه اویلر

طبق قضیه اویلر:

دو طرف را در $a^{-1}$ ضرب می کنیم:

که اگر $m$ عددی اول باشد:

پس می توانیم در $O(\log m)$ معکوس پیمانه ای را به کمک الگوریتم توان به دست آوریم.

محاسبه کسر ها به پیمانه $m$

در بعضی از سوال ها که پاسخشان عددی گویا است، از شما به جای نمایش اعشاری کسر $\frac{p}{q}$ مقدار $p\cdot q^{-1} \mod m$ خواسته می شود. با توجه به این که :

و این که :

می توانیم هنگام جمع و ضرب دو کسر عدد همنهشت با آن ها به پیمانه $m$ را جمع و ضرب کنیم و هنگام تقسیم ، معکوس عدد همنهشت با مخرج را در صورت ضرب کنیم و به این صورت عدد همنهشت با یک کسر به پیمانه $m$ را بدست آوریم.