euclidean algorithm

[logistic_guy]

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

 

[khansaheb]

Suppose \(\displaystyle a = 57970\) and \(\displaystyle b = 10353\). Apply the Euclidean Algorithm and show that \(\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!!

 

[logistic_guy]

@khansaheb

What does \(\displaystyle (57970,10353) = 17\) mean?

 

[Harry_the_cat]

Check out

Khan Academy

www.khanacademy.org

to see a clearly worked example with correct notation.

 

[logistic_guy]

Check out

Khan Academy

www.khanacademy.org

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 \(\displaystyle \text{GCD}\) (The Greatest Common Divisor). I will try to solve it without cheating as I always do.

 

[logistic_guy]

this notation means the \(\displaystyle \text{GCD}\)

\(\displaystyle \frac{57970}{10353} = 5 + \frac{6205}{10353}\)

Or

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

 

[logistic_guy]

Next.

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

 

[logistic_guy]

Next.

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

 

[logistic_guy]

Next.

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

 

[logistic_guy]

Next.

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

 

[logistic_guy]

Next.

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

This means that:

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

 

[Agent Smith]

Factorize(x) into pairs of factors
Factorize(y) into pairs of factors
Find GCF(x y) using the 2 factor trees.