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?
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.