Question

whats the euclidean algorithm & how does it work? examples please.

Answer 1

it is a way to find the greatest common divisor using division with remainder

Answer 2

EX: gcd(14,35). First we divide 35 by 14 with remainder.

35= 2(14)+7

Now you divide 14 by your remainder 7:

14= 2(7)+0

You repeat the process until you get 0, and then the previous remainder is the greatest common divisor

Answer 3

so here 7 is the greatest common divisor of 14 and 35

Answer 4

In general: gcd(a,b), a>b. Divide a by b with remainder r:

\[a=q_1b+r_1\]

Answer 5

So how would the solution go for 25&65. The answer would be 5 wouldn't it?

Answer 6

then divide b by the first remainder, etc until you get remainder 0, then check the last remainder:

\[b=q_2r_1+r_2\]
\[r_1=q_3r_2+r_3\]

.
. etc until some r_n is 0, then r_(n-1) is the gcd(a,b)
.

Answer 7

ok lets try that problem. gcd(65,25)

65=2(25)+15
25=1(15)+10
15=1(10)+5<-----gcd(65,25)
10=2(5)+0<------stop here and go up one remainder

Answer 8

so you're right it is 5

Answer 9

hope that helps :)

Answer 10

Why divide 25 by 2 first?

Answer 11

we divided 65 by 25 first

Answer 12

25 goes into 65 two whole times, then there is 15 left

Answer 13

65=2*25+15

Answer 14

it is just another way to think about division. 65/25=2+15/25

Answer 15

so multiply by 25 through the whole thing and you get

65=2*25+15

Answer 16

It did help a lot. Thank you soo much :)

Answer 17

y.w. :)