Math 480, Spring 2015, Assignment 2

Carefully define the following terms, then give one example and one non-example of each:

1. Fast algorithm.
2. Divisibility (of one integer by another).
3. Greatest common divisor.
4. Relatively prime.
5. Congruent modulo $m$.
6. $\mathbb{Z}/m\mathbb{Z}$ (as a structure, with addition and multiplication operations).
7. Multiplicative inverse (modulo $m$).
8. Euler totient function.

Carefully state the following theorems (you do not need to prove them):

1. Theorem on the time complexity of the Euclidean algorithm (this is the statement following item (5) in Theorem 1.7).
2. Theorem on the time complexity of exponentiation by repeated squaring.

Carefully describe the following algorithms:

1. Division with remainder.
2. Extended Euclidean algorithm.
3. Algorithms for addition, subtraction, and multiplication in $\mathbb{Z}/m\mathbb{Z}$.
4. Algorithms for inversion and division in $\mathbb{Z}/m\mathbb{Z}$.
5. Algorithm for exponentiation in $\mathbb{Z}/m\mathbb{Z}$ (by repeated squaring, not by naive multiplication).

Solve the following problems:

1. Exercises 1.6, 1.9, 1.15, and 1.16.

Coding projects:

1. (Euclidean algorithm) Implement the extended Euclidean algorithm (i.e. write a function that takes two integers $a$ and $b$ as inputs and returns integers $x$, $y$, and $d$ with $d=\mathrm{gcd}(a, b)$ and $xa + yb = d$.)

1. (Modular arithmetic) Implement the structure $\mathbb{Z}/m\mathbb{Z}$ with all of its operations (i.e. addition, subtraction, multiplication, inversion, division, and exponentiation). If your language supports object-oriented programming, then it is probably a good idea to write a class whose instances represent elements of $\mathbb{Z}/m\mathbb{Z}$. Each instance could store two integers (let's call them value and modulus) as data members, and the class could provide methods for all of the operations, as well as a method that provides a string representation for output to the screen. Your inversion method should throw an exception when called on a non-invertible element, and your remaining methods should throw exceptions when called on arguments with unequal moduli. (If your language does not support OOP, then you can implement elements of $\mathbb{Z}/m\mathbb{Z}$ as two-element structs, and just write functions for the operations. If exception handling is not available, then you can simulate exceptions by making each function return an integer status code.)

--------------------End of assignment--------------------