Diophantine Equation
Consider the equation \(ax + by = c\) where $ a, b, c \, \epsilon \, Z $. Now we need to solve for $ x \, and \, y \, \epsilon \, Z $ that satisfy the equation.
Application
- Modular Inverse of a number can be found by transforming \(b*b^{-1}=1 \, mod \, n\) to \(b*b^{-1} + n*n^{-1} = 1\).
- Solving linear diophantine equation.
- RSA Algorithm (used in finding public and private key).
Algorithm
Linear Diophantine Equation can be solved using Extended Euclid Algorithm.
Consider equation \(ax + by = c\). Note, equation has a solution if and only if gcd(a,b) | c.
If x1, y1 is any particular solution of this equation, then all other solution is given
by
\(x = x1 + (b \div d)t, \, y = y1 - (a \div d)t.\)
Detailed proof for the above equation is in David M.Burton number theory book.
Consider base equation for pair \((a,b)\), \(a * x + b*y = g\), where g is gcd(a,b).
Now let us find an solution of the (x1, y1) problem for the new pair (b%a, a):
\((b\%a)*x1 + a*y1 = g,\) Note, \((b\%a) = b - \lfloor b/a \rfloor * a\).
Now after substituting in the above expression, we get \(g = ((b - \lfloor b/a \rfloor * a) * x1 + a * y1)\)
and, performing the regrouping of the terms, we obtain: \(g = b * x1 + a * (y1 - \lfloor b/a \rfloor * x1)\)
So final expression is \(\lbrace x = y1 - \lfloor b/a \rfloor * x1, y = x1 \rbrace\).
Code
/* Global Variable */
int x,y, d;
void extendedEuclid(int a, int b)
{
if(b == 0)
{
x = 1;
y = 0;
d = a;
return;
}
extendedEuclid(b, a % b);
int X1, Y1;
X1 = y;
Y1 = x - (a/b) * y;
x = X1;
y = Y1;
}Related Problems
- SRM 507 DIV 1000