Math 361, Spring 2022, Assignment 6

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

1. Euler totient function (as examples please give one or two illustrative calculations of its values; non-examples are not sensible or needed in this case).

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

1. Theorem characterizing the units of $\mathbb{Z}_n$ (i.e. $[a]\in\mathbb{Z}_n$ is a unit if and only if...).
2. Formula for $\phi(p^k)$ when $p$ is prime.
3. Formula for $\phi(ab)$ when $\mathrm{gcd}(a,b)=1$.
4. Formula for $\phi(n)$ when the prime factorization $n=p_1^{k_1}\dots p_l^{k_l}$ is known.

Solve the following problems:

1. Make a table showing the values of $\phi(n)$ for $n\in\{1,2,3,\dots,20\}$.
2. Two students try to calculate $\phi(45)$ as follows: one says that $\phi(45)=\phi(9)\phi(5)=(3^2-3^1)(5-1)=6\times4=24$, and another says that $\phi(45)=\phi(3)\phi(15)=\phi(3)\phi(3)\phi(5)=(3-1)(3-1)(5-1)=16$. Which one is wrong, and why?
3. The table you constructed above should show that $\phi(15)=8$. Working in $\mathbb{Z}_{15}$, compute the following expressions: $1^8, 2^8, 4^8, 7^8, 8^8, 11^8, 13^8,$ and $14^8$. (Hint: there are various tricks that make these computations easier than they look. For example, when computing powers of $4$ you will quickly find that $4^2=16=1$, from which it follows that $4^8=(4^2)^4=1^4=1$. For another example, when computing powers of $14$ it will help to notice that $14=-1$. Using tricks like this, a clever person can compute all of these expressions with very little work.)
4. Based on the previous problem, try to formulate a conjecture regarding the value of the expression $a^{\phi(n)}$ in $\mathbb{Z}_n$.
5. Try to prove the conjecture you formulated above. (Hint: Lagrange's Theorem is very, very helpful.)
6. Again working in $\mathbb{Z}_{15}$, compute the expressions $3^8, 5^8, 6^8, 9^8, 10^8,$ and $12^8$. Do these contradict the conjecture you formulated above? (If so, then reformulate the conjecture. If your initial conjecture was wrong, then reformulating it may give you a crucial hint about how to prove the reformulated conjecture, since any successful proof will need to make some use of the additional hypothesis. The process of mathematical discovery often works this way---it is good to learn from one's mistakes.)

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

Definitions and Theorems:

https://drive.google.com/file/d/15F-NUWtjYWj_V5s1ZixPGkJgpyIoKfrG/view?usp=sharing

Problems:

https://drive.google.com/file/d/1aO3LiY-6kUvdmm8c2150t7D8s0QaIArN/view?usp=sharing