Question

C₁= 5

C₂= 6

C₃= 10

GCD --> Greater Common Divisor

B1 a. Let x := 3C1 + 1 and let y := 5C2 + 1. Use the Euclidean algorithm to determine the GCD (x, y), and we denote this integer by g. b. Reverse the steps in this algorithm to find integers a and b with ax + by = g. c. Use this to find the inverse of x modulo y. If the inverse doesn't exist why not? B2 a. Show that for integers a, b E Z, (a,b) = Cz implies (C3, b) > C1. b. Let n be the product of the first C primes (those of smallest sizes). What is the smallest number of possible prime divisors to check whether n + 1 is also a prime?

Answer 1

soin B1. Giren 4-5 (-6C = 10 a. x=39+ 1 2-3 (5) +1 16 & y = 562+1 g 5(6) +1 31 by Euclidean algorithm. To find • GCD (NY) Consider 31 = 16 x 1 + 15 16 = 15x1 + 15 1x15 to 6 GCD (16, 31) = 1 ire g = 1 1 Hence b.) Now GCD (2,y) = Consider 16- 15x1 = 16-(31-16) 16-31+ 16 2 (16) + (-1) 31 1 here a= 2 & b = -1 such that g axtby ) c) To moduloy, consider find inverse of Halfmot 31) 16 x'g (mod 31) for x! = 2, 32 = 1 (mod 31) Hence Inverse of 16 modulo 31 is dl inverse of x modulo y is 2 CS ie Scanned with CamScanner