Diophantine Equation Practice

(gcd = greatest common divisor)

1. There is only a solution when gcd( 1027, 712 ) = 1 or in other words 1027 and 712 are relatively prime.

2. Using the Euclidian algorithm to calcutate gcd(1027,712)

$$\small{
\begin{array}{|r|r|r|r|}
\hline
&&&\\
a & b & q& r \\
\hline
&&&\\
1027 & 712 & 1 & 315 \\
712 & 315 & 2 & 82 \\
315 & 82 & 3 & 69 \\
82 & 69 & 1 & 13 \\
69 & 13 & 5 &4 \\
13 & 4 &3 & \textcolor[rgb]{1,0,0}{1} \\
4 & 1 & 4 & 0 \\
&&&\\
\hline
\end{array}
}$$

The greatest common divisor gcd(1027,712) $$\textcolor[rgb]{1,0,0}{=1}$$

and we can go on

3. Using Extended Euclidean algorithm to calculate the first solution

$$\small{
\begin{array}{|r|r|r|r||r|r|}
\hline
&&&&&\\
a & b & q& r &x&y\\
\hline
&&&&&\\
1027 & 712 & 1 & 315 & \textcolor[rgb]{1,0,0}{-165} & 73 - 1 (-165) = \textcolor[rgb]{1,0,0}{238}\\
712 & 315 & 2 & 82 & 73 & -19 - 2\cdot 73 = -165\\
315 & 82 & 3 & 69 & -19 & 16 -3(-19) = 73\\
82 & 69 & 1 & 13 & 16 & -3 -1\cdot 16 = -19\\
69 & 13 & 5 &4 & - 3 & 1 -5(-3) = 16\\
13 & 4 &3 & 1 & 1 & 0 - 3\cdot 1 = -3 \\
4 & 1 & 4 & 0 & 0 & 0\cdot 4 + 1 = 1\\
&&&&&\\
\hline
\end{array}
}$$

$$\small{\text{
The first solution is $ (-165,238) \qquad 1027 \cdot (\textcolor[rgb]{1,0,0}{ -165} ) + 712 \cdot \textcolor[rgb]{1,0,0}{238} = 1
$}}\\\\$$

4. All Solutions:

$$\small{\text{$
\begin{array}{lcl}
\boxed{
a\cdot x + b \cdot y = 1 }\\\\
\mathrm{First~ solution~~} (x_0,~ y_0)\\
\mathrm{All~ solutions~~} \left(x_0+\dfrac{z\cdot b}{ gcd(a,b) } ,~ y_0 - \dfrac{z\cdot a}{ gcd(a,b) }\right)\\
\end{array}
$}}\\\\$$

$$\small{\text{$
\begin{array}{lcl}
\boxed{
1027\cdot x + 712 \cdot y = 1 }\\\\
\mathrm{First~ solution~~} (x_0=-165,~ y_0=238)\\
\mathrm{All~ solutions~~} \left(-165+\dfrac{z\cdot 712}{ 1 } ,~ 238 - \dfrac{z\cdot 1027}{ 1 }\right)\\
\end{array}
$}}\\\\$$

we have:

$$\small{\text{$
\begin{array}{lcl}
\left\{~\left(~ -165 + 712\cdot z,~ 238 - 1027\cdot z\right)~|~z \in Z ~
\right\} \\
\end{array}
$}}\\\\$$

I'm going to employ maximum cheating on this one.......

Using the Euclidian algorithm, we have

1027  = 1(712) + 315

712 = 2(315) + 82

315 = 3(82) + 69

82 = 1(69) + 13

69 = 5(13) + 4

13 = 3(4) + 1

4 = 4(1) + 0

                              1        2        3         1        5          3          4

1  0                        1        2        7         9        52     165       712     

0  1                        1        3       10       13       75      238     1027

Take the  determinant of          165     712

                                                 238   1027        =   -1

So.....

1027(165) - 712(238) = - 1   but...we need a  "+1 "   .....so......multiplying through by -1, we have

1027(-165) + 712(238) = 1

So....x = -165   and y = 238....however.....this is only one solution.....the general solution is given by

x , y   =  [ (-165 + 712k), (238 - 1027k) ]

Well aren't you just so clever.  I worked it out Too :))

Well....Ms. SmartyPants......I even provided a general solution.....so.....take that  !!!   

Thanks for that great answer Heureka :)