Download the .ipynb file for this notebook, and place your solutions where indicated (you can make more cells for each problem), keeping the original problem descriptions. Upload only one file, which contains all your work; it should be named "HW03_firstname_lastname". Please include comments in your code; this can also help you get partial credit if your code doesn't work.
Then upload it to Blackboard as Homework 3 in the Assignments tab. See Collaboration Policy in Homework section of course webpage (it's the same as it was for previous homeworks).
Write a function extended_gcd that takes in a pair of positive integers $a,b$ and returns a pair $(e,f)$ of integers such that $ae+bf=d$, where $d$ equals $gcd(a,b)$. Do not use the builtin function xgcd (though you can use this to test your function). Use your function to find an inverse of $17$ modulo $122$, i.e. an integer $e$ such that $$17e \equiv 1 \bmod 122.$$
# Your solution goes here
Write a function num_primes(n) that returnes the number of primes that are less than or equal to $n$. For instance num_primes(5) should return $3$, since $2,3,5$ are the primes that are less than or equal to $5$. Do not use any bulit-in functions that have to do with primes (you are welcome to reuse the primality test function you wrote for a previous homework). Use it compute the ratio num_primes(n)/n for $n=10, 10^2, \ldots, 10^{5}$. Plot these ratios using the built-in list_plot command (you will need to look up the syntax, since we haven't covered this). How do you think this ratio behaves as $n\to \infty$?
# Your solution goes here
We say that two integers $a,b$ are relatively prime if $gcd(a,b)=1$ (or equivalently, they share no common prime factor). Write a function num_rel_prime(n) that returns the number of positive integers less than $n$ that are relatively prime to $n$ (where $n$ is any positive integer). For instance, num_rel_prime(6) should return $2$, since $1,5$ are the positive integers less than $6$ that are relatively prime to it. Compute num_rel_prime(n) for $$n=7,11,13,17,19,23,4,9,25,49,12,18,20,50.$$ Based on these experiments and any more that you find useful, guess a general formula for num_rel_prime(n) in terms of the prime factorization of $n$.
# Your solution goes here
(a) Write a function alt_gcd(a,b) that returns the gcd of $a,b$ (where $a,b$ are positive integers), but do NOT use the Euclidean algorithm. Rather, use the factoring function you wrote for last homework (or some modification of it); recall that if we know the prime factorizations of both $a,b$, we can find the $gcd$ by looking at the smaller power of each prime that occurs in each of $a,b$.
(b) Let $f(n)$ be the maximum of the running time of your alt_gcd(a,b) function, where $a,b$ range over all pairs of $n$ digit numbers. Using timed experiments, guess the rough order of growth of $f(n)$ as $n\to \infty$ (i.e. is it logarithmitic, linear, quadratic, exponential)? The %%time and %time commands may be useful for doing the timing.
(I am not actually asking you to compute $f$, just to guess it's order of growth. The maximum run-time for an $n$-digit number is not so different than the run-time for a random $n$ digit number, so you don't have to try all $n$ digit numbers, just a few random ones.)
# Your solution goes here