The Story So Far
You are a mathematician, learning to program mathematics. You mainly have access to numbers right now - your instructor hasn't covered matrices, general groups, rings or functions - so numbers are what you will practice on.
Create a file
NumberTheoryPractice.py
. Inside, write a docstring for a functionfactorial(n)
, which returns the factorial as an integer for a nonnegative integer n. Include multiple examples, including at 0.
We are going to practice recursion:
Write a function,
factorial(n)
, implementing your docstring using recursion. Use an unlimited cache to store the values.
Now let's try something a little more challenging;
Write a docstring for a function,
gcd(a,b)
, with examples including positive, negative, and zero values for a and b.
Next you will implement this function.
Write a function,
gcd(a,b)
, which computes the gcd using recursion. Remember thatgcd(a,b) = gcd(a%b,b) = gcd(a,b%a)
.
While this is likely to terminate fairly quickly for any sensible pair a,b - far apart or close together - practice rewriting it as a while
loop.
Rewrite
gcd(a,b)
using loops instead of recursion.
Often, we want more than just the gcd
- we want the coefficients. Fortunately, we can adapt this algorithm; write an implementation egcd
conforming to the following docstring:
""" Computes the Extended GCD $g$ of $a,b$. Returns $g,x,y$ with $g=ax+by$.
Parameters
----------
a : int
b : int
Returns
-------
g : int
The GCD of $a,b$ - the smallest positive integer which can be
expresssed as a linear combination of $a$ and $b$.
x : int
y : int
Coefficients such that a*x+b*y = g. Selected such that x is the
smallest possible nonnegative value.
Examples
--------
>>> egcd(0,5)
(5, 0, 1)
>>> egcd(1,2)
(1, 1, 0)
>>> egcd(4,6)
(2, 2, -1)
"""
Now that we have an extended GCD, we can:
Write an
invmod(a,m)
function which computes an integer b in the range [0,m) such that a*b = 1 mod m (in python speak, a*b%m == 1). This function should return a new type of Error namedNonInvertibleError
- a subclass of ValueError.
Now that we have this, we can:
Write a function
find_invertible_mod(candidates,m)
which takes in alist
(or other iterable) and returns the inverse of the first element in that list mod m. Use theinvmod
function. For example,find_invertible_mod(range(2,10),30)
should return 13, the inverse of 7.Make sure your functions are passing all tests, that no extra code is executed. Save and upload the
NumberTheoryPractice.py
to Brightspace.