Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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

4 Answers 4

up vote 5 down vote accepted

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

share|improve this answer
4  
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
1  
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$.

share|improve this answer
    
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
1  
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.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.