# Greatest Common Divisor

I have calculated $d = 39$ but don't know how to find $u$ and $v$.

Btw I know this is not really a cryptography question, but there isn't a tag for GCD.

-
Is it me or does $6$ not divide $975$? – Lord_Farin Apr 19 '13 at 14:48
@Lord_Farin Yes you're right. I must have made a mistake. – Adegoke A Apr 19 '13 at 14:49

$\newcommand{\GCD}{\operatorname{GCD}}$

Hint:

Use extended Euclid's division Algorithm as vonbrand suggested.

$ax+by=\GCD(a,b)$

$2184=975 \times 2+234$

$975=234 \times 3+39$

$234=39 \times 6+0$

$\GCD (2184,975)=39$

Now use the method of back-substitution:

$\ 975-(234 \times 3)=39$

$\ 975-((2184-(975 \times 2)) \times 3)=39$

-
Use the extended Euclidean algorithm – vonbrand Apr 19 '13 at 14:46
Well, yes! Extended one. – Inceptio Apr 19 '13 at 14:48
...about which you may read here. – Lord_Farin Apr 19 '13 at 14:49
@Inceptio Can you show the workings for the second part, please. I don't understand the Wikipedia method. – Adegoke A Apr 19 '13 at 15:10
I'm afraid you didn't see the substitution part. $39=975-234 \times 3$ $234=2184-975 \times 2$. Substitute $2184-975 \times 2$ instead of $234$ back in there. You get everything in terms of $2184$ and $975$. – Inceptio Apr 19 '13 at 15:16

You can use a matrix technique. First, write

$$\left[ \begin{array}{cc|c} 1 & 0 & 2184 \\ 0 & 1 & 975 \end{array}\right]$$

Then perform repeated row operations, e.g.:

$$\left[ \begin{array}{cc|c} 1 & 0 & 2184 \\ 0 & 1 & 975 \end{array}\right] \stackrel{R_1-2R_2}{\longrightarrow} \left[ \begin{array}{cc|c} 1 & -2 & 234 \\ 0 & 1 & 975 \end{array}\right] \stackrel{R_2-4R_1}{\longrightarrow} \left[ \begin{array}{cc|c} 1 & -2 & 234 \\ -4 & 9 & 39 \end{array}\right]$$

$$\left[ \begin{array}{cc|c} 1 & -2 & 234 \\ -4 & 9 & 39 \end{array}\right] \stackrel{R_2-4R_1}{\longrightarrow} \left[ \begin{array}{cc|c} 1 & -2 & 234 \\ -4 & 9 & 39 \end{array}\right]$$

Since $39$ divides $234$ we stop and we get $\gcd(2184,975) = 39$ and, $(-4) \cdot 2184 + 9 \cdot 975 = 39$.

-
This is nice(+1) – Inceptio Apr 19 '13 at 15:04
Thank you. :-)) – Adegoke A Apr 19 '13 at 15:06
What operations are you doing in between the matrices? – Adegoke A Apr 19 '13 at 15:30
Row operations. – Fly by Night Apr 19 '13 at 15:34
For example, $R_1-3R_2$ means subtract three lots of row two from row one. You subtract term by term. Because 975 goes into 2184 twice, leaving a remainder, I do $R_1-2R_2$. Then because 234 goes into 975 four times, leaving a remainder, I do $R_2-4R_1$. You keep juggling like this, taking as many lots of the smaller from the bigger until the smaller divides into the bigger without remainder. – Fly by Night Apr 19 '13 at 15:37

Cancelling the gcd: $\rm\ 56u + 25v = 1\:\Rightarrow\: mod\ 25\!:\ u \equiv \dfrac{1}{56}\equiv \dfrac{-24}6 \ \equiv -4,\$ so $\rm\ u = -4\! +\! 25n,\:$ so $\rm\: v = (1\!-\!56u)/25\, =\, (1-56(-4\!+\!25n))/25\, =\, 9\!-\!56n,\:$ i.e. $\rm\: (u,v)\, =\, (-4,9)+(25,-26)n$.

Remark $\$ Generally it is more efficient to employ the extended Euclidean algorithm.

-

By using The Extended Euclidean Algorithm

$gcd(2184, 975) = x$

$2184 = 2*975 + 234$

$975 = 4*234 + 39$

$234 = 6*39$

Thus $gcd(2184, 975) = 39$

$d = 2184u + 975v$. Solve for $u$ and $v$.

$39 = 975 - 4*234$

$39 = 975 - 4(2184 - 2*975)$

$39 = 9*975 - 4*2184$

$u = -4$ and $v = 9$

Two more examples here.

-