Answer to Question #179577 in Discrete Mathematics for oata

Question #179577

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)


1
Expert's answer
2021-04-14T01:05:32-0400

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"


Need a fast expert's response?

Submit order

and get a quick answer at the best price

for any assignment or question with DETAILED EXPLANATIONS!

Comments

No comments. Be the first!

Leave a comment

LATEST TUTORIALS
New on Blog
APPROVED BY CLIENTS