primitive_roots_proofs.tex

\documentclass{article}
\usepackage[utf8]{inputenc}
\usepackage[english]{babel}

\usepackage{amsthm}
\usepackage{amsmath}
\usepackage[makeroom]{cancel}
\usepackage{amssymb}
\usepackage{enumitem}

\title{Primitive Roots Proofs}
\author{Karim El Shenawy}
\date{February 2021}

\usepackage{natbib}
\usepackage{graphicx}

\begin{document}

\maketitle

\section*{Introduction}
This course notebook is the collection of theorem proofs, exercises and answers from Unit 6 of the Number Theory Through Inquiry (Mathematical Association of America Textbooks).

\section*{Theorems to Mark}

\subsection*{6.4 Theorem} 
\quad \textit{Suppose p is a prime and $ord_p(a) = d$. Then for each natural number i with $(i, d) = 1, ord_p(a^i) = d$.}

\begin{proof}
Suppose p is a prime, $ord_p(a) = d$ and that $ord_p(a^i) = k$ for each natural number i. Then, by definition, $(a^i)^k \equiv 1 \;(\bmod\; p)$. This also implies that
\begin{align*}
    && (a^i)^k &\equiv 1 \;(\bmod\; p)&&\\
    && a^{ik} &\equiv 1 \;(\bmod\; p)&&
\end{align*}
Hence, $ord_p(a) = ik$ which is given as $ord_p(a) = d$. By Theorem 4.10, this implies that $d \mid ik$.\\
Now, suppose that $(i, d) = 1$. Then this implies that $d \nmid i$, thus $d \mid ik \Longrightarrow d \mid k$.\\
Moreover, since $ord_p(a) = d$ we know that $a^d \equiv 1 \;(\bmod\; p)$, which is also,
\begin{align*}
    && a^d &\equiv 1 \;(\bmod\; p)&&\\
    && (a^d)^i &\equiv 1 \;(\bmod\; p)&&\\
    && a^{di} &\equiv 1 \;(\bmod\; p)&&
\end{align*}
Then by Theorem 4.10, $k\mid d$. Therefore since $k\mid d$ and $d\mid k$, then $k = d$ which also implies that $ord_p(a^i) = ord_p(a)$.
\end{proof}

\subsection*{6.12 Lemma} 
\quad \textit{If p is a prime, then}
\begin{center}
    $\sum_{d \mid p^k} \phi(d) = p^k$
\end{center}

\begin{proof}
Given prime p, then the only possible d values where $d \mid p$ are 1 and p. Thus, by direct proof,
\begin{center}
    $\sum_{d \mid p^k} \phi(d) = \phi(1) + \phi(p) + \phi(p^2) + ... + \phi(p^k)$\\
    $= 1 + (p - 1) + (p^2 - p) + (p^3 - p^2) + ... + (p^{k-1} - p^{k-2}) + (p^k - p^{k-1})$\\
    $ = p^k$
\end{center}
\end{proof}

\subsection*{6.15 Theorem} 
\quad \textit{If n is a natural number, then}
\begin{center}
    $\sum_{d \mid n} \phi(d) = n$
\end{center}

\begin{proof}
Let n be a natural number. By the fundamental theorem of arithmetic, we know that any natural n can be expressed in terms of primes, thus $n = p_1^{r_1} \cdot p_2^{r_2} \cdot ... \cdot p_m^{r_m}, p_i \neq p_i$ for $i \neq j$ and where r and m are integers. Now suppose that $\sum_{d \mid n} \phi(d) = n$, then by direct proof,
\begin{align*}
    &&\sum_{d \mid n} \phi(d) &= (\sum_{d_1 \mid p_1^{r_1}} \phi(d_1)) \cdot (\sum_{d_2 \mid p_2^{r_2}} \phi(d_2)) \cdot ... \cdot (\sum_{d_r \mid p_m^{r_m}} \phi(d_m))&&\\
    &&\sum_{d \mid n} \phi(d) &= p_1^{r_1} \cdot p_2^{r_2} \cdot ... \cdot p_m^{r_m}&& \textbf{By Lemma 6.12}\\
    &&\sum_{d \mid n} \phi(d) &= n&&
\end{align*}
Thus, since $n = p_1^{r_1} \cdot p_2^{r_2} \cdot ... \cdot p_m^{r_m}$, $\sum_{d \mid n} \phi(d) = n$ holds.
\end{proof}

\subsection*{6.21 Theorem} 
\quad \textit{If n is a natural number, k is an integer, and m is an integer relatively prime to n, then the set of n integers}
\begin{center}
    $\{k, k+m, k+2m, k+3m,...,k+(n-1)m\}$
\end{center}
\textit{is a complete residue system modulo n.}

\begin{proof}
Assume n is a natural number, k is an integer, and m is an integer relatively prime to n. Also, suppose there exist a set A = $\{k, k+m, k+2m, k+3m,...,k+(n-1)m\}$. Suppose that $a \in A$ and thus $a \equiv k \;(\bmod\; m)$, then
\begin{align*}
    &\Longrightarrow a \equiv k \;(\bmod\; m)&\\
    &\Longrightarrow a - k \equiv 0 \;(\bmod\; m)&\\
    &\Longrightarrow m \mid a - k&\\
    &\Longrightarrow mx = a - k&\\ 
    &\textbf{By division algorithm, $\exists x \in \mathbf{Z}, 1 \leq x \leq n-1$}&\\
    &\Longrightarrow a = k + mx&\\
    &\Longrightarrow a = k, k+m, k+2m, k+3m,...,k+(n-1)m&
\end{align*}
Thus, the set A is a complete residue system modulo n.
\end{proof}

\subsection*{6.32 Theorem} 
\quad \textit{If k and n are natural numbers with $(k,\phi(n))=1$, then there exist positive integers u and v satisfying $ku = \phi(n)v+1$.}

\begin{proof}
Suppose k and n are natural numbers with $(k,\phi(n))=1$. Also suppose by Theorem 1.39, then $(k,\phi(n))=1$ can be expressed as $ku + ks = 1, \exists u,s \in \mathbf{Z}$. Therefore, there exist positive integers u and v satisfying $ku = \phi(n)(-s)+1$ where $s = -v$.
\end{proof}

\subsection*{6.37 Theorem} 
\quad \textit{If a is an integer, v is a natural number, and n is a product of distinct primes, then $a^{v\phi{(n)}+1} \equiv  a \;(\bmod\; n)$.}

\begin{proof}
Suppose $a \in \mathbf{Z}$, $v \in \mathbf{N}$ and n is the product of distinct primes. By Euler's Theorem we know that $a^{\phi(n)} \equiv 1 \;(\bmod\; n)$. Then we'll encounter 2 possible cases which we can prove by direct proof,
\begin{itemize}
    \item Case 1: if $(a,n) = 1$ with $a \neq n$, then\\
        \begin{align*}
            &&a^{\phi(n)} &\equiv 1 \;(\bmod\; n)&&\\
            &&a^{v\phi(n)+1} &\equiv a^{v\phi(n)+1} \;(\bmod\; n)&&\\
            && &\equiv 1^{v}a \;(\bmod\; n)&&\\
            && &\equiv a \;(\bmod\; n)&&
        \end{align*}
    \item Case 2: if $(a,n) \neq 1$, then\\
        \begin{align*}
            &&a &\equiv 0 \;(\bmod\; n)&&\\
            &&a^{\phi(n)} &\equiv 0 \;(\bmod\; n)&&\\
            &&a^{v\phi(n)+1} &\equiv 0\times a \;(\bmod\; n)&&\\
            && &\equiv a \equiv 0 \;(\bmod\; n)&&
        \end{align*}
\end{itemize}
\end{proof}
\section*{Practice Theorems from Polynomial Congruences and Primitive Roots}

\subsection*{6.1 Theorem} 
\quad \textit{Let $a_nx^n + a_{n-1}x^{n-1} + ... + a_0$ be a polynomial of degree $n > 0$ with integer coefficients and assume $a_n \neq 0$. Then an integer r is a root of f(x) if and only if there exists a polynomial g(x) of degree n-1 with integer coefficients such that $f(x) = (x-r)g(x)$.}

\begin{proof}
Let $f(x) = a_nx^n + a_{n-1}x^{n-1} + ... + a_0$ be a polynomial of degree $n > 0$ with integer coefficients and assume $a_n \neq 0$. Suppose that the root of $f(x)$ is the integer r, then by definition $f(r) = 0$.\\
Now, suppose we divide f(x) by (x-r), then by the remainder theorem we will get f(r) as the remainder. But since f(r) = 0, then the remainder is also 0. Therefore, f(x) is divisible by (x-r) thus $f(x) \mid (x-r)$ if $f(r) = 0$. Since, by definition, $f(x) \mid (x-r) \Longrightarrow f(x) = (x-r)g(x)$ for some polynomial g(x). This also implies that g(x) is of degree n-1 since f(x) is of degree n and (x-r) is of degree 1. Thus, there must exist a polynomial g(x) of degree n-1 with integer coefficients such that $f(x) = (x-r)g(x)$ when the integer r is a root of f(x).\\\\
Conversely, suppose g(x) exists as a polynomial of degree n-1 with integer coefficients such that $f(x) = (x-r)g(x)$, where r is an integer. By definition, x can be the root off(x) if and only if f(x) = 0, thus;
\begin{align*}
    && f(x) &= (x-r)g(x) &&\\
    && f(r) &= (r-r)g(x) &&\\
    && f(r) &= 0 \times g(x) &&\\
    && f(r) &= 0 &&
\end{align*}
Hence, r must be the root of f(x).
\end{proof}

\subsection*{6.2 Theorem} 
\quad \textit{Let $a_nx^n + a_{n-1}x^{n-1} + ... + a_0$ be a polynomial of degree $n > 0$ with integer coefficients and assume $a_n \neq 0$. Let p be a prime number and r an integer. Then, if $f(r) \equiv 0 \;(\bmod\; p)$, there exists a polynomial g(x) of degree n-1 such that}
\begin{center}
    $(x-r)g(x) = a_nx^n + a_{n-1}x^{n-1} + ... + a_1x + b_0$
\end{center}
\textit{where $a_0 \equiv b_0 \;(\bmod\; p)$.}

\begin{proof}
Let $f(x) = a_nx^n + a_{n-1}x^{n-1} + ... + a_0$ be a polynomial of degree $n > 0$ with integer coefficients and assume $a_n \neq 0$. Also let p be a prime and r an integer. If we divide f(x) by (x-r) then there must be a polynomial g(x) of degree n-1 since f(x) is of degree n and (x-r) is of degree 1, such that f(x) = (x-r)g(x) + f(r), by the remainder theorem. Also, since (x-r) is of degree 1, then f(r) must be a constant say R, f(x) = (x-r)g(x) + R.\\
We know that two polynomial are said to be equal if they have the same degree and have the same coefficients of respective terms. Clearly all the coefficients of f(x) and (x-r)g(x) are same except of the constant term. Therefore,
\begin{center}
    $(x-r)g(x) = a_nx^n + a_{n-1}x^{n-1} + ... + a_1x + b_0$
\end{center}
Then from f(x) = (x-r)g(x) + R, we have,
\begin{center}
    $a_0 = b_0 + R$\\
    $\Longrightarrow a_0 = b_0 + R \equiv b_0 \;(\bmod\; p)$\\
    $\Longrightarrow f(r) = R \equiv 0 \;(\bmod\; p)$\\
    $\Longrightarrow b_0 + A \equiv b_0 \;(\bmod\; p)$
\end{center}
Therefore, 
\begin{center}
    $(x-r)g(x) = a_nx^n + a_{n-1}x^{n-1} + ... + a_1x + b_0$
\end{center}
where $a_0 \equiv b_0 \;(\bmod\; p)$.
\end{proof}

\subsection*{6.3 Theorem (Lagrange's Theorem)} 
\quad \textit{If p is a prime and $f(x) = a_nx^n + a_{n-1}x^{n-1} + ... + a_0$ is a polynomial with integer coefficients and $a_n \neq 0$, then $f(x) \equiv 0 \;(\bmod\; p)$ has at most n non-congruent solutions modulo p.}

\begin{proof}
Suppose p is a prime and $f(x) = a_nx^n + a_{n-1}x^{n-1} + ... + a_0$ is a polynomial with integer coefficients and $a_n \neq 0$.
\end{proof}

\subsection*{6.4 Theorem} 
\quad \textit{Suppose p is a prime and $ord_p(a) = d$. Then for each natural number i with $(i, d) = 1, ord_p(a^i) = d$.}

\begin{proof}
Suppose p is a prime, $ord_p(a) = d$ and that $ord_p(a^i) = k$ for each natural number i. Then, by definition, $(a^i)^k \equiv 1 \;(\bmod\; p)$. This also implies that
\begin{align*}
    && (a^i)^k &\equiv 1 \;(\bmod\; p)&&\\
    && a^{ik} &\equiv 1 \;(\bmod\; p)&&
\end{align*}
Hence, $ord_p(a) = ik$ which is given as $ord_p(a) = d$. By Theorem 4.10, this implies that $d \mid ik$.\\
Now, suppose that $(i, d) = 1$. Then this implies that $d \nmid i$, thus $d \mid ik \Longrightarrow d \mid k$.\\
Moreover, since $ord_p(a) = d$ we know that $a^d \equiv 1 \;(\bmod\; p)$, which is also,
\begin{align*}
    && a^d &\equiv 1 \;(\bmod\; p)&&\\
    && (a^d)^i &\equiv 1 \;(\bmod\; p)&&\\
    && a^{di} &\equiv 1 \;(\bmod\; p)&&
\end{align*}
Then by Theorem 4.10, $k\mid d$. Therefore since $k\mid d$ and $d\mid k$, then $k = d$ which also implies that $ord_p(a^i) = ord_p(a)$.
\end{proof}

\subsection*{6.5 Theorem} 
\quad \textit{For a prime p and natural number d, at most $\phi(d)$ incongruent integers modulo p have order d modulo p.}

\begin{proof}
Suppose a prime p and a natural number d. By Theorem 6.4, we know that for each natural number i with $(i, d) = 1, ord_p(a^i) = d$ with $ord_p(a) = d$. Since, $(i, d) = 1$, i can only be in the range of $1 \leq i \leq d$. Moreover, by Fermat's Little Theorem, if $x^d \equiv 1 \;(\bmod\; p)$, then $ord_p(a) = d$. Thus there are exactly $\phi(d)$ a integers. Not all the powers of a will be distinct modulo p but there is at most $\phi(d)$.
\end{proof}

\subsection*{6.6 Theorem} 
\quad \textit{Let p be a prime and suppose g is a primitive root modulo p. Then the set $\{0, g, g^2, g^3,...,g^{p-1}\}$ forms a complete residue system modulo p.}

\begin{proof}
Suppose a prime b and primitive root modulo p is g, thus $g^{p-1} \equiv 1 \;(\bmod\; p)$. Given the set $G = \{0, g, g^2, g^3,...,g^{p-1}\}$. the set is a complete residue system, if every integer belongs to an element from the set.\\
By Theorem 4.4, we can deduce that there exist natural numbers i and j , with $i \neq j$, such that $g^i \equiv g^j \;(\bmod\; p)$. This implies that all elements in G are all distinct. Now let a be an integer where by the division algorithm, $a = np + r$ where $n,r \in \mathbf{Z}$ with $0 \leq r < p$. Then, $g^a \equiv g^{np+r} \equiv g^{np}g^r \equiv g^r \;(\bmod\; p)$. Thus each integer does belong to an element of the set which then implies that the set $\{0, g, g^2, g^3,...,g^{p-1}\}$ forms a complete residue system modulo p.
\end{proof}

\subsection*{6.7 Exercise} 
\quad \textit{For each of the primes p less than 20 find a primitive root and make a chart showing what powers of the primitive root give each of the natural numbers less than p.}

\begin{table}[h]
\begin{tabular}{lllllllll}
\hline
\textbf{Prime p} & \textbf{2} & \textbf{3} & \textbf{5} & \textbf{7} & \textbf{11} & \textbf{13} & \textbf{17} & \textbf{19} \\ \hline
\multicolumn{1}{|l|}{\begin{tabular}[c]{@{}l@{}}Primitive \\ Roots a\end{tabular}} & \multicolumn{1}{l|}{1} & \multicolumn{1}{l|}{2} & \multicolumn{1}{l|}{2} & \multicolumn{1}{l|}{3} & \multicolumn{1}{l|}{2} & \multicolumn{1}{l|}{2} & \multicolumn{1}{l|}{3} & \multicolumn{1}{l|}{2} \\ \hline
\multicolumn{1}{|l|}{$a^1$} & \multicolumn{1}{l|}{1} & \multicolumn{1}{l|}{2} & \multicolumn{1}{l|}{2} & \multicolumn{1}{l|}{3} & \multicolumn{1}{l|}{2} & \multicolumn{1}{l|}{2} & \multicolumn{1}{l|}{3} & \multicolumn{1}{l|}{2} \\ \hline
\multicolumn{1}{|l|}{$a^2$} & \multicolumn{1}{l|}{1} & \multicolumn{1}{l|}{1} & \multicolumn{1}{l|}{4} & \multicolumn{1}{l|}{2} & \multicolumn{1}{l|}{4} & \multicolumn{1}{l|}{4} & \multicolumn{1}{l|}{9} & \multicolumn{1}{l|}{4} \\ \hline
\multicolumn{1}{|l|}{$a^3$} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{2} & \multicolumn{1}{l|}{3} & \multicolumn{1}{l|}{6} & \multicolumn{1}{l|}{8} & \multicolumn{1}{l|}{8} & \multicolumn{1}{l|}{10} & \multicolumn{1}{l|}{8} \\ \hline
\multicolumn{1}{|l|}{$a^4$} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{1} & \multicolumn{1}{l|}{4} & \multicolumn{1}{l|}{5} & \multicolumn{1}{l|}{3} & \multicolumn{1}{l|}{13} & \multicolumn{1}{l|}{16} \\ \hline
\multicolumn{1}{|l|}{$a^5$} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{5} & \multicolumn{1}{l|}{10} & \multicolumn{1}{l|}{6} & \multicolumn{1}{l|}{5} & \multicolumn{1}{l|}{13} \\ \hline
\multicolumn{1}{|l|}{$a^6$} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{1} & \multicolumn{1}{l|}{9} & \multicolumn{1}{l|}{12} & \multicolumn{1}{l|}{15} & \multicolumn{1}{l|}{17} \\ \hline
\multicolumn{1}{|l|}{$a^7$} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{7} & \multicolumn{1}{l|}{11} & \multicolumn{1}{l|}{11} & \multicolumn{1}{l|}{14} \\ \hline
\multicolumn{1}{|l|}{$a^8$} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{3} & \multicolumn{1}{l|}{9} & \multicolumn{1}{l|}{16} & \multicolumn{1}{l|}{9} \\ \hline
\multicolumn{1}{|l|}{$a^9$} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{6} & \multicolumn{1}{l|}{5} & \multicolumn{1}{l|}{14} & \multicolumn{1}{l|}{18} \\ \hline
\multicolumn{1}{|l|}{$a^{10}$} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{1} & \multicolumn{1}{l|}{10} & \multicolumn{1}{l|}{8} & \multicolumn{1}{l|}{17} \\ \hline
\multicolumn{1}{|l|}{$a^{11}$} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{7} & \multicolumn{1}{l|}{7} & \multicolumn{1}{l|}{15} \\ \hline
\multicolumn{1}{|l|}{$a^{12}$} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{1} & \multicolumn{1}{l|}{4} & \multicolumn{1}{l|}{11} \\ \hline
\multicolumn{1}{|l|}{$a^{13}$} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{12} & \multicolumn{1}{l|}{3} \\ \hline
\multicolumn{1}{|l|}{$a^{14}$} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{2} & \multicolumn{1}{l|}{6} \\ \hline
\multicolumn{1}{|l|}{$a^{15}$} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{6} & \multicolumn{1}{l|}{12} \\ \hline
\multicolumn{1}{|l|}{$a^{16}$} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{1} & \multicolumn{1}{l|}{5} \\ \hline
\multicolumn{1}{|l|}{$a^{17}$} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{10} \\ \hline
\multicolumn{1}{|l|}{$a^{18}$} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{1} \\ \hline
\end{tabular}
\end{table}

\subsection*{6.8 Theorem} 
\quad \textit{Every prime p has a primitive root.}

\begin{proof}
Given a prime p. There are p-1 positive integers, $1,2,...,p-1$ where each of them is less than p. Also let x be a positive integer where $p-1 = xk, \exists k \in \mathbf{Z}$. Each of these will have some multiplicative order modulo p. So if we count all those of order 1, and all of those of order 2, etc. Then the total count will of course be p-1. Now, suppose that the function f(x) results to the total number of integers of order x, for example f(1) of order 1. Then,
\begin{center}
    $p-1 = \sum_{x=1}^\infty f(x)$
\end{center}
However, there will be orders that divide p-1. Thus, most terms in the sum above will be zero and only those with $x \mid p-1$ will contribute to the sum. Therefore, 
\begin{center}
    $p-1 = \sum_{x \mid p-1}^\infty f(x)$
\end{center}
This then implies that every prime will have a primitive root since $x \mid p-1$ holds for all integer values of x.
\end{proof}

\subsection*{6.9 Exercise} 
\quad \textit{Consider the prime p = 13. For each divisor d = 1,2,3,4,6,12 of 12 = p-1, mark which of the natural numbers in the set $\{1,2,3,4,5,6,7,8,9,10,11,12\}$ have order d.}

\begin{itemize}
    \item d = 1, then only 1.
    \begin{itemize}
        \item $1^1 \equiv 1 \;(\bmod\; 13)$
    \end{itemize}
    \item d = 2, then only 12.
    \begin{itemize}
        \item $12^2 \equiv 1 \;(\bmod\; 13)$
    \end{itemize}
    \item d = 3, then 3 and 9 only.
    \begin{itemize}
        \item $3^3 \equiv 1 \;(\bmod\; 13)$
        \item $9^3 \equiv 1 \;(\bmod\; 13)$
    \end{itemize}
    \item d = 4, then 5 and 8 only.
    \begin{itemize}
        \item $5^4 \equiv 1 \;(\bmod\; 13)$
        \item $8^4 \equiv 1 \;(\bmod\; 13)$
    \end{itemize}
    \item d = 6, then 4, 10, 11 and 12. 
    \begin{itemize}
        \item $4^6 \equiv 1 \;(\bmod\; 13)$
        \item $10^6 \equiv 1 \;(\bmod\; 13)$
        \item $11^6 \equiv 1 \;(\bmod\; 13)$
        \item $12^6 \equiv 1 \;(\bmod\; 13)$
    \end{itemize}
\end{itemize}

\subsection*{6.10 Exercise} 
\quad \textit{Compute each of the following sums.}

\begin{enumerate}
    \item $\sum_{d \mid 6}^\infty \phi(d)$
    \begin{align*}
        &\Longrightarrow \phi(1) + \phi(2) + \phi(3) + \phi(6)&\\
        &\Longrightarrow 1 + 1 + 2 + 2&\\
        &\Longrightarrow 6&
    \end{align*}
    \item $\sum_{d \mid 10}^\infty \phi(d)$
    \begin{align*}
        &\Longrightarrow \phi(1) + \phi(2) + \phi(5) + \phi(10)&\\
        &\Longrightarrow 1 + 1 + 4 + 4&\\
        &\Longrightarrow 10&
    \end{align*}
    \item $\sum_{d \mid 24}^\infty \phi(d)$
    \begin{align*}
        &\Longrightarrow \phi(1) + \phi(2) + \phi(3) + \phi(4) + \phi(6) + \phi(8) + \phi(12) + \phi(24)&\\
        &\Longrightarrow 1 + 1 + 2 + 2 + 2 + 4 + 4 + 8&\\
        &\Longrightarrow 24&
    \end{align*}
    \item $\sum_{d \mid 36}^\infty \phi(d)$
    \begin{align*}
        &\Longrightarrow \phi(1) + \phi(2) + \phi(3) + \phi(4) + \phi(6) + \phi(9) + \phi(12) + \phi(18) + \phi(36)&\\
        &\Longrightarrow 1 + 1 + 2 + 2 + 2 + 6 + 4 + 6 + 12&\\
        &\Longrightarrow 36&
    \end{align*}
    \item $\sum_{d \mid 27}^\infty \phi(d)$
    \begin{align*}
        &\Longrightarrow \phi(1) + \phi(3) + \phi(9) + \phi(27)&\\
        &\Longrightarrow 1 + 2 + 6 + 18&\\
        &\Longrightarrow 27&
    \end{align*}
\end{enumerate}

\textbf{Conjecture.} \textit{For a natural number n,}
\begin{center}
    $\sum_{d \mid n} \phi(d) = n$
\end{center}

\begin{proof}
We can proof this by Lemma 6.12 and by the Fundamental Theorem of Arithmetic.
\end{proof}

\subsection*{6.11 Lemma} 
\quad \textit{If p is a prime, then}
\begin{center}
    $\sum_{d \mid p} \phi(d) = p$
\end{center}

\begin{proof}
Given prime p, then the only possible d values where $d \mid p$ are 1 and p. Thus, by direct proof,
\begin{center}
    $\sum_{d \mid p} \phi(d) = \phi(1) + \phi(p) = 1 + p - 1 = p$
\end{center}
\end{proof}

\subsection*{6.12 Lemma} 
\quad \textit{If p is a prime, then}
\begin{center}
    $\sum_{d \mid p^k} \phi(d) = p^k$
\end{center}

\begin{proof}
Given prime p, then the only possible d values where $d \mid p$ are 1 and p. Thus, by direct proof,
\begin{center}
    $\sum_{d \mid p^k} \phi(d) = \phi(1) + \phi(p) + \phi(p^2) + ... + \phi(p^k)$\\
    $= 1 + (p - 1) + (p^2 - p) + (p^3 - p^2) + ... + (p^{k-1} - p^{k-2}) + (p^k - p^{k-1})$\\
    $ = p^k$
\end{center}
\end{proof}

\subsection*{6.13 Lemma} 
\quad \textit{If p and q are two different primes, then}
\begin{center}
    $\sum_{d \mid pq} \phi(d) = pq$
\end{center}

\begin{proof}
Given distinct primes p and q, then the only possible d values where $d \mid pq$ are 1, p, q and pq. Thus, by direct proof,
\begin{center}
    $\sum_{d \mid p} \phi(d) = \phi(1) + \phi(p) + \phi(q) + \phi(pq)$\\
    $= 1 + (p - 1) + (q - 1) + (p-1)(q-1)$\\
    $= p + q - 1 + pq - p - q + q$\\
    $= pq$
\end{center}
\end{proof}

\subsection*{6.14 Lemma} 
\quad \textit{If n and m are are relatively prime natural numbers, then}
\begin{center}
    $(\sum_{d \mid m} \phi(d)) \cdot (\sum_{d \mid n} \phi(d)) = (\sum_{d \mid nm} \phi(d))$
\end{center}

\begin{proof}
Considering relatively prime natural numbers n and m. Suppose 
\begin{center}
    $(\sum_{d \mid nm} \phi(d))$.
\end{center}  
By Theorem 1.3, we can express $d\mid nm$ as $d \mid n$ and $d \mid m$, thus the new sum can be,
\begin{center}
    $(\sum_{d \mid nm} \phi(d))$\\
    $\Longrightarrow (\sum_{d_1 \mid n \text{ and } d_2 \mid m} \phi(d_1d_2))$\\
    $\Longrightarrow (\sum_{d_1 \mid n \text{ and } d_2 \mid m} \phi(d_1) \phi(d_2))$\\
    $\Longrightarrow (\sum_{d_1 \mid n \text{ and } d_2 \mid m} \phi(d_1) \phi(d_2))$\\
    $\Longrightarrow (\sum_{d \mid m} \phi(d)) \cdot (\sum_{d \mid n} \phi(d))$
\end{center}
\end{proof}

\subsection*{6.15 Theorem} 
\quad \textit{If n is a natural number, then}
\begin{center}
    $\sum_{d \mid n} \phi(d) = n$
\end{center}

\begin{proof}
Let n be a natural number. By the fundamental theorem of arithmetic, we know that any natural n can be expressed in terms of primes, thus $n = p_1^{r_1} \cdot p_2^{r_2} \cdot ... \cdot p_m^{r_m}, p_i \neq p_i$ for $i \neq j$ and where r and m are integers. Now suppose that $\sum_{d \mid n} \phi(d) = n$, then by direct proof,
\begin{align*}
    &&\sum_{d \mid n} \phi(d) &= (\sum_{d_1 \mid p_1^{r_1}} \phi(d_1)) \cdot (\sum_{d_2 \mid p_2^{r_2}} \phi(d_2)) \cdot ... \cdot (\sum_{d_r \mid p_m^{r_m}} \phi(d_m))&&\\
    &&\sum_{d \mid n} \phi(d) &= p_1^{r_1} \cdot p_2^{r_2} \cdot ... \cdot p_m^{r_m}&& \textbf{By Lemma 6.12}\\
    &&\sum_{d \mid n} \phi(d) &= n&&
\end{align*}
Thus, since $n = p_1^{r_1} \cdot p_2^{r_2} \cdot ... \cdot p_m^{r_m}$, $\sum_{d \mid n} \phi(d) = n$ holds.
\end{proof}

\subsection*{6.16 Exercise} 
\quad \textit{For a natural number n consider the fractions}
\begin{center}
    $\frac{1}{n},\frac{2}{n},\frac{3}{n},...,\frac{n}{n},$
\end{center}
\textit{all written in reduced form. For example, with n = 10 we would have}
\begin{center}
    $\frac{1}{10},\frac{1}{5},\frac{3}{10},\frac{2}{5},\frac{1}{5},\frac{3}{5},\frac{7}{10},\frac{4}{5},\frac{9}{10},1$
\end{center}
\textit{Try to find a natural one-to-one correspondence between the reduced fractions and the numbers $\phi{d}$ for $d \mid n$. Show how that observation provides a very clever proof to the preceding theorem.}

We can attempt to express them as the form of pairs,
\begin{center}
    $(1,10), (1,5), (3,10), (2,5), (1,5), (3,5), (7,10), (4,5), (9,10), (1,1)$
\end{center}
This represents a one-to-one correspondence between the reduced fractions and the numbers $\phi{d}$ for $d \mid n$. Thus the preceding theorem can be proved by 
\begin{center}
    $(1,p_1^{r_1}), (2,p_1^{r_1}), ... , (m,p_m^{r_m})$.
\end{center}

\subsection*{6.17 Theorem} 
\quad \textit{Every prime p has $\phi(p-1)$ primitive roots.}

\begin{proof}
Suppose a prime p, we know by Theorem 6.8 that p has a primitive root. Now let the residues of p be $1,2,3,..,p-1$ which will have order equal to some divisor d of p-1 modulo p. Now let f(d) be the number of residues that have order d modulo p. Then,
\begin{center}
    $\sum_{d \mid p-1} f(d) = p-1$
\end{center}
Suppose that for each d of p-1, we have,
\begin{center}
    $f(d) \leq \phi(d)$.
\end{center}
By Theorem 6.15, we can then obtain,
\begin{center}
    $\sum_{d \mid p-1} f(d) \leq \sum_{d \mid p-1} \phi(d)$\\
    $p-1 \leq p-1$
\end{center}
Thus, by the central equality every prime p has $\phi(p-1)$ primitive roots must hold.
\end{proof}

\subsection*{6.18 Exercise} 
\quad \textit{Make a conjecture about the value $\phi(p)$ for a prime p.}

\textbf{Conjecture.} \textit{For a prime p, $\phi(p) = p - 1$.}
\begin{proof}
By definition, Euler's function counts the number of integers less than p that are relatively prime to p. Since, p is prime then all numbers under p are relatively prime to p thus $\phi(p) = p - 1$.
\end{proof}

\subsection*{6.19 Exercise} 
\quad \textit{Make a conjecture about the value $\phi(p^k)$ for a prime p and natural number k.}
\textbf{Conjecture.} \textit{For a prime p, $\phi(p^k) = p^k - p^{k-1}$.}

\subsection*{6.20 Theorem} 
\quad \textit{If n is a natural number and A is a complete residue system modulo n, then the number of numbers in A that are relatively prime to n is equal to $\phi(n)$.}

\begin{proof}
Let n be a natural number and A is a complete residue system modulo n. This implies that there exists numbers in A that are relatively prime to n such that $\{a \in A | (n,a) = 1, 1 \leq a \leq n\}$. By definition of Euler's function, $\phi(n)$ is equal to the number of natural numbers less than or equal to n that are relatively prime to n, thus proven.
\end{proof}

\subsection*{6.21 Theorem} 
\quad \textit{If n is a natural number, k is an integer, and m is an integer relatively prime to n, then the set of n integers}
\begin{center}
    $\{k, k+m, k+2m, k+3m,...,k+(n-1)m\}$
\end{center}
\textit{is a complete residue system modulo n.}

\begin{proof}
Assume n is a natural number, k is an integer, and m is an integer relatively prime to n. Also, suppose there exist a set A = $\{k, k+m, k+2m, k+3m,...,k+(n-1)m\}$. Suppose that $a \in A$ and thus $a \equiv k \;(\bmod\; m)$, then
\begin{align*}
    &\Longrightarrow a \equiv k \;(\bmod\; m)&\\
    &\Longrightarrow a - k \equiv 0 \;(\bmod\; m)&\\
    &\Longrightarrow m \mid a - k&\\
    &\Longrightarrow mx = a - k&\\ 
    &\textbf{By division algorithm, $\exists x \in \mathbf{Z}, 1 \leq x \leq n-1$}&\\
    &\Longrightarrow a = k + mx&\\
    &\Longrightarrow a = k, k+m, k+2m, k+3m,...,k+(n-1)m&
\end{align*}
Thus, the set A is a complete residue system modulo n.
\end{proof}

\subsection*{6.22 Exercise} 
\quad \textit{Consider the relatively prime natural numbers 9 and 4. Write down all the natural numbers less than or equal to $36 = 9 \cdot 4$ in a rectangular array that is 9 wide and 4 high. Then circle those numbers in that array that are relatively prime to 36. Try some other examples using relatively prime natural numbers.}

\begin{table}[h]
\begin{tabular}{|l|l|l|l|l|l|l|l|l|}
\hline
1 & 2 & 3 & 4 & \textcircled{5} & 6 & \textcircled{7} & 8 & 9 \\ \hline
10 & \textcircled{11} & 12 & \textcircled{13} & 14 & 15 & 16 & \textcircled{17} & 18 \\ \hline
\textcircled{19} & 21 & 22 & \textcircled{23} & 24 & \textcircled{25} & 26 & 27 & 28 \\ \hline
\textcircled{29} & 30 & \textcircled{31} & 32 & 34 & \textcircled{35} & 36 &  &  \\ \hline
\end{tabular}
\end{table}

\subsection*{6.23 Theorem} 
\quad \textit{If n and m relatively prime natural numbers, then}
\begin{center}
    $\phi(mn) = \phi(m)\phi(n)$
\end{center}

\begin{proof}
Given relatively prime natural numbers n and m. We know from Conjecture 6.19 that,
Incomplete, no clue.
\end{proof}

\subsection*{6.24 Exercise} 
\quad \textit{Compute each of the following}
\begin{enumerate}
    \item $\phi(3) = 2$
    \item $\phi(5) = 4$
    \item $\phi(15) = \phi(3)\phi(5) = 8$
    \item $\phi(45) = \phi(5)\phi(9) = 32$
    \item $\phi(98) = \phi(2)\phi(49) = 48$
    \item $\phi(5^611^417^{10}) = \phi(5^6)\phi(11^4)\phi(17^{10}) = (5^6 - 5^5)(11^4-11^3)(17^{10}-17^9)$
\end{enumerate}

\subsection*{6.25 Question} 
\quad \textit{To what power would you raise 15 to be certain that you would get an answer that is congruent to 1 modulo 98? Why?}

$15^{\phi(98)}$ and by Euler's Theorem.

\subsection*{6.26 Question} 
\quad \textit{How many primitive root does the prime 251 have?}

$\phi(251) = 250$.

\subsection*{6.27 Exercise} 
\quad \textit{Try, using paper and pencil, to solve several congruences of the form $x^k \equiv b \;(\bmod\; 5)$ and $x^k \equiv b \;(\bmod\; 6)$.}

\begin{align*}
    &&x^2 &\equiv \{2,3\} \;(\bmod\; 5)&& x = no solution\\
    &&x^3 &\equiv \{2,3\} \;(\bmod\; 5)&& x = \{3\}\\
    &&x^4 &\equiv \{2,3\} \;(\bmod\; 5)&& x = no solution\\
\end{align*}

\begin{align*}
    &&x^2 &\equiv \{2,5\} \;(\bmod\; 6)&& x = no solution\\
    &&x^3 &\equiv \{2,3\} \;(\bmod\; 6)&& x = \{1,2,3,4,5\}\\
\end{align*}

\subsection*{6.28 Exercise} 
\quad \textit{Compute $a^9 \;(\bmod\; 5)$ for several choices of a. Can you explain what happens? Now compute $a^{17} \;(\bmod\; 15)$ for several choices of a. Does your previous explanation apply here too?}

\begin{align*}
    &&2^9&\equiv 512 \equiv 2\;(\bmod\; 5)&&\\
    &&3^9&\equiv 19683 \equiv 3\;(\bmod\; 5)&&\\
    &&4^9&\equiv 262144 \equiv 4\;(\bmod\; 5)&&\\
    &&5^9&\equiv 1953125 \equiv 0\;(\bmod\; 5)&&
\end{align*}
We notice that we can compute modulo to that last digit. Also another observation is that a and modulo result matched up until 5. Therefore, my explanation is that the result of the modulo is the same as the value for a up until the modulo value.

\begin{align*}
    &&2^{17}&\equiv 131072 \equiv 2 \;(\bmod\; 15)&&\\
    &&3^{17}&\equiv 129140163 \equiv 3 \;(\bmod\; 15)&&\\
    &&4^{17}&\equiv 17179869184 \equiv 4 \;(\bmod\; 15)&&\\
    &&5^{17}&\equiv 762939453125 \equiv 5 \;(\bmod\; 15)&&\\
    &&6^{17}&\equiv 16926659444736 \equiv 6 \;(\bmod\; 15)&&\\
    &&15^{17}&\equiv 98526125335693359375 \equiv 0 \;(\bmod\; 15)&&\\
\end{align*}

Yes my explanation holds until the value of modulo which is 15.

\subsection*{6.29 Theorem} 
\quad \textit{If a is an integer and v and n are natural numbers such that $(a, n) = 1$, then $a^{v\phi{(n)}+1} \equiv  a \;(\bmod\; n)$.}

\begin{proof}
Suppose a is an integer and v and n are natural numbers such that $(a, n) = 1$. Thus with Fermat's Little Theorem and by direct proof, we have
\begin{align*}
    &&a^{\phi(n)} &\equiv 1 \;(\bmod\; n)&&\\
    &&a^{\phi(n)v} &\equiv 1^v \;(\bmod\; n)&&\\
    &&a^{\phi(n)v}\cdot a &\equiv 1^v \cdot a \;(\bmod\; n)&&\\
    &&a^{\phi(n)v + 1} &\equiv a^v \;(\bmod\; n)&&
\end{align*}
\end{proof}

\subsection*{6.30 Question} 
\quad \textit{Consider the congruence $x^5 \equiv 2 \;(\bmod\; 7)$. Can you think of an appropriate operation we can apply to both sides of the congruence that would allow us to "solve" for x? If so, is the value obtained for x a solution to the original congruence?}

\begin{align*}
    &&x^5 &\equiv 2 \;(\bmod\; 7)&&\\
    &&x^{5\phi(7)} &\equiv 2^{\phi(7)} \;(\bmod\; 7)&&\\
    &&x^{5\phi(7)}x &\equiv 2^{\phi(7)}x \;(\bmod\; 7)&&\\
    &&x^{5\phi(7)+1} &\equiv 64x \;(\bmod\; 7)&&\\
    &&x^{31} &\equiv x \;(\bmod\; 7)&&
\end{align*}
By trial and error, we conclude that x = 4.

\subsection*{6.31 Question} 
\quad \textit{Consider the congruence $x^3 \equiv 7 \;(\bmod\; 10)$. Can you think of an appropriate operation we can apply to both sides of the congruence that would allow us to "solve" for x? If so, is the value obtained for x a solution to the original congruence?}

\begin{align*}
    &&x^3 &\equiv 7 \;(\bmod\; 10)&&\\
    &&x^{3\phi(10)} &\equiv 7^{\phi(10)} \;(\bmod\; 10)&&\\
    &&x^{3\phi(10)}x &\equiv 7^{\phi(10)}x \;(\bmod\; 10)&&\\
    &&x^{3\phi(10)+1} &\equiv x \;(\bmod\; 7)&&\\
    &&x^{13} &\equiv x \;(\bmod\; 7)&&
\end{align*}
By trial and error, we conclude that x = 3.

\subsection*{6.32 Theorem} 
\quad \textit{If k and n are natural numbers with $(k,\phi(n))=1$, then there exist positive integers u and v satisfying $ku = \phi(n)v+1$.}

\begin{proof}
Suppose k and n are natural numbers with $(k,\phi(n))=1$. Also suppose by Theorem 1.39, then $(k,\phi(n))=1$ can be expressed as $ku + ks = 1, \exists u,s \in \mathbf{Z}$. Therefore, there exist positive integers u and v satisfying $ku = \phi(n)(-s)+1$ where $s = -v$.
\end{proof}

\subsection*{6.33 Exercise} 
\quad \textit{Use your observations so far to find solutions to the following congruences. Be sure to check that your answers are indeed solutions.}
\begin{enumerate}
    \item $x^7 \equiv 4 \;(\bmod\; 11)$
    \begin{itemize}
        \item $\phi(11) = 10$
        \item $7u - 10v = 1, u = 3, v = 2$
        \item $ x \equiv b^3 \;(\bmod\; 11)$
    \end{itemize}
    \begin{align*}
        &&x &\equiv 4^3 \equiv 9 \;(\bmod\; 11)&&
    \end{align*}
    \item $x^5 \equiv 11 \;(\bmod\; 18)$
    \begin{itemize}
        \item $\phi(18) = 6$
        \item $5u - 6v = 1, u = -1, v = -1$
        \item $ x \equiv b^{-1} \;(\bmod\; 11)$
    \end{itemize}
    \begin{align*}
        &&x &\equiv 11^{-1} \equiv 5 \;(\bmod\; 11)&&
    \end{align*}
    \item $x^7 \equiv 2 \;(\bmod\; 8)$
    \begin{itemize}
        \item $\phi(8) = 4$
        \item $7u - 4v = 1, u = -1, v = -2$
        \item $x \equiv b^{-1} \;(\bmod\; 8)$
    \end{itemize}
    \begin{align*}
        &&x &\equiv 2^{-1} \equiv 0 \;(\bmod\; 8)&&
    \end{align*}
\end{enumerate}

\subsection*{6.34 Question} 
\quad \textit{What hypotheses on k,b and n do you think are necessary for your method to produce a solution to the congruence $x^k \equiv b \;(\bmod\; n)$? Make a conjecture and prove it.}

\textbf{Conjecture.} \textit{Let k,b and n be natural numbers. (b, n) must be 1 to find a solution for $x^k \equiv b \;(\bmod\; b)$}

\begin{proof}
By definition of modulo, given natural numbers a and n. If $(a,n) \neq 1$, then $a \equiv 0 \;(\bmod\; b)$. Thus by Theorem 6.32, there will be no solution.
\end{proof}

\subsection*{6.35 Theorem} 
\quad \textit{If b is an integer and k and n are natural numbers such that $(k, \phi(n)) = 1$ and $(b, n) = 1$, then $x^k \equiv b \;(\bmod\; n)$ has a unique solution modulo n. Moreover, that solution is given by}
\begin{center}
    $x \equiv b^u \;(\bmod\; n)$,
\end{center}
\textit{where u and v are positive integers such that $ku = \phi(n)v+1$.}

\begin{proof}
Suppose b is an integer and k and n are natural numbers such that $(k, \phi(n)) = 1$. Then by Theorem 6.32, we know that $x^k \equiv b \;(\bmod\; n)$ has a solution modulo n. Now suppose that, $(b, n) = 1$ and that there exits two distinct solutions $x_1$ and $x_2$ such that $x_1^k \equiv b \;(\bmod\; n)$ and $x_2^k \equiv b \;(\bmod\; n)$. Therefore, by direct proof,
    \begin{align*}
        &&x_1 - x_2 &\equiv 0 \;(\bmod\; n)&&\\
        &&x_1 &\equiv x_2 \;(\bmod\; n)&&
    \end{align*}
    Thus, the solution must be unique if $(b, n) = 1$.
\end{proof}

\subsection*{6.36 Exercise} 
\quad \textit{Find the 49th root of 100 modulo 151.}

\begin{align*}
    &x^{49} \equiv 100 \;(\bmod\; 151)&\\
    &k = 49&\\
    &\phi(151) = 150&\\
    &(k, \phi(151)) = (49, 150) \Longrightarrow 49u = 150v+1 , \exists u, v \in \mathbf{Z}&\\
    &u = 49&\\
    &v = 16&\\
    &x \equiv 100^{49} \equiv 103 \;(\bmod\; 151)&
\end{align*}

\subsection*{6.37 Theorem} 
\quad \textit{If a is an integer, v is a natural number, and n is a product of distinct primes, then $a^{v\phi{(n)}+1} \equiv  a \;(\bmod\; n)$.}

\begin{proof}
Suppose $a \in \mathbf{Z}$, $v \in \mathbf{N}$ and n is the product of distinct primes. By Euler's Theorem we know that $a^{\phi(n)} \equiv 1 \;(\bmod\; n)$.
\begin{itemize}
    \item Case 1: if $(a,n) = 1$ with $a \neq n$, then\\
        \begin{align*}
            &&a^{\phi(n)} &\equiv 1 \;(\bmod\; n)&&\\
            &&a^{v\phi(n)+1} &\equiv a^{v\phi(n)+1} \;(\bmod\; n)&&\\
            && &\equiv 1^{v}a \;(\bmod\; n)&&\\
            && &\equiv a \;(\bmod\; n)&&
        \end{align*}
    \item Case 2: if $(a,n) \neq 1$, then\\
        \begin{align*}
            &&a &\equiv 0 \;(\bmod\; n)&&\\
            &&a^{\phi(n)} &\equiv 0 \;(\bmod\; n)&&\\
            &&a^{v\phi(n)+1} &\equiv 0\times a \;(\bmod\; n)&&\\
            && &\equiv a \equiv 0 \;(\bmod\; n)&&
        \end{align*}
\end{itemize}
\end{proof}

\subsection*{6.38 Theorem} 
\quad \textit{If n is a natural number that is a product of distinct primes, and k is a natural number such that $(k, \phi(n)) = 1$, then $x^k \equiv b \;(\bmod\; n)$ has a unique solution modulo n for any integer b. Moreover, that solution is given by}
\begin{center}
    $x \equiv b^u \;(\bmod\; n)$,
\end{center}
\textit{where u and v are positive integers such that $ku - \phi(n)v = 1$.}

\begin{proof}
Suppose n is natural number that is a product of distinct primes and k is a natural number such that $(k, \phi(n)) = 1$. By Theorem 1.39, we can express $(k, \phi(n)) = 1 \Longrightarrow ku + \phi(n)(-v) = 1, \exists u, v \in \mathbf{Z}$.\\
Now there exists integer b such that $(b, n) = 1$. Thus, by Theorem 6.32 and 6.37, $b^{ku} \equiv b^{v\phi{(n)}+1} \equiv  b \;(\bmod\; n)$. Now we know, using Euler's Theorem, that $b^{\phi(n)} \equiv  1 \;(\bmod\; n)$, which then can be express as,
\begin{align*}
    &&b^{\phi(n)} &\equiv  1 \;(\bmod\; n)&&\\
    &&b^{v\phi(n)} &\equiv  1^v \;(\bmod\; n)&&\\
    &&b^{v\phi(n)} &\equiv  1 \;(\bmod\; n)&&
\end{align*}

Now suppose x is the solution to $x \equiv b^u \;(\bmod\; n)$. Given $b^{ku} \equiv b \;(\bmod\; n)$, we can express it in terms of the solution x as $b^{ku} \equiv (b^u)^k \equiv x^k \equiv b \;(\bmod\; n)$. Thus, $x^k \equiv b \;(\bmod\; n)$ has a unique solution modulo n for any integer b.
\end{proof}

\subsection*{6.39 Exercise}
\quad \textit{Find the 37th root of 100 modulo 210.}

\begin{align*}
    &x^{37} \equiv 100 \;(\bmod\; 210)&\\
    &k = 37&\\
    &\phi(210) = 48&\\
    &(k, \phi(210)) = (37, 48) \Longrightarrow 37u = 48v+1 , \exists u, v \in \mathbf{Z}&\\
    &u = 13&\\
    &v = 10&\\
    &x \equiv 100^{13} \equiv 100 \;(\bmod\; 210)&
\end{align*}

\subsection*{6.40 Theorem} 
\quad \textit{Let p be a prime, b an integer, and k a natural number. Then the number of kth roots of b modulo p is either 0 or (k, p-1).}

\begin{proof}
Let p be a prime, b an integer, and k a natural number. Suppose $x^k \equiv b \;(\bmod\; p)$ has a solution where $x = a, \exists \in \mathbf{Z}$. Then the other solutions are $x = ad, \exists d \in \mathbf{Z}$ with $d^k \equiv 1 \;(\bmod\; p)$. This solution must be in the set of $\{d \;(\bmod\; p) and ord_p(d) \mid k\}$ which also implies that the set is $\{d \;(\bmod\; p), ord_p(d) \mid k and ord_p(d) \mid p-1\}$. This suggests that that the solution has to be $(k, p-1)$.
\end{proof}

\subsection*{6.41 Blank Paper Exercise} 
\begin{itemize}
    \item Modulo to the power
    \item Polynominal Modulo
    \item Canoical complete residue systems
    \item Linear Congrueneces
    \item Chinese Remainder Theorem
    \item Proof 6.23 were extremely difficult. Did not complete 
\end{itemize}

\end{document}