Lab 4 : Extended Euclidean algorithm and the sieve of Eratosthenes

1 Preliminaries

If you are using Python 2, add the following statement to the top of your file (if you don’t know which version you are using, there’s no harm in adding it anyway):

from __future__ import print_function

To run doctests, add the following to the bottom of your file:

if (__name__ == '__main__'):
  import doctest
  doctest.testmod(optionflags= doctest.NORMALIZE_WHITESPACE)

2 Extended Euclidean algorithm

In class we showed that for \(a,b\in\mathbb{Z}, b \neq 0\), we can always find integers \(x,y\in\mathbb{Z}\) satisfying \(\gcd(a,b) = ax + by\). We also saw how we may use the steps of a run of the Euclidean algorithm to find such \(x,y\). While in class we would wait until we had computed \(\gcd(a,b)\) before we started to compute \(x,y\), it is possible to do both at the same time.

Suppose we want to find \(x,y\) such that \(\gcd(a,b) = ax + by\). Recall when we apply the Euclidean algorithm, we generate a sequence of remainders. In fact, we can view \(a\) and \(b\) as the first and second elements in this sequence. Let us record this in a table:

i	q	r	x	y
0	0	20	1	0
1	0	16	0	1

Notice that indeed \(20 = 20\cdot 1 + 16\cdot 0\) and \(16 = 20\cdot 0 + 16\cdot 1\). Now we run the Euclidean algorithm as usual, but we update \(x\) and \(y\) at the same time.

i	q	r	x	y
0	0	20	1	0
1	0	16	0	1
2	1	4	1	-1
3	4	0	-4	5

We find \(\gcd(20,16) = 4\) on the third line. We also find the desired \(x,y\): \(\gcd(20,16) = 4 = 20 \cdot 1 + 16 \cdot (-1)\).

Now you already know how to update \(q\) and \(r\) (in your Python implementation, use the operations \\ and %.) How do we update \(x\) and \(y\)? You might have already noticed that the simplifications we would perform in class involved only the quotient and the previous coefficients. Here are the update formulas: \(x_{i+2} = x_{i} - q_{i+2} \cdot x_{i+1}\) and \(y_{i+2} = y_{i} - q_{i+2} \cdot y_{i+1}\).

Exercise 1 Write a function which takes integers \(a\) and \(b > 0\) and returns a tuple of four lists: the first contains the sequence of quotients (the \(q\) column); the second the sequence of remainders (the \(r\) column); the third the sequence of coefficients of \(a\) (the \(x\) column); the fourth the sequence of coefficients of \(b\) (the \(y\) column). (We suggest using negative list indices and append: some examples are here.)

def ext_eucl(a, b):
    """Assume b > 0.

    >>> ext_eucl(20, 16)
    ([0, 0, 1, 4], [20, 16, 4, 0], [1, 0, 1, -4], [0, 1, -1, 5])
    """

Exercise 2 Write a function which displays the main results of the extended Euclidean algorithm.

def ext_eucl_display(a, b):
  """Assume b > 0.

  >>> ext_eucl_display(120, 32)
  gcd(120, 32) = 8 = -1 * 120 + 4 * 32
  >>> -1 * 120 + 4 * 32
  8

  """

Exercise 3 Write a function which displays a run of the extended Euclidean algorithm in table form.

def ext_eucl_table(a, b):
    """Assume b > 0.

    >>> ext_eucl_table(120, 32)
      0 120   1   0
      0  32   0   1
      3  24   1  -3
      1   8  -1   4
      3   0   4 -15

    """

2 The sieve of Eratosthenes

The sieve of Eratosthenes is used to filter out all of the composite numbers from 2 to a given number \(n \geq 2\). What remains is the primes up to \(n\). For example, suppose we choose \(n = 30\). We start with

—	2	3	4	5	6	7	8	9	10
11	12	13	14	15	16	17	18	19	20
21	22	23	24	25	26	27	28	29	30

First, we remove the multiples of 2 which are greater than 2:

—	2	3	—	5	—	7	—	9	—
11	—	13	—	15	—	17	—	19	—
21	—	23	—	25	—	27	—	29	—

Then we remove the multiples of 3 which are greater than 3:

—	2	—	—	5	—	7	—	—	—
11	—	13	—	—	—	17	—	19	—
21	—	23	—	25	—	—	—	29	—

Finally, we remove the multiples of 5 which are greater than 5:

—	2	3	—	5	—	7	—	—	—
11	—	13	—	—	—	17	—	19	—
21	—	23	—	—	—	—	—	29	—

And we’re done. These are the primes up to 30. (Why is it safe to stop with 5?)

Exercise 4 Define a function which takes an integer and a list of integers and filters out all multiples of that integer.

def filter_multiples(n, l):
    """
    >>> filter_multiples(2, range(20))
    [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
    """

Exercise 5 Define a function which takes an integer greater than 1 and returns the prime numbers from 2 to that number by implementing the sieve of Eratothenes. (We suggest using range to generate the initial list of numbers: some examples are here.)

def sieve(n):
    """Assume n > 1.

    >>> sieve(40)
    [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]

    """

Exercise 6 Define a function which takes an integer greater than 1 and returns all of its prime factors in ascending order.

def factors(a):
    """Assume a > 1.

    >>> factors(20124)
    [2, 2, 3, 3, 13, 43]
    >>> factors(9973)
    [9973]

    """

Exercise 7 Define a function which takes an integer greater than 1 and displays its prime factors as a string in such a way that the output string can be evaluated to return the original input.

def display_factors(a):
    """Assume a > 1.

    >>> display_factors(20124)
    2*2*3*3*13*43
    >>> 2*2*3*3*13*43
    20124

    """

Exercise 8 Define a function which prints out the result of sieve in a table.

def sieve_table(n):
    """
    >>> sieve_table(110)
         2  3     5     7
     11    13          17    19
           23                29
     31                37
     41    43          47
           53                59
     61                67
     71    73                79
           83                89
                       97
    101   103         107   109
    >>>

    """