Solution to Assignment 1 Due: 6th April 2021 at 5.00 p.m. Total: 70 marks 1. Using the … - Sikademy
Author Image

Archangel Macsika

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 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

Related Answers

Was this answer helpful?

Join our Community to stay in the know

Get updates for similar and other helpful Answers

Question ID: mtid-5-stid-8-sqid-3193-qpid-1892