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

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

בהינתן שני מספרים שלמים $a,b$ ומודולוס $m$, תוצאת החילוק המודולרי של $b$ ב־$a$ היא מספר $z$ המקיים:

$az\equiv b{\pmod {m}}$

למשל

$6\equiv 2/3{\pmod {8}}$

כי

$6\cdot 3=18\equiv 2{\pmod {8}}$

קיום ויחידות

בניגוד לשלוש פעולות החשבון האחרות, תוצאת החילוק המודולרי לא תמיד קיימת. למשל, המספר $1/2{\pmod {8}}$ אינו קיים, כי אין $z$ שלם עבורו $2z\equiv 1{\pmod {8}}$.

תנאי הכרחי ומספיק לכך שהתוצאה תתקיים היא, שהמ.מ.ג.ב $\gcd(a,m)=d$ מחלק את $b$.

בדוגמה למעלה, המ.מ.ג.ב של 8 ו־2 הוא 2, והמחולק 1 אינו מתחלק ב־2, ולכן תוצאת החילוק אינה קיימת.

בניגוד לשלוש פעולות החשבון האחרות, תוצאת החילוק המודולרי אינה בהכרח יחידה. למשל:

$2/6\equiv 3\equiv 7{\pmod {8}}$

כי $6\cdot 7=42\equiv 2{\pmod {8}}$.

באופן כללי, אם $z\equiv b/a{\pmod {m}}$ אזי לכל מספר שלם $k$

$z+k\cdot {\frac {m}{\gcd(a,m)}}\equiv b/a{\pmod {m}}$

כי לכל $k$ מתקיים

$a\cdot \left(z+k\cdot {\frac {m}{\gcd(a,m)}}\right)\equiv az+k\cdot {\frac {a}{\gcd(a,m)}}\cdot m\equiv az\equiv a{\pmod {m}}$

תוצאת החילוק היא יחידה מודולו המספר ${\frac {m}{\gcd(a,m)}}$.

חישוב

ניתן לחשב חילוק מודולרי על ידי חישוב הופכי כפלי מודולרי של המחלק $a$, אם הוא קיים. בפרט, אם $a^{-1}$ הוא ההופכי הכפלי המודולרי של $a$ מודולו $m$, אז על־פי ההגדרה:

${\begin{aligned}a^{-1}\cdot a\equiv 1{\pmod {m}}\\b\cdot a^{-1}\cdot a\equiv b{\pmod {m}}\end{aligned}}$

ומכאן

$z\equiv b\cdot a^{-1}{\pmod {m}}$

אולם, ישנם מקרים שבהם ההופכי הכפלי המודולרי אינו קיים – כאשר ל־$a,m$ ישנו מחלק משותף גדול מ־1 (ראו הופכי כפלי מודולרי), ועדיין ניתן לבצע חילוק. לפיכך טוב יותר לבצע חילוק ישירות בעזרת אלגוריתם אוקלידס המורחב. אלגוריתם זה מוצא את המ.מ.ג.ב של שני מספרים נתונים, ובנוסף לכך מחשב שני מספרים $x,y$ המקיימים את המשוואה:

$ax+my=d=\gcd(a,m)$

כאמור בסעיף הקודם, ניתן לבצע את החילוק אם ורק אם $b$ הוא כפולה שלמה של $d$, כלומר כאשר קיים מספר שלם $q$ עבורו

$b=qd$

במקרה זה ניתן להכפיל את המשוואה הקודמת ב־$q$ ולקבל:

$aqx+mqy=qd=b$

מכאן, על־פי הגדרת החשבון המודולרי:

$aqx\equiv b{\pmod {m}}$

ומכאן $qx$ הוא תוצאת החילוק.

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

/**
 * 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";
	}
}

ראו גם

• הופכי כפלי מודולרי
• חשבון מודולרי
• חילוק

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

• יסודות של תורת המספרים החישובית, רוברט קמפבל, אוניברסיטת UMBC מרילנד.