euclidean algorithm

logistic_guy

Senior Member
Joined
Apr 17, 2024
Messages
1,268
Suppose a=57970\displaystyle a = 57970 and b=10353\displaystyle b = 10353. Apply the Euclidean Algorithm and show that (57970,10353)=17\displaystyle (57970,10353) = 17.

💪👺👺
 
Suppose a=57970\displaystyle a = 57970 and b=10353\displaystyle b = 10353. Apply the Euclidean Algorithm and show that (57970,10353)=17\displaystyle (57970,10353) = 17.

💪👺👺
Please include the PROPER "statement" of Euclidean algorithm that is expected to be used here.

Or may be you don't know "that" - and "that" is why you are stuck!!
 
Check out


to see a clearly worked example with correct notation.
Thank you a lot professor Harry. I didn't see how Khan solved it but it was very helpful to know that this notation means the GCD\displaystyle \text{GCD} (The Greatest Common Divisor). I will try to solve it without cheating as I always do.
 
Last edited:
this notation means the GCD\displaystyle \text{GCD}
5797010353=5+620510353\displaystyle \frac{57970}{10353} = 5 + \frac{6205}{10353}

Or

57970=(5)10353+6205\displaystyle 57970 = (5)10353 + 6205
 
Next.

57970=(5)10353+6205\displaystyle 57970 = (5)10353 + 6205
10353=(1)6205+4148\displaystyle 10353 = (1)6205 + 4148
 
Next.

57970=(5)10353+6205\displaystyle 57970 = (5)10353 + 6205
10353=(1)6205+4148\displaystyle 10353 = (1)6205 + 4148
6205=(1)4148+2057\displaystyle 6205 = (1)4148 + 2057
 
Next.

57970=(5)10353+6205\displaystyle 57970 = (5)10353 + 6205
10353=(1)6205+4148\displaystyle 10353 = (1)6205 + 4148
6205=(1)4148+2057\displaystyle 6205 = (1)4148 + 2057
4148=(2)2057+34\displaystyle 4148 = (2)2057 + 34
 
Next.

57970=(5)10353+6205\displaystyle 57970 = (5)10353 + 6205
10353=(1)6205+4148\displaystyle 10353 = (1)6205 + 4148
6205=(1)4148+2057\displaystyle 6205 = (1)4148 + 2057
4148=(2)2057+34\displaystyle 4148 = (2)2057 + 34
2057=(60)34+17\displaystyle 2057 = (60)34 + 17
 
Next.

57970=(5)10353+6205\displaystyle 57970 = (5)10353 + 6205
10353=(1)6205+4148\displaystyle 10353 = (1)6205 + 4148
6205=(1)4148+2057\displaystyle 6205 = (1)4148 + 2057
4148=(2)2057+34\displaystyle 4148 = (2)2057 + 34
2057=(60)34+17\displaystyle 2057 = (60)34 + 17
    34=(2)17\displaystyle \ \ \ \ 34 = (2)17

This means that:

gcd(57970,10353)=17\displaystyle \text{gcd}(57970,10353) = 17
 
Top