Part 0

Write a program ex0.cpp that reads $x$ and $n$ from user and prints out true if there is a multiplicative inverse of $x$ in $\mathbb{Z}_n$. We will brute force this! Just write a loop that tries each $i$ from $0$ to $n-1$ and checks whether $x*i \bmod n$ is equal to $1$ or not.

$ ./ex0 3 4 true

$ ./ex0 2 4 false

$ ./ex0 8 21 true

$ ./ex0 15 21 false

Note: I would start off writing a program that prints out "no inverse" or prints out the inverse so you can check it. For example:

$ ./a.out
5 7
3  ← since 3*5 = 15 and 15 mod 7 = 1

Part 1

Write program ex1.cpp that starts with your previous program and turns the whole thing (except for input/output) into a function. then modify the program so that it reads only $n$ from the user and prints out n : followed by a space-separate list of all the elements of $\mathbb{Z}_n$ that do not have multiplicative inverses.

$ ./ex0 4 4 : 0 2

$ ./ex0 11 11 : 0

$ ./ex0 21 21 : 0 3 6 7 9 12 14 15 18

Part 2

Write program ex2.cpp that starts with your previous program and turns the whole thing (except for input/output) into a function. Then modify the program so that it goes through "$n$" values 2 through 31 and prints out the Part 1 output for each on a separate line.

2 : ···
3 : ···
4 : 0 2 ← line for n=4 from previous part
.
.
.
31 : ···

Make a hypothesis

Make a hypothesis: for a given $n$ and $x$ in $\mathbb{Z}_n$, what determines whether $x$ has a multiplicative inverse in $\mathbb{Z}_n$?