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

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

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

לדוגמה, $2/3\equiv 6\!\!\!{\pmod {8}}$ משום ש-$6\cdot 3=18\equiv 2\!\!\!{\pmod {8}}$.

קיום ויחידות

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

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

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

חישוב

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

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

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

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

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

$bx+my=\gcd\{b,m\}$

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

$a=q\cdot \gcd\{b,m\}$

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

$bqx+mqy=q\cdot \gcd\{b,m\}=a$

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

$bqx\equiv a\!\!\!{\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.wiki.x.io/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 מרילנד.