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

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

בהינתן שני מספרים שלמים a ו-b ומודולוס m, כך ש-b,m זרים, תוצאת החילוק המודולרי של a ב-b היא מספר z המקיים .

לדוגמה,  משום ש-.

קיום ויחידות 

משמעותו של הביטוי  היא "המספר היחיד, z, הפותר את המשוואה ". מספר כזה קיים, כאמור, רק כאשר b,m זרים. 

עם זאת, ייתכן שלמשוואה  יהיו פתרונות גם כאשר b,m אינם זרים. למשוואה יש פתרונות אם ורק אם המחלק המשותף המקסימלי של b,m מחלק את a; ובמקרה כזה, תוצאת החילוק מוגדרת היטב מודולו  (אבל לא מודולו m).

באופן כללי, אם  אז לכל מספר שלם k, מתקיים כי 
.

חישוב 

ניתן לחשב חילוק מודולרי על ידי חישוב הופכי כפלי מודולרי של המחלק b, אם הוא קיים. בפרט, אם  הוא ההופכי הכפלי המודולרי של b מודולו m, אז על-פי ההגדרה:

ומכאן אפשר לחשב את z (תוצאת החילוק של a ב-b):

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

כאמור בסעיף הקודם, ניתן לבצע את החילוק אם ורק אם a הוא כפולה שלמה של gcd(b,m), כלומר, כאשר קיים מספר שלם q המקיים:

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

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

ומכאן ש- 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 מרילנד.

הערות שוליים 

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