Question

1. Are the following expressions true or false? 2550 (mod 5) 3353 (mod 11) 1856 (mod 3) 8058 (mod 9) 3859 (mod 4) True True True True True False False False False False 2. Apply Euclid's algorithm to find gcd (424762, 28101). Calculations: gcd (424762, 28101) = 3. Record the number 1800 as the product of primes. 1800 =

Answer 1

1)

True

False

False

Ture

False

2)

Answer : 17

gcd(424762, 28101)

Step 1:
a = b % a = 424762 % 28101

b = 424762

Step 2:

a = b % a = 424762 % 28101 = 3247

b = 28101

Step 3:

a = b % a = 28101 % 3247 = 2125

b = 3247

Step 4:

a = b % a = 3247 % 2125 = 1122

b = 2125

Step 5:

a = b % a = 2125 % 1122 = 1003

b = 1122

Step 6:

a = b % a = 1122 % 1003 = 119

b = 1003

Step 7:

a = b % a = 1003 % 119 = 51

b = 119

Step 8:

a = b % a = 119 % 51 = 17

b = 51

Step 9:

a = b % a = 51 % 17 = 0

b = 17

Remainder is 0, then the answer will be 17

3)

1800 = 5 x 5 x 3 x 3 x 2 x 2 x 2