Problem 14
Which elements of \(Z_{35}\) do not have multiplicative inverses in \(Z_{35}\) ?
Problem 14
Show that if \(x^{n-1} \bmod n=1\) for all integers \(x\) that are not multiples of \(n\), then \(n\) is prime. (The slightly weaker statement \(" x^{n-1} \bmod n=1\) for all \(x\) relatively prime to \(n "\) does not imply that \(n\) is prime. There is a famous infinite family of numbers called Carmichael numbers that are counterexamples. [2], [13])
Problem 14
Write the \({ }_{7}\) multiplication table for \(Z_{7}\).
Problem 14
Suppose for applying RSA, \(p=11, q=23\), and \(e=13\). What is the value of \(d\) ? Show how to encrypt the message 100 and then how to decrypt the resulting message.
Problem 15
If \(k=j q+r\), as in Euclid's division theorem, is there a relationship between \(\operatorname{gcd}(j, k)\) and \(\operatorname{gcd}(r, k)\) ? If so, what is it?
Problem 17
The Fibonacci numbers \(F_{i}\) are defined as follows: $$ F_{i}= \begin{cases}1 & \text { if } i \text { is } 1 \text { or } 2 \\\ F_{i-1}+F_{i-2} & \text { otherwise. }\end{cases} $$ What happens when you run Euclid's extended GCD algorithm on \(F_{i}\) and \(F_{i+1}\) ? (This problem is asking not only for the answer but also about the execution of the algorithm.)
Problem 18
Write pseudocode to take \(m\) integers \(x_{1}, x_{2}, \ldots, x_{m}\) and an integer \(n\) and return \(\left(\Pi_{i}^{m} x_{i}\right) \bmod n .\) Be careful about overflow; in this context, being careful about overflow means that at no point should you ever compute a value that is greater than \(n^{2}\).
Problem 18
Write (and run on several different inputs) a program to implement Euclid's extended GCD algorithm. Be sure to return \(x\) and \(y\) in addition to the GCD. About how many times does your program have to make a recursive call to itself? What does that say about how long you should expect the program to run as you increase the size of the \(j\) and \(k\) whose GCD you are computing?
Problem 19
The least common multiple (LCM) of two positive integers \(x\) and \(y\) is the smallest positive integer \(z\) such that \(z\) is an integer multiple of both \(x\) and \(y\). Give a formula for the least common multiple that involves the GCD.
Problem 21
Give an example of an equation of the form \(a_{n} x=b\) that has a solution even though \(a\) and \(n\) are not relatively prime, or show that no such equation exists.
