# Is Euclid's algorithm for the GCD of two numbers wrong?

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?

• The formula is definitely right. Perhaps one of the programming SEs can help you debug your code. – TokenToucan Jun 6 '15 at 3:00
• Yes, it is correct, you should post your code in the Programming exchange sites (or even tell us how you programmed the algorithm). – YoTengoUnLCD Jun 6 '15 at 3:01
• yall are much more kind than me. – muaddib Jun 6 '15 at 3:02
• @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. – KlingL Jun 6 '15 at 3:11
• @LarryK show me your code I can fix it – alkabary Jun 6 '15 at 3:17

\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.
• @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{}$ – Michael Hardy Jun 6 '15 at 3:09
• @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. – YoTengoUnLCD Jun 6 '15 at 3:17
• @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{}$ – Michael Hardy Jun 6 '15 at 4:02