Lecture 05.tex

\documentclass[a4paper]{article}

\usepackage{amsmath,amsthm,amssymb, titling, mdframed}

\title{\vspace{-2cm}Lecture V\vspace{-2cm}}
\date{}

\newmdtheoremenv{theorem}{Theorem}
\newmdtheoremenv{definition}{Definition}
\newmdtheoremenv{corollary}{Corollary}
\newmdtheoremenv{algorithm}{Algorithm}
\newmdtheoremenv{lemma}{Lemma}

\begin{document}
\maketitle
\section{Lecture Summary}
\begin{theorem}
Every element in a field $\mathbb{F}$ of order $q$ satisfies the equation $x^{q^{n}} - x = 0$ for every $n \in \mathbb{N}^{+}$.
\end{theorem}


\begin{theorem}
Every irreducible polynomial of degree $d$ over a field of order $q$ divides $x^{q^{k}} - x$ if $k$ is any multiple of $d$.
\end{theorem}


\begin{theorem}
In a field of order $q$, the polynomial $x^{q^{k}} - x$ factors into the product of all monic irreducible polynomials whose degrees divide $k$.
\end{theorem}


\begin{theorem}
If $f(x)$ is an irreducible polynomial of degree $m$ over $\mathbb{Z}_{p}$ and $m$ divides $k \in \mathbb{N}^{+}$, then a field of order $p^{k}$ must contain $m$ roots of $f(x)$.
\end{theorem}


\begin{theorem}
If $p$ is a prime and $k \in \mathbb{N}^{+}$ then there exists a unique finite field of order $p^{k}$.
\end{theorem}


\begin{theorem}
Let $n \in \mathbb{N}, n \geq 2$, and $a \in \mathbb{N}^{+}$ be such that $gcd(n, a) = 1$. Then we have the following:
\begin{center}
$n$ is prime if and only if $(X + a)^{n} \equiv (X^{n} + a)$ mod $n$
\end{center}
\end{theorem}


\begin{theorem}
Modular exponentiation can be computed in time \\ $O(max\{\log{a}, \log{m}, \log{x} \}^{3})$.
\end{theorem}


\begin{definition}
\textbf{Pseudo Primes -} Let $n \in \mathbb{N}$ be an odd composite number, and let $b \in \mathbb{N}$ such that $gcd(b, n) = 1$. Then $n$ is said to be pseudo-prime to the base $b$ if $b^{n-1} \equiv 1$ mod $n$.
\end{definition}


\begin{samepage}
\begin{theorem}
Let $n \in \mathbb{N}$ be an odd composite number. Then we have \\
(1) $n$ is pseudo-prime to the base $b$ with gcd($b,n$) = $1$ if and only if the order $d$ of $b$ in $\mathbb{Z}_{n}^{*}$ divides $n - 1$.\\
(2) If $n$ is pseudo-prime to the bases $b_{1}$ and $b_{2}$ such that gcd($b_{1}, n$) = $1$ and gcd($b_{2}, n$) = $1$, then $n$ is also pseudo-prime to the bases $b_{1}, b_{2}, b_{1}b_{2}^{-1}$, and $b_{1}^{-1}b_{2}$.\\
(3) If there is a $b \in \mathbb{Z}_{n}^{*}$ satisfying $b_{n - 1} \not \equiv 1$ mod $n$, then
\begin{center}
$|\{b \in \mathbb{Z}_{n}^{*}| b^{n - 1} \not \equiv 1$ mod $n \} | \geq \frac{\varphi (n)}{2}$.
\end{center}
\end{theorem}
\end{samepage}


\begin{theorem}
Let $n \in \mathbb{N}$ be an odd composite number. Then we have \\
(1) If there is a square number $q^{2} > 1$ dividing $n$ then $n$ is not a Carmichael number. \\
(2) If $n$ is square-free, then $n$ is Carmichael number if and only if $(p - 1)$ divides $n - 1$ for every prime $p$ dividing $n$.
\end{theorem}



\section{Exercises}
\noindent \textbf{Exercise 5.1}  Let $p$ be a prime number. Then $\mathbb{Z}^{*}_{p^2}$ is cyclic.
\begin{proof}
We distinguish the cases $p = 2$ and $p > 2$.\\
Case $1$. $p = 2$\\
Since $\mathbb{Z}_{2^{2}}^{*} = \mathbb{Z}_{4}^{*} = \{1, 3 \}$, it suffices to test $3$. We compute $3^{1} \equiv 3$ mod $4$, as well as $3^2 = 9 \equiv 1$ mod $4$ and thus, $\mathbb{Z}_{2^{2}}^{*}$ is cyclic.\\
Case $2$. $p > 2$\\
By \textbf{Corollary 2 from Lecture 3} we know that $\mathbb{Z}_{p}^{*}$ is a cyclic group of order $p - 1$. Let $g \in \mathbb{Z}_{p}^{*}$ be a generator for $\mathbb{Z}_{p}^{*}$. Thus, it suffices to show the following claim:\\
Claim $1$. Either $g$ or $g + p$ is a generator for $\mathbb{Z}_{p^{2}}^{*}$.\\
Let $n$ be the order of $g$ in $\mathbb{Z}_{p^{2}}^{*}$. Then $g^{n} \equiv 1$ mod $p^{2}$, and consequently we also have $g^{n} \equiv 1$ mod $p$. So $p - 1$ must divide $n$. Moreover since $n$ is the order of $g$ in $\mathbb{Z}_{p^{2}}^{*}$, we also know that $N$ divides $\varphi (p^{2})$ (this comes from \textbf{Corollary 1 from Lecture 1}). By \textbf{Theorem 11 from Lecture 2} we know that $\varphi (p^{2}) = p(p - 1)$, and hence, $n|p(p - 1)$. Thus, we have both $(p - 1)|n$ and $n|p(p - 1)$, and consequently either $n = p - 1$ or $n = p(p - 1)$.\\
If $n = p(p - 1)$, then $g$ is also a generator for $\mathbb{Z}_{p^{2}}^{*}$, and we are done.\\
Now, assume $n = p - 1$. Therefore, we know that
$$g^{p - 1} \equiv 1\ mod\ p^{2}$$
Let $s =_{df} g + p$. Hence, $s \equiv g$ mod $p$, and so $s$ is also a generator for $\mathbb{Z}_{p}^{*}$. Using the same arguments as above we conclude that the order of $s$ in $\mathbb{Z}_{p^{2}}^{*}$ is either $p - 1$ or $p(p - 1)$. Thus it suffices to show that $s^{p - 1} \not \equiv 1$ mod $p^{2}$.\\
Using the binomial theorem we obtain
$$s^{p-1} = (g + p)^{p - 1} = \sum_{k = 0}^{p - 1} \binom{p-1}{k} g^{k}p^{p - 1 - k} \equiv g^{p - 2} \cdot p(p - 1) + g^{p - 1}\ mod\ p^{2}$$
From $g^{p - 1} \equiv 1$ mod $p^{2}$ we obtain:
$$s^{p - 1} \equiv 1 - pg^{p-2}\ mod\ p^{2}$$
Finally, suppose $s^{p - 1} \equiv 1$ mod $p^{2}$. Then we get $pg^{p - 2} \equiv 0$ mod $p^{2}$. But this means that there must be a $k$ such that $k \cdot p^{2} = pg^{p - 2}$, and consequently, $kp = g^{p - 2}$. Thus $g^{p - 2} \equiv 0$ mod $p$, a contradiction, since $g$ is a generator of $\mathbb{Z}_{p}^{*}$.\\
Taking this all together, we see that $s^{p - 1} \equiv 1 - pg^{p-2}$ mod $p^{2}$ implies $s^{p - 1} \not \equiv 1$ mod $p^{2}$, and so $s$ has order $p(p - 1)$. Hence $s$ is a generator for $\mathbb{Z}_{p^{2}}^{*}$. Consequently, $\mathbb{Z}_{p^{2}}^{*}$ is cyclic.
\end{proof}



\noindent\rule{12cm}{0.4pt}\\
\noindent \textbf{Exercise 5.2} Every Carmichael number is the product of at least 3 distinct primes.
\begin{proof}
Since Carmichael numbers are not prime, let's try to prove that there is a Carmichael number that has a form of $a=pq$, where both $p$ and $q$ are distinct prime numbers, or in other words, show that Carmichael number is product of at least two distinct primes. According to the first assertion of \textbf{Theorem 9}, Carmichael numbers are square-free, so $p$ and $q$ have to be distinct. Also, let's assume that $p$ is a larger prime of the two, in other words $p > q$.\\
According to the second assertion of the \textbf{Theorem 9} we have that $a$ is a Carmichael number iff ($p$-1) divides ($a$-1) for ever $p$ that divides $a$. For this to be true, since $a = pq$, we have:
\begin{center}
$(p-1) \mid (pq - 1)$
\end{center}
Since prime $p$ divides $pq$. From here we have that there is some integer $k$ such that:
\begin{center}
$(p-1)k = pq - 1$
\end{center}
And if we multiply $(p-1)$ with a prime $q$, we would get:
\begin{center}
$(p-1)q = pq - q$
\end{center}
If we subtract the last two equations we will get:
\begin{center}
$(p-1)(k-q) = q - 1$
\end{center}
Which would mean that $(p-1) \mid (q-1)$, which is impossible since $p$ is a larger prime of the two distinct primes. This means that there is no Carmichael number that is product of two distinct primes, meaning that Carmichael number is product of at least three distinct primes.
\end{proof}



\noindent\rule{12cm}{0.4pt}\\
\noindent \textbf{Exercise 5.3} Prove equation (2) in \textbf{Example 5.1}.
\begin{proof}
The equations (2) from the said example is as follows:
\begin{center}
$x(x + 1)(x^3 + x + 1)(x^3 + x^2 + 1) = x^8 - x$
\end{center}
over $\mathbb{Z}_{2}$. Since in $\mathbb{Z}_{2}$ 1+1 = 0, we have that:
\begin{center}
$-1 = 1$\\
$2x = 0$
\end{center}
With that in mind we can expand the left hand side of the equation:
\begin{center}
$x(x + 1)(x^3 + x + 1)(x^3 + x^2 + 1) = x^8 - x$\\
$(x^2 + x)(x^3 + x + 1)(x^3 + x^2 + 1) = x^8 - x$\\
$(x^5 + x^3 + x^2 + x^4 + x^2 + x)(x^3 + x^2 + 1) = x^8 - x$
\end{center}
Since we have that $x^2 + x^2 = 0$ over $\mathbb{Z}_{2}$ this is equal to:
\begin{center}
$(x^5 + x^4 + x^3 + x)(x^3 + x^2 + 1) = x^8 - x$\\
$(x^8 + x^7 + x^5 + x^7 + x^6 + x^4 + x^6 + x^5 + x^3 + x^4 + x^3 + x) = x^8 - x$
\end{center}
Again, considering that $2x^7=0$, $2x^4 = 0$, $2x^3 = 0$, $2x^6 = 0$ and $2x^5=0$ over $\mathbb{Z}_{2}$ this is same as:
\begin{center}
$x^8 + x = x^8 - x$
\end{center}
And since in $\mathbb{Z}_{2}$ -1 = 1, the above equation is true, which is what needed proving.
\end{proof}



\noindent\rule{12cm}{0.4pt}\\
\noindent \textbf{Exercise 5.4} Calculate $5^{71}$ mod 31 and provide your solution in the way of the example given at page 39.
\begin{proof}
We start by representing 71 in binary form. Since 71 = 64 + 4 + 2 + 1, we know that in binary system it looks like $0100\ 0111_{2}$. So after taking that $y_0 = 1$ we can calculate:
\begin{center}
$y_1 \equiv 5^1 \equiv 5$ mod 31\\
$y_2 \equiv 5^2 \equiv 25 \equiv -6$ mod 31\\
$y_3 \equiv 5^3 \equiv 125 \equiv 26 \equiv -5$ mod 31\\
$y_4 \equiv 5^4 \equiv (-6)^2 \equiv 36 \equiv 5$ mod 31\\
$y_5 \equiv 5^5 \equiv 3125 \equiv 25 \equiv -6$ mod 31\\
$y_6 \equiv 5^6 \equiv (-5)^2 \equiv 25 \equiv -6$ mod 31\\
$y_7 \equiv 5^7 \equiv 78125 \equiv 5$ mod 31\\
\end{center}
So finally we have that:
\begin{center}
$5^{71} \equiv 5^{64+4+2+1} \equiv 5^{64}5^{4}5^{2}5^{1} \equiv 5 \cdot 5 \cdot (-6) \cdot 5 \equiv 5 \cdot 5 \cdot 25 \cdot 5 \equiv 5^5$
\end{center}
So we have that $5^71 \equiv 5^5 \equiv 25$ mod 31.\\
This could also be done by noticing that 31 is a prime number, which would mean that $5^{30}$ is 1, and $5^{60}$ is $1^2$ mod 31 (\textbf{Fermat's Little Theorem}). So we would look at $5^{71}$ as $5^{11}$ mod 31.
\end{proof}



\noindent\rule{12cm}{0.4pt}\\
\noindent \textbf{Exercise 5.5} Prove Assertion (2) of \textbf{Theorem 8}. The assertion reads:
\begin{center}
If $n$ is pseudo-prime to the bases $b_1$ and $b_2$ such that gcd($b_1$, $n$) = 1 and gcd($b_2$, $n$) = 1, then $n$ is also pseudo-prime to the bases $b_{1}b_{2}$, $b_{1}b_{2}^{-1}$, and $b_{1}^{-1}b_{2}$.
\end{center}
\begin{proof}
Since $n$ is a composite number for which $b_{1}^{n-1} \equiv 1$ mod $n$ and $b_{2}^{n-1} \equiv 1$ mod $n$, or in other words $b_{1}^n \equiv b_{1}$ mod $n$ and $b_{2}^n \equiv b_{2}$ mod $n$, this implies that $(b_{1}b_{2})^n = b_{1}^{n}b_{2}^{n} \equiv b_{1}b_{2}$ mod $n$, which is same as $(b_{1}b_{2})^{n-1} \equiv 1$ mod $n$, meaning $n$ is also pseudo-prime to the base $b_{1}b_{2}$.\\
Having $n$ be pseudo-prime to the bases $b_1$ and $b_2$ implies that $b_1^{-n} = {(b_1^{n})}^{-1} \equiv b_1^{-1}$ mod $n$ and $b_2^{-n} = {(b_2^{n})}^{-1} \equiv b_2^{-1}$ mod $n$ respectively, or that $n$ is pseudo-prime to bases $b_{1}^{-1}$ and $b_{2}^{-1}$ also. From this and the proof that $n$ is pseudo-prime for the base $b_{1}b_{2}$ we have that it is also pseudo-prime for base $b_{1}b_{2}^{-1}$, and $b_{1}^{-1}b_{2}$, which is what needed proof.
\end{proof}
\end{document}