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.
Can't find a solution anywhere?
NEED A FAST ANSWER TO ANY QUESTION OR ASSIGNMENT?
Get the Answers Now!You will get a detailed answer to your question or assignment in the shortest time possible.
Here's the Solution to this Question
1. a)
There is an integer such that
Then:
So:
b) There are integers and such that:
Then:
So:
2.a)
# 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)
Output:
b)
# 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[0]= False
prime[1]= 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
4.
# 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
5.
6.If
Then:
7.
8.