1
$\begingroup$

So today in Computer Science I was asked to write a program that used Euclid's algorithm to find the GCD of two numbers that you input. My teacher told us that if x is some positive integer larger than y, Euclid's algorithm was the GCD of x & y  =  the GCD of y & the remainder of x/y, (setting y = the remainder of x/y every time) while the remainder of x/y does not equal 0 (the final remainder not equaling zero being the answer).

My program is right... most of the time. When I input the numbers 50 & 23, or 98 and 59, it tells me their GCD is 2, which is obviously wrong because 23 & 59 are prime. Do you guys know if this formula is right?

$\endgroup$
  • 3
    $\begingroup$ The formula is definitely right. Perhaps one of the programming SEs can help you debug your code. $\endgroup$ – TokenToucan Jun 6 '15 at 3:00
  • $\begingroup$ Yes, it is correct, you should post your code in the Programming exchange sites (or even tell us how you programmed the algorithm). $\endgroup$ – YoTengoUnLCD Jun 6 '15 at 3:01
  • $\begingroup$ yall are much more kind than me. $\endgroup$ – muaddib Jun 6 '15 at 3:02
  • $\begingroup$ @YoTengoUnLCD I found the larger of the two numbers. Then I set the smaller variable equal to the remainder of the larger variable over the smaller variable, then I checked to see if the smaller variable then equaled zero (because the remainder was zero). If it did not, I set a third variable equal to the smaller variable. I would repeat this until the smaller variable did equal zero, then I would output the third variable. $\endgroup$ – KlingL Jun 6 '15 at 3:11
  • $\begingroup$ @LarryK show me your code I can fix it $\endgroup$ – alkabary Jun 6 '15 at 3:17
4
$\begingroup$

Euclid's algorithm is right and your program is wrong.

\begin{align} 50 - 23 & = 27 \\ 27 - 23 & = 4 \\ \\ 23 - 4 & = 19 \\ \\ 19 - 4 & = 15 \\ 15 - 4 & = 11 \\ 11 - 4 & = 7 \\ 7 - 4 & = 3 \\ \\ 4 - 3 & = 1 \\ 3 - 1 & = 2 \\ 2 - 1 & = 1 \end{align} Now you're looking for $\gcd(1,1)$, and that is $1$. \begin{align} 98 - 59 & = 39 \\ \\ 59 - 39 & = 20 \\ \\ 39 - 20 & = 19 \\ \\ 20 - 19 & = 1 \end{align} etc.

$\endgroup$
  • $\begingroup$ Where did the 19, 15, and 11 come from? $\endgroup$ – KlingL Jun 6 '15 at 3:06
  • 1
    $\begingroup$ @LarryK : From subtracting. The point is that $\gcd(a,b)=\gcd(a-b,b)$. If $a>b$, then replace the pair $(a,b)$ with $(a-b,b)$, and the gcd is still the same. That's the idea of Euclid's algorithm. ${}\qquad{}$ $\endgroup$ – Michael Hardy Jun 6 '15 at 3:09
  • $\begingroup$ Oh, I'm using division, and finding the remainder from that. $\endgroup$ – KlingL Jun 6 '15 at 3:12
  • $\begingroup$ @LarryK it's the same, in principle, if $a>b$ then $a=qb+r$ with $b>r$, so $gcd(a,b)=gcd(qb+r,b)=gcd(qb+r-b,b)=...=gcd(r,b)=gcd(b,r)$. Remember that division is just substracting many times. $\endgroup$ – YoTengoUnLCD Jun 6 '15 at 3:17
  • $\begingroup$ @LarryK : The reason for stating it in the form $\gcd(a,b)=\gcd(a-b,b)$ is that it's easy to prove those two are equal. After that it can be seen that $\gcd(a,b)=\gcd(r,b)$ where $r$ is the remainder on division of $a$ by $b$. ${}\qquad{}$ $\endgroup$ – Michael Hardy Jun 6 '15 at 4:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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