## Description

## Objectives:

1. Use the Sieve of Eratosthenes to find all primes in a given range.

2. Design a computational algorithm for finding the Bézout coefficients of two integers.

3. Use Bézout coefficients to calculate the GCD.

NOTE:

Unless otherwise stated in the FIXME comment, you may not change the outline of the

algorithm provided by introducing new loops or conditionals, or by calling any built-in functions

that perform the entire algorithm or replaces a part of the algorithm.

Problem 1:

Complete the function primes(a, b) which uses the Sieve of Eratosthenes to create and

return a list of all the primes satisfying .

INPUT:

a – a positive integer greater than or equal to 1 ( ValueError if an integer less than

1 is given); the lower bound

b – a positive integer greater than or equal to a ( ValueError if b < a ); the

upper bound

OUTPUT:

a set of all the primes satisfying a b

EXAMPLE:

>> primes(1, 10)

p a ≤ p ≤ b

p ≤ p ≤

{2, 3, 5, 7}

>> primes(50, 100)

{53, 59, 61, 67, 71, 73, 79, 83, 89, 97}

NOTE: The order of the elements might be different in your output in comparison to the

expected output, and that is okay! Your output is correct as long as you have all the primes.

Problem 2:

Complete the function bezout_coeffs(a, b) that computes the Bezout coefficients s and

t of a and b .

1. INPUT:

a , b – distinct integers

2. OUTPUT: {a: s, b: t} – dictionary where keys are the input integers and values are

their corresponding Bezout coefficients.

EXAMPLE: >> bezout_coeffs(414, 662)

{414 : 8, 662 : -5}

NOTE:

In [1]:

def primes(a, b):

if a < 1 or b < a: # handling invalid range

raise ValueError(“Invalid range given”)

if a == 1: # handling starting point a = 1

a = 2 # this ensures 1 is not listed as a prime

# FIXME: initialize `stop` which is the stopping criteria for

# the loop in the Sieve of Eratosthenes

stop = “FIXME: Replace this string”

# FIXME: initialize a Python set called `P` that contains

# all integers in the range [a, b]

P = set(“FIXME: Replace this string”)

for x in range(2, stop):

# FIXME: use Python list comprehension to create a set

# of multiples of x in the range [2, b];

# HINT: the set of multiples of x can be expressed as

# k * x, where k is an integer; hence the comprehension should

# loop over values that satisfy k * x <= b

multiples_x = set(“FIXME: replace this string”)

P -= multiples_x # removing the multiples of x from the set P

return P

The algorithm for the function bezout_coeff(a,b) uses the logic employed in the following

example:

Suppose . We seek and such that gcd

Let’s begin by defining . At every round in attempting to

attain the gcd, we will refer to and as the current coefficients of 13 and 21, respectively.

Round 1:

We will call this EQN 1

NOTICE:

Round 2:

from EQN 1

NOTICE:

Round 3:

a = 13, b = 21 s t (13, 21) = 13s + 21t

s0 = 1, t0 = 0, a1 = 13, b1 = 21

si ti

21 = 1 ⋅ 13 + 8

⟹ 8 = 21 − 1 ⋅ 13

⟹ s1 = −1, t1 = 1

s1 = − ( b1 div a1 ) = −(21 div 13) = −1

a2 = 8, b2 = 13

13 = 1 ⋅ 8 + 5

⟹ 5 = 13 − 1 ⋅ 8

= 1 ⋅ 13 − 1(21 − 1 ⋅ 13)

= 2 ⋅ 13 − 1 ⋅ 21

⟹ s2 = 2, t2 = −1

s2 = s0 − s1 ( b2 div a2)

= 1 − 1 ( 13 div 8)

= 1 − (−1)(1)

= 2

t2 = t0 − t1 ( b2 div a2)

= 0 − 1 ( 13 div 8)

= 0 − 1 (1)

= −1

NOTICE:

Round :

For any round , the corresponding and values are given by

You should verify for yourself that for any ,

a3 = 5, b3 = 8

8 = 1 ⋅ 5 + 3

⟹ 3 = 8 − 1

b3 div a3

⋅ 5

= 1 ⋅ ( 1

t1

⋅ 21 −1

s1

⋅ 13) − 1

b3 div a3

( 2

s2

⋅ 13 −1

t2

⋅ 21)

= −3 ⋅ 13 + 2 ⋅ 21

⟹ s3 = −3, t3 = 2

s3 = s1 − s2 ( b3 div a3)

= −1 − (2)(1)

= −3

t3 = t1 − t2 ( b3 div a3)

= 1 − (−1)(1)

= 2

⋮

k

k ≥ 2 sk

tk

sk = sk−2 − sk−1 ( bk div ak)

tk = tk−2 − tk−1 ( bk div ak)

a, b

s0 = 1

t0 = 0

s1 = −( b div a)

t1 = 1

In [22]:

def bezout_coeffs(a, b):

“””

computes the Bezout coefficients of two given positive integers

:param a: int type; positive integer

:param b: int type; positive integer

:returns: dict type; a dictionary with parameters a and b as keys,

Problem 3:

Create a function gcd(a, b) that computes the greatest common divisor of a and b using

the bezout_coeff function you implemented for problem 2 lecture. No credit will be given to

functions that employ any other implementation. For example, using the built-in function

math.gcd() as part of our implementation will not receive any credit.

INPUT:

* `a`,`b` – integers

OUTPUT: d – the gcd

EXAMPLE:

>> gcd(414, 662)

and their corresponding Bezout coefficients as values.

:raises: ValueError if a < 0 or b < 0

“””

if a < 0 or b < 0:

raise ValueError(

f”bezout_coeffs(a, b) does not support negative arguments.”)

s0 = 1

t0 = 0

s1 = -1 * (b // a)

t1 = 1

temp = b

bk = a

ak = temp % a

while ak != 0:

temp_s = s1

temp_t = t1

# FIXME: Update s1 according to the formula for sk

s1 = “FIXME: Replace this string”

# FIXME: Update t1 according to the formula for tk

t1 = “FIXME: Replace this string”

s0 = temp_s

t0 = temp_t

temp = bk

# FIXME: Update bk and ak

bk = “FIXME: Replace this string”

ak = “FIXME: Replace this string”

# FIXME: Replace each string with the correct coefficients of a and b

return {a: “FIXME: replace this string”, b: “FIXME: replace this string”}

2

HINT

The GCD of any two numbers must be positive by definition.

Problem 4:

Complete the function mod_inv(a, m) that returns the inverse of a modulo m that is in the

range . If the gcd of a and m is not 1, then the function raises a ValueError

exception.

Example:

>> mod_inv(3, 11)

4

In [26]:

def gcd(a,b):

“””

computes the greatest common divisor of two given integers

:param a: int type;

:param b: int type;

:returns: int type; the gcd of a and b

“””

A = abs(a)

B = abs(b)

if A == B:

pass # FIXME: replace this pass with the correct return value

bez = bezout_coeffs(A, B)

return # FIXME: replace this pass with the correct return value

[1, m − 1]

In [ ]:

def mod_inv(a, m):

“””

computes the inverse of a given integer a under a given modulo m

:param a: int type; the integer of interest

:param m: int type; the modulo

:returns: int type; the integer in range [0, m) that is the inverse of a under mod

:raises: ValueError if m < 0 or if a and m are not relatively prime

“””

if m < 0:

raise ValueError(f”mod_inv(a, m) does not support negative modulo m = {m}”)

g = gcd(a, m)

if g != 1:

raise ValueError(f”mod_inv(a, m) does not support integers that are not relati

A = a

while A < 0:

A += “””FIXME: replace this string so that by the end of the loop, A is in ran

inverse = “””FIXME: replace this string with the inverse of a under modulo m”””

while inverse < 0:

inverse += “””FIXME: replace this string so that by the end of the loop, the i

Problem 5:

Complete the function solve_mod_equiv(a, b, m, low, high) that returns a set all

integers satisfying,

and,

If gcd , ValueError is raised.

INPUT:

a , b , low , high – integers

m – positive integer, greater than 1

OUTPUT: Python set {} of all integers satisfying the conditions above.

EXAMPLE:

>> solve_mod_equiv(3, 4, 7, -5, 5)

{-1}

return inverse

x

ax ≡ b (mod m)

low ≤ x ≤ high

(a, m) ≠ 1

In [3]:

def solve_mod_equiv(a, b, m, low, high):

“””

computes all solutions to the equivalence ax ≡ b (mod m)

that are in the range [low, high]

:param a: int type; the coefficient of the unknown value x

:param b: int type; the integer that ax is equivalent to

under modulo m

:param m: int type; the modulo

:param low: int type; the lower bound for the solutions

:param high: int type; the upper bound for the solutions

:raises: ValueError if high < low or if m < 0

“””

if high < low:

raise ValueError(f”solve_mod_equiv() does not support the upper bound {high} l

if m < 0:

raise ValueError(f”solve_mod_equiv() does not support negative modulo m = {m}”

a_inv = mod_inv(a, m)

k_low = “””FIXME: replace this string with the correct lower bound for k, if x = m

k_high = “””FIXME: replace this string with the correct upper bound for k, if x =

x = “””FIXME: replace this string with the Python list comprehension that uses x =

return set(x)