חילוק מודולרי

חילוק מודולרי הוא פעולת חילוק המתבצעת בין מספרים שלמים בחשבון מודולרי. הפעולה מוגדרת היטב אם ורק אם המחלק זר למודולוס. 

בהינתן שני מספרים שלמים <math>a,b</math> ומודולוס <math>m</math>, כאשר <math>b,m</math> זרים, תוצאת החילוק המודולרי של <math>a</math> ב-<math>b</math> היא מספר <math>c</math> המקיים <math>bc\equiv a\!\!\!\pmod{m}</math>.

לדוגמה, <math>2/3\equiv6\!\!\!\pmod{8}</math> משום ש-<math>6\cdot3=18\equiv2\!\!\!\pmod{8}</math>.

==קיום ויחידות==
משמעותו של הביטוי <math>a/b\!\!\!\pmod{m}</math> היא "המספר היחיד <math>c</math> הפותר את המשוואה <math>bc\equiv a\!\!\!\pmod{m}</math>". מספר כזה קיים, כאמור, רק כאשר <math>b,m</math> זרים. 

עם זאת, ייתכן שלמשוואה <math>bc\equiv a\!\!\!\pmod{m}</math> יהיו פתרונות גם כאשר <math>b,m</math> אינם זרים. למשוואה יש פתרונות אם ורק אם המחלק המשותף המקסימלי של <math>b,m</math> מחלק את <math>a</math>; ובמקרה כזה, תוצאת החילוק מוגדרת היטב מודולו <math>\frac{m}{\gcd\{b,m\}}</math> (אבל לא מודולו <math>m</math>).

באופן כללי, אם <math>c\equiv a/b\!\!\!\pmod{m}</math> אז לכל מספר שלם <math>k</math> מתקיים כי <math>c+k\cdot\frac{m}{\gcd\{b,m\}}\equiv a/b\!\!\!\pmod{m}</math>. 

==חישוב==
ניתן לחשב חילוק מודולרי על ידי חישוב הופכי כפלי מודולרי של המחלק <math>b</math>, אם הוא קיים. בפרט, אם <math>b^{-1}</math> הוא ההופכי הכפלי המודולרי של <math>b</math> מודולו <math>m</math>, אזי על-פי ההגדרה:
:<math>\begin{align}b^{-1}\cdot b\equiv1\!\!\!\pmod{m}\\a\cdot b^{-1}\cdot b\equiv a\!\!\!\pmod{m}\end{align}</math>
ומכאן אפשר לחשב את <math>c</math> (תוצאת החילוק של <math>a</math> ב-<math>b</math>):
:<math>c\equiv a\cdot b^{-1}\!\!\!\pmod{m}</math>
אולם, ישנם מקרים שבהם ההופכי הכפלי המודולרי אינו קיים – כאשר ל-<math>b,m</math> ישנו מחלק משותף גדול מ-1 (ראו הופכי כפלי מודולרי), ועדיין ניתן לבצע חילוק. לפיכך טוב יותר לבצע חילוק ישירות בעזרת אלגוריתם אוקלידס המורחב. אלגוריתם זה מוצא את הממג"ב של שני מספרים נתונים (במקרה זה: <math>b,m</math>), ובנוסף לכך מחשב שני מספרים <math>x,y</math> המקיימים את המשוואה:
:<math>bx+my=\gcd\{b,m\}</math>
כאמור בסעיף הקודם, ניתן לבצע את החילוק אם ורק אם <math>a</math> הוא כפולה שלמה של <math>\gcd\{b,m\}</math>, כלומר כאשר קיים מספר שלם <math>q</math> המקיים:
:<math>a=q\cdot\gcd\{b,m\}</math>
במקרה זה ניתן להכפיל את המשוואה הקודמת ב-<math>q</math> ולקבל:
:<math>bqx+mqy=q\cdot\gcd\{b,m\}=a</math>
מכאן, על-פי הגדרת החשבון המודולרי:
:<math>bqx\equiv a\!\!\!\pmod{m}</math>
ומכאן ש-<math>qx</math> הוא תוצאת החילוק.

לפניכם מימוש מעשי של האלגוריתם בשפת ++C:

<syntaxhighlight lang="cpp">

/**
 * Euclid's extended algorithm:
 * Given a,b, Find gcd,x,y that solve the equation:
 * ax + by = gcd(a,b)
 * @see http://en.wikipedia.org/wiki/Modular_multiplicative_inverse#Computation
 */
void xgcd (int a, int b,
	int& gcd, int& x, int& y)
{
	x=0, y=1; 
	int u=1, v=0, m, n, q, r;
	gcd = b;
	while (a!=0)
 {
		q=gcd/a; r=gcd%a;
		m=x-u*q; n=y-v*q;
		gcd=a; a=r; x=u; y=v; u=m; v=n;
	}
}

/**
 * Modular division:
 * @return integer z such that: z * B mod m == A.
 * If there is more than one (i.e. when gcd(B,m)>1) - returns the smallest such integer
 */
int divide (int A, int B, int m)
{
	assert (0 <= A && A<m);
	assert (0 <= B && B<m);

	int gcd, x, y;
	xgcd (B, m, gcd, x, y); // x B + y m = gcd(B,m)
	if (A%gcd == 0)
 { 
		int q = A / gcd; // x q B + y q m = m gcd = A
		return ((x + m)*q) % (m/gcd); // Return the smallest result possible
	}
 else
 {
		throw "no quotient";
	}
}
</syntaxhighlight>

== ראו גם ==
*הופכי כפלי מודולרי
*חשבון מודולרי
*חילוק

==קישורים חיצוניים==

*[http://userpages.umbc.edu/~rcampbel/NumbThy/Class/BasicNumbThy.html יסודות של תורת המספרים החישובית], רוברט קמפבל, אוניברסיטת UMBC מרילנד.

==הערות שוליים==

קטגוריה:תורת המספרים
קטגוריה:פעולות בינאריות
קטגוריה:חילוק