Question

Can someone explain how to use the Euclidean algorithm, to me?

Answer 1

https://www.khanacademy.org/math/cc-sixth-grade-math/cc-6th-factors-and-multiples/cc-6th-gcf/v/greatest-common-divisor

Answer 2

I think he uses it in the vid.

Answer 3

No, he doesn't.
The Euclidean algorithm is a technique in getting the gcd.

Answer 4

Are you sure? I thought i read at the desscription he did.
In that case you can search youtube; it has many videos describing this technique.

Answer 5

Ok why don't we do an example to explain. First lets find the gcd of 14 and 28

Answer 6

by inspection the answer is clearly 14, right? so now let us apply the algorithm and see if we get the same answer.

Answer 7

Okay.
28 = 14 * 2 + 0
?

Answer 8

yep i was trying to type that pretty but meh, so good your remainder is zero right? therefore the 14 is your gcd

Answer 9

so do a big number you pick two

Answer 10

729 and 9

Answer 11

k, so first set up the eq.

Answer 12

729=a*9+r

Answer 13

okay, so.
729 = 81*9 + 0

Answer 14

good so the gcd is?

Answer 15

81

Answer 16

thanks.

Answer 17

wait

Answer 18

I have the general concept understood.

Answer 19

does 81 divide 9?

Answer 20

729 = 81*9 + 0
81 = 9*9 + 0
9 = 9*1 + 0

Answer 21

not quite, 9 is the answer but you can stop at the first step because the remainder is 0

Answer 22

let's try 613 and 769

Answer 23

769=?

Answer 24

they're both primes right? so they're gcd would just be 1..

Answer 25

meh we'll see. but first apply the algorithm

Answer 26

769=a*613+r

Answer 27

769 = 1*613 + 156

Answer 28

613 = 3*156 + 145
156 = 1*145 + 11
145 = 13*11 + 2
11 = 5*2 + 1
2 = 2*1 + 0
1 = 1*1 + 0
?

Answer 29

yep that is exactly how it works

Answer 30

ok ty

Answer 31

np good luck in number theory