# Answer in Discrete Mathematics for oata #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. 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=2cdot117+65”

“117=65cdot1+52”

“65=52cdot1+13”

“52=13cdot4+0”

“gcd=13”

6.If “m=gcd(1002,71)”

“1002=71cdot14+8”

“71=8cdot8+7”

“8=7cdot1+1”

“7=1cdot7+0”

“gcd=1”

Then:

“1=8-1cdot7=8-1cdot(71-8cdot8)=-1cdot71+8cdot9=”

“=-1cdot71+9cdot(1002-71cdot14)=9cdot1002-15cdot71”

“p=9,q=-15”

7.

“486=2cdot222+42”

“222=42cdot5+12”

“42=12cdot3+6”

“12=6cdot2+0”

“gcd=6”

“6=42-12cdot3=42-3(222-42cdot5)=-3cdot222+16cdot42=”

“=-3cdot222+16(486-2cdot222)=16cdot486-35cdot222”

“x=16,y=35”

8.

“421=38cdot11+3”

“11=3cdot3+2”

“3=2cdot1+1”

“2=1cdot2+0”

“gcd=1”

“1=3-1cdot2=3-(11-3cdot3)=-11+3cdot4=-11+4(421-38cdot11)=”

“=4cdot421-39cdot11”

“x=4,y=153”