1.find the gcd(5311,7571)?

Answer 1

because 2 numbers are large factorisation is not a good choice

using GCD(a, b) = GCD(a-b,b) where a >b

we get GCD(5311,7571)
= GCD(5311,7571-5311)
= GCD(5311,2260)
=GCD(5311-2260,2260)
= GCD(3051,2260)
= GCD(3051-2260,2260)
= GCD(791,2260)
= GCD(791,226) because 10 devides 2260 but not 791
= GCD(791,113) becuase 2 devides 226 not 791
= 113 as 113 devides 791
so GCD = 113

Answer 2

Using Euclid theorem

for gcd (5311,7571)

7571 - 5311 = 2260
5311 - 2260 = 3051
3051 - 2260 = 791
2260 - 791 * 2 = 678
791 - 678 = 113
678 - 113* 6 = 0

Thus the GCD is 113 for both 5311 & 7571

Answer 3

Using the Euclidian algorithm:

7571
5311
2260
791
678
113
0

So gcd (5311, 7571) = 113
5311 = 47 * 113
7571 = 67 * 113

Answer 4

Because the two numbers are odd, we can apply Donald Knuth's binary algorithm directly. Take the difference of the two numbers, halve it repeatedly until it is odd, and start again with that odd number and the smaller of the two previous odd numbers, until they are the same. Thus:

7571 - 5311 = 2260, 1130, 565
5311 - 565 = 4746, 2373
2373 - 565 = 1808, 904, 452, 226, 113
565 - 113 = 452, 226, 113 and we are done.