Questions   
Sort: 
 #4
avatar+26400 
+10

 1027x+712y=1

(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}
$}}\\\\$$

 

Jul 2, 2015
 #2
avatar
0
Jul 2, 2015

2 Online Users

avatar
avatar