Question

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)

Answer 1

1. a)

There is an integer $k$ such that $ak=b$

Then:

$bc=akc$

So: $a|bc$

b) There are integers $k$ and $m$ such that:

$ak=b,bm=c$

Then:

$akm=c$

So: $a|c$

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: $976371285$

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.

$a=299,b=117$

$a=bq+r$

$299=2\cdot117+65$

$117=65\cdot1+52$

$65=52\cdot1+13$

$52=13\cdot4+0$

$gcd=13$

6.If $m=gcd(1002,71)$

$1002=71\cdot14+8$

$71=8\cdot8+7$

$8=7\cdot1+1$

$7=1\cdot7+0$

$gcd=1$

Then:

$1=8-1\cdot7=8-1\cdot(71-8\cdot8)=-1\cdot71+8\cdot9=$

$=-1\cdot71+9\cdot(1002-71\cdot14)=9\cdot1002-15\cdot71$

$p=9,q=-15$

7.

$486=2\cdot222+42$

$222=42\cdot5+12$

$42=12\cdot3+6$

$12=6\cdot2+0$

$gcd=6$

$6=42-12\cdot3=42-3(222-42\cdot5)=-3\cdot222+16\cdot42=$

$=-3\cdot222+16(486-2\cdot222)=16\cdot486-35\cdot222$

$x=16,y=35$

8.

$421=38\cdot11+3$

$11=3\cdot3+2$

$3=2\cdot1+1$

$2=1\cdot2+0$

$gcd=1$

$1=3-1\cdot2=3-(11-3\cdot3)=-11+3\cdot4=-11+4(421-38\cdot11)=$

$=4\cdot421-39\cdot11$

$x=4,y=153$