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

از shaazzz
پرش به ناوبری پرش به جستجو

معکوس پیمانه ای عدد به پیمانه ، عددی است مثل چنان که به عدد ، نیز می گویند.

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

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

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

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;
}

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

طبق قضیه اویلر: دو طرف را در ضرب می کنیم: که اگر عددی اول باشد: پس می توانیم در معکوس پیمانه ای را به کمک الگوریتم توان به دست آوریم.

محاسبه کسر ها به پیمانه [ویرایش]

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