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?