Math and stuff

Exercise from P.140 of Modern Cryptography and Elliptic Curves - A Beginner’s Guide. For $5 \leq n \leq 15$, use your knowledge of these groups to characterize them as in the Fundamental Theorem. $U_5 = \langle 2 \rangle \cong \mathbb{Z}_4$ $U_6 = \langle 5 \rangle \cong \mathbb{Z}_2$ $U_7 = \langle...

Theorem 6.11 from P.139 of Modern Cryptography and Elliptic Curves - A Beginner’s Guide. \(\mathbb{Z}_{m} \times \mathbb{Z}_{n} \cong \mathbb{Z}_{mn}\) if and only if $\gcd(m, n) = 1$. \(\mathbb{Z}_{m} \times \mathbb{Z}_{n} \cong \mathbb{Z}_{mn}\) if and only if $(1, 1)$ is a generator. $(1, 1)$ is a generator if and only if...

Exercise from P.93 of Modern Cryptography and Elliptic Curves - A Beginner’s Guide. Find the formula for $\phi(p^r)$ for prime $p$ and $r \geq 1$. Let $a$ be an integer between 1 and $p^r$ such that $\gcd(a, p^r) \ne 1$. $\gcd(a, p^r) \mid p^r$, so $\gcd(a, p^r) = p^k$ for...

Exercise from P.94 of Modern Cryptography and Elliptic Curves - A Beginner’s Guide. When $\gcd(m, n) = 1$, $\phi(mn) = \phi(m)\phi(n)$. For any $k \in \mathbb{N}$, $U_k = \{ \lbrack a\rbrack_k \mid \gcd(a, n) = 1 \}$ as defined in the book. By Proposition 4.11, it suffices to show $\abs{U_{mn}}...

Exercise from P.71 of Modern Cryptography and Elliptic Curves - A Beginner’s Guide. Prove the Chinese Remainder Theorem. We proved the special case with $n = 2$ previously We will prove this by induction on $n$. Assume that we have proved it for some $n \geq 2$. Now, let a...