Math 4100 — Introduction to Number Theory

Thursday, January 15
Link to code from class.

The file linked above is the example Sage code written in class. It introduces basic arithmetic in Sage, variables, loops, if statements, lists, and functions.

Some of the particular examples given in the file are:

• Calculating the factorial recursively (Line 239)
• Determining how many steps it takes the Collatz algorithm to stop, if it stops (Line 293)
• Generating a list of primes using the sieve of Erasthosthenes (Line 346)
• Using the list generated above to get a list of twin primes (Line 400)
• Generating a list of Pythagorean triples, parametrized by rational slopes whose denominator is less than a given value (Line 417)

Due: Thursday, January 29 Extended to Tuesday, February 3

1. Create a function called euclid which takes two arguments, m and n, and returns their greatest common divisor by applying Euclid's algorithm. Your function should handle bad inputs (e.g., if m and/or n equals zero) in a "reasonable" way such as throwing an exception.
2. Create a function called diophantus which takes two arguments, a and b, and solves the Diophantine equation $ax + by = \text{gcd}(a, b)$ using the algorithm described in class where each remainder of the Euclidean algorithm was rewritten in the form $r_i = a\, x_i + b\, y_i$.
3. Create a function called improved_diophantus which takes two arguments, a and b, and solves the Diophantine equation $ax + by = \text{gcd}(a, b)$ using the algorithm described in Figure 6.1 (pg. 44) of Silverman.

Due: Tuesday, February 10

1. Create a function sundaram which takes a number n and generates a list of all the prime numbers less than $2n + 2$ by using the sieve of Sundaram. To do this, generate a list of all the integers between $1$ and $n$. Then remove all the integers of the form $i + j + 2ij$ where $i$ and $j$ are natural numbers and $i + j + 2ij \leq n$. For each number remaining in the list, double that number and add 1. This will give all of the odd primes up to $2n + 2$. Add $2$ to the front of the list, and then return this list of primes.
2. Create a function factorization_of which determines the prime factorization of a given natural number n. To do this, first generate a list of primes which are less than or equal to n using your sundaram function from problem 1. Then, for each of the prime numbers in your list, divide n by your prime as much as possible, keeping track of how many times you can divide the number by the prime. (Be careful here: You're really checking to see if n is a multiple of the given prime, so use the % operator and see if the remainder is zero or not.) Your function should return a list of pairs where the first element of the pair is the prime, and the second element of the pair is the power that prime is raised to. For example, factorization_of(528) should return the list [(2, 4), (7, 3), (13, 2)], since the prime factorization of $528$ is $2^4 \cdot 7^3 \cdot 13^2$
3. Create a function print_factorization which takes a number n and prints its prime factorization to the screen. For example, print_factorization(528) should print out 2^4 * 7^3 * 13^2. To do this, use your factorization_of function above to calculate the prime factorization, and then build a string by iterating through the array returned by factorization_of.
   
   Some hints for building the string: First create an empty string, primes = ''. You can concatenate two strings together using +; for example, 'Hello ' + 'world' results in the string 'Hello world'. To concatenate something onto the end of a string (like, say, primes) use +=. If you try to concatenate something that's not a string onto a string, Sage will complain. Convert non-string quantities (like integers) to strings using the str function; e.g., 'My favorite prime is ' + str(2).
4. Create a function phi which calculates Euler's totient function, $\phi(n)$, for a given number $n$. That is, phi should take a single argument n and return the number of integers $1 \leq a \leq n$ which are relatively prime to $n$.

Due: Thursday, February 19

1. Create a function linear_congruence which takes three numbers, a, m, c, as inputs and returns a list of all of the $x$ in $0 \leq x < m$ solving the congruence $$ ax \equiv c \text{ (mod $m$)}. $$ If there are no solutions, then return the empty list [].
   Do not do this by simply testing a*x % m == c for each $x$ between $0$ and $m-1$.
2. Create a function chinese_remainder which takes two pairs of numbers, (a, m) and (b, n) and then solves the system of congruences $$ \begin{align*} x \equiv& a \text{ (mod $m$)} \\ x \equiv& b \text{ (mod $n$)} \end{align*} $$ Throw an exception if the gcd of $m$ and $n$ is not 1.
3. Recall that if we consider the integers modulo a number $m$, then division may not be well-defined. That is, in general it is not the case that $$ ac \equiv bc \text{ (mod $m$)} $$ implies $a \equiv b \text{ (mod }m\text{)}$. However, this is true if $c$ and $m$ are relatively prime. In particular, if $m$ is a prime number, then all non-zero $x$ in $1 \leq x < m$ have a unique multiplicative inverse. For example, the multiplicative inverse of $4$ modulo $7$ is $2$, as $4 \cdot 2 \equiv 1 \text{ (mod }m\text{)}$.
   
   Write a function mod_inverse which takes two values, $a$ any integer and $p$ a prime. If $a$ is not congruent to $0$ modulo $p$, then return the unique value $1 \leq b < p$ such that $ab$ is congruent to $1$ modulo $p$. If $a$ is congruent to zero modulo $p$, then raise an exception. (Do not worry about testing if the given value of $p$ is prime: assume the user will always enter a prime value for $p$.)