Assignment 1 Due: 6th April 2021 at 5.00 p.m. Total: 70 marks 1. Using the theorem divisibility, prove the following a) If a|b , then a|bc ∀a,b,c∈ℤ ( 5 marks) b) If a|b and b|c , then a|c (5 marks) 2. Using any programming language of choice (preferably python), implement the following algorithms a) Modular exponentiation algorithm (10 marks) b) The sieve of Eratosthenes (10 marks) 3. Write a program that implements the Euclidean Algorithm (10 marks) 4. Modify the algorithm above such that it not only returns the gcd of a and b but also the Bezouts coefficients x and y, such that 𝑎𝑥+𝑏𝑦=1 (10 marks) 5. Let m be the gcd of 117 and 299. Find m using the Euclidean algorithm (5 marks) 6. Find the integers p and q , solution to 1002𝑝 +71𝑞= 𝑚 (5 marks) 7. Determine whether the equation 486𝑥+222𝑦=6 has a solution such that 𝑥,𝑦∈𝑍𝑝 If yes, find x and y. If not, explain your answer. (5 marks) 8. Determine integers x and y such that 𝑔𝑐𝑑(421,11) = 421𝑥 + 11𝑦. (5 marks)
The Answer to the Question
is below this banner.
Here's the Solution to this Question
There is an integer such that
b) There are integers and such that:
# Simple python code that first calls pow() # then applies % operator. a = 2 b = 100 p = (int)(1e9+7) # pow function used with % d = pow(a, b) % p print (d)
# Python algorithm compute all primes smaller than or equal to # n using Sieve of Eratosthenes def SieveOfEratosthenes(n): # Create a boolean array "prime[0..n]" and initialize # all entries it as true. A value in prime[i] will # finally be false if i is Not a prime, else true. prime = [True for i in range(n + 1)] p = 2 while (p * p <= n): # If prime[p] is not changed, then it is a prime if (prime[p] == True): # Update all multiples of p for i in range(p * 2, n + 1, p): prime[i] = False p += 1 prime= False prime= False # Print all prime numbers for p in range(n + 1): if prime[p]: print p, #Use print(p) for python 3
3.Euclidean Algorithm to compute the greatest common divisor.
from math import * def euclid_algo(x, y, verbose=True): if x < y: # We want x >= y return euclid_algo(y, x, verbose) print() while y != 0: if verbose: print('%s = %s * %s + %s' % (x, floor(x/y), y, x % y)) (x, y) = (y, x % y) if verbose: print('gcd is %s' % x) return x
# function for extended Euclidean Algorithm def gcdExtended(a, b): # Base Case if a == 0 : return b,0,1 gcd,x1,y1 = gcdExtended(b%a, a) # Update x and y using results of recursive # call x = y1 - (b//a) * x1 y = x1 return gcd,x,y