\documentclass[11pt]{article}
\usepackage[utf8]{inputenc}
\usepackage{graphicx,amssymb,amsmath,amsthm,hyperref,setspace}
\usepackage[a4paper, total={6in, 8in}, margin=1in]{geometry}

\title{Prime Numbers and ``Euclidean'' Proofs}
\author{Nathaniel DeRousse}
\date{\textit{April 17, 2020}}

\newtheorem{theorem}{Theorem}[section]
\newtheorem{definition}{Definition}[section]
\newtheorem{corollary}{Corollary}[theorem]
\newtheorem{lemma}[theorem]{Lemma}

\begin{document}
    \maketitle
    \doublespacing
    
    \begin{abstract}
        This paper will discuss prime numbers, beginning with Euclud's proof of the infinitude of primes, and then demonstrate how this ``Euclidean'' method of proof is a powerful tool for further investigation of the properties of prime numbers commonly encountered in number theory. These properties include the infinitude of prime numbers congruent to $3\pmod{4}$ and $1\pmod{4}$, as well as more complex cases that highlight the limits of the Euclidean method of proof.
    \end{abstract}
    
    \section{Introduction}
    A prime number $p$ is a natural number that has exactly two factors, $1$ and itself. Every natural number can be formed by multiplying together prime numbers, and as such these ``building blocks of number theory'' are extremely important. \cite{Silverman} The study of prime numbers dates back to the time of Euclid, and it was Euclid himself who elegantly proved the infinitude of prime numbers.
    \begin{theorem}[Infintely Many Primes Theorem \cite{Silverman}]
        There are infinitely many prime numbers.
    \end{theorem}
    \begin{proof}
        Suppose there is a list of primes $p_1,p_2,\dots,p_r$. Let $$A=p_1p_2\cdots p_r+1.$$
        If $A$ is prime, then the initial list is incomplete, and therefore there are infinitely many primes.\par
        Suppose $A$ is not prime. Let $q$ be some prime dividing $A$, thus $$q\mid p_1p_2\cdots p_r+1.$$
        If $q$ were in our original list, then it would divide $A$, meaning it would have to divide $1$, which is impossible.\par
        So $q$ is a prime number that is not in the original list, and hence there are infinitely many primes. \cite{Silverman}
    \end{proof}
    Interestingly, the argument that Euclid uses in this famous proof can be extended further into the study of prime numbers.

    \section{More Examples of Euclidean Proofs}
    Observe in the following list of prime numbers, $$3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 83, 89, 97, 101,\dots,$$ that all of the primes are odd, because $2$ is the only even prime. Furthermore, observe that each of these numbers is either congruent to $1\pmod{4}$ or $3\pmod{4}$. \cite{Silverman} These two categories can be thought of as either $1$ more that a multiple of $4$ or $1$ less than a multiple of $4$, respectively. Physically separating the two types of primes yields the following lists:\\
    \begin{center}
        \begin{tabular} { c c }
            \hline
            $p\equiv1\pmod{4}:$ & $5, 13, 17, 29, 37, 41, 53, 61, 73, 89, 97, 101,\dots$ \\
            \hline
            $p\equiv3\pmod{4}:$ & $3, 7, 11, 19, 23, 31, 43, 47, 59, 67, 71, 79, 83,\dots$ \\
            \hline
        \end{tabular}
    \end{center}\par
    Naturally, one might wonder whether each of these more specific list of prime numbers is infinite. As it turns out, the Euclidean argument can indeed be extended to each of these cases.
    \subsection{Primes congruent to $3$ Modulo $4$}
    \begin{theorem}[Primes $3\pmod{4}$ Theorem \cite{Silverman}]
        There are infinitely many primes that are congruent to 3 modulo 4.
    \end{theorem}
    \begin{proof}
        Suppose there is a list of primes congruent to $3$ modulo $4$:  $3,p_1,p_2,\dots,p_r$. Let $$A=4p_1p_2\cdots p_r+3.$$
        Let $A$ be written as the product of prime factors such that $$A=q_1q_2\cdots q_s.$$
        Note that because $A$ is defined to be congruent to to $3\pmod{4}$, $2$ is not among its prime factors. Therefore, all of its prime factors are congruent to either $3\pmod{4}$ or $1\pmod{4}$.\par
        Now, because the product of numbers that are congruent to $1\pmod{4}$ is itself congruent to $1\pmod{4}$, one of the prime factors of $A$ must be congruent to $3\pmod{4}$ in order for $A$ to be congruent to $3\pmod{4}$.\par
        Additionally, because none of the original list of primes $3,p_1,p_2,\dots,p_r$ divides $A$, then the prime factors of $A$ are not in our original list. Thus there exists a prime number congruent to $3\pmod{4}$ that is not in the original list.\par
        Therefore, there are infinitely many primes congruent to $3$ modulo $4$. \cite{Silverman}
    \end{proof}
    The above proof is a relatively direct extension of Euclid's original argument. In contrast, the next proof utilizes another important concept in number theory while also demonstrating the flexibility of Euclid's argument.
    \subsection{Primes congruent to $1$ Modulo $4$}
    Before continuing, some familiarity with the concept of quadratic reciprocity is needed.
    \begin{definition}[Quadratic Residue \cite{Silverman}]
        A nonzero number that is congruent to a square modulo $p$ is called a \textbf{quadratic residue (QR) modulo $p$}. A number that is not congruent to a square modulo $p$ is called a \textbf{(quadratic) nonresidue (NR) modulo $p$}. 
    \end{definition}
    For example, under integers modulo $5$,
    \begin{eqnarray*}
        0^2\equiv0\pmod{5}\\
        1^2\equiv1\pmod{5}\\
        2^2\equiv4\pmod{5}\\
        3^2\equiv4\pmod{5}\\
        4^2\equiv1\pmod{5}.
    \end{eqnarray*}
    In this case, $1$ and $4$ are QRs modulo 5, and $2$ and $3$ are NRs modulo 5.\par
    In order to simplify arithmetic involving quadratic residues, a special notation is often used. Assuming that $a$ is not a multiple of $p$, the \textit{Legendre symbol} \cite{Silverman} of $a$ modulo $p$ is
    \begin{eqnarray*}
        \left(\frac{a}{p}\right) =
        \left\{\begin{array}{rl}
            1 & \text{if } a \text{ is a quadratic residue modulo } p,\\
            -1 & \text{if } a \text{ is a nonresidue modulo } p.
        \end{array}\right.
    \end{eqnarray*}\par
    Finally, one more necessary theorem:
    \begin{theorem}[Quadratic Reciprocity \cite{Silverman}]
        Let $p$ be an odd prime. Then
        \begin{center}
            $\left(\frac{-1}{p}\right)=1$ if $p\equiv1\pmod{4}$, and\\
            $\left(\frac{-1}{p}\right)=-1$ if $p\equiv3\pmod{4}.$
        \end{center}
    \end{theorem}
    With Theorem 2.2 in hand, it is now possible to prove the infinitude of $1$ modulo $4$ primes using the Euclidean argument.
    \begin{theorem}[Primes $1\pmod{4}$ Theorem \cite{Silverman}]
        There are infinitely many primes that are congruent to 1 modulo 4.
    \end{theorem}
    \begin{proof}
        Suppose there is a list of primes congruent to $1$ modulo $4$:  $p_1,p_2,\dots,p_r$. Let $$A=(2p_1p_2\cdots p_r)^2+1.$$
        Let $A$ be written as the product of prime factors such that $$A=q_1q_2 \cdots q_s.$$
        Since none of the original list of primes $p_1,p_2,\dots,p_r$ divides $A$, the prime factors of $A$ are not in our original list.\par
        Because $A$ is odd by definition, all of its prime factors $q_1,q_2,\dots,q_r$ are also odd.\par
        Now, since the prime factor $q_i$ divides $A$, $$(2p_1p_2\cdots p_r)^2+1=A\equiv0\pmod{q_i}.$$
        Let $x=(2p_1p_2 \cdots p_r)^2$ and rearrange the congruence so that $$x^2\equiv-1\pmod{q_i}\text{ or }\left(\frac{-1}{q_i}\right)=1.$$
        By Theorem 2.2, $q_i$ is therefore congruent to $1\pmod{4}$).\par
        Thus, the original list of primes is incomplete and there are infinitely many primes congruent to $1$ modulo $4$ \cite{Silverman}.
    \end{proof}
    This proof demonstrates that the Euclidean argument, simply by including other results from across number theory, can be expanded to tackle more complicated proofs, thereby demonstrating the utility and flexibility of these ``Euclidean'' proofs. However, ``Euclidean'' proofs can also be constructed for more arithmetic progressions of primes, and naturally, one might wonder how far this argument can go, with the end goal being Dirichlet's 1837 theorem which abstractly summarizes the study of prime numbers in arithmetic progressions. \cite{Silverman}
    \begin{theorem}[Dirichlet's Theorem on Primes in Arithmetic Progressions \cite{Silverman}]
        Let a and m be integers with gcd(a,m)=1. Then there are infinitely many primes that are congruent to a modulo m. That is, there are infinitely many prime numbers p satisfying $$p\equiv a\pmod{m}.$$
    \end{theorem}
    The traditional proof offered by Dirichlet for this theorem is a complicated one, involving calculus with complex numbers, and it would thus be useful to have a ``Euclidean'' proof as well. \cite{Silverman} As it turns out, this is unfortunately not possible in every case, as there are limits to the scenarios which allow use of the Euclidean argument. Before defining these limits, however, it will be necessary to extend our study of prime numbers to polynomials.
    
    \section{Prime Divisors and Polynomials}
    A polynomial's prime divisors, as well some properties involving prime divisors, will be essential in exploring the limits of the ``Euclidean'' proof.
    \begin{definition}[Prime Divisors \cite{MurtyandThain}]
        A \textbf{prime divisor} p of a polynomial f with integer coefficients is any prime number such that $p | f(n)$ for some integer n.
    \end{definition}
    As it turns out, prime divisors have some nice properties.
    \subsection{Infinitude of Prime Divisors}
    Fittingly, all non-constant polynomials with integer coefficients have an infinite number of prime divisors, and this can indeed be proven using a modified form of the Euclidean argument.
    \begin{theorem}[Infinitely Many Prime Divisors Theorem \cite{MurtyandThain}]
        If $f\in\mathbb{Z} [x]$ is non-constant, then f has infinitely many prime divisors.
    \end{theorem}
    \begin{proof}
        To begin, notice that $f$ has at least one prime divisor, because $f(x)=\pm1$ has a number of solutions that is at most the degree of $f$. Additionally, $\{f(n)\,|\,n\in\mathbb{Z}\}$ is an infinite set. Now suppose $f(0)=c\neq0$ and that f has a finite number of prime divisors $p_1, p_2,\dots,p_k$. Let $$Q=p_1p_2\cdots p_k.$$ \
        Note that $f(x)$ has the form $c_nx^n+c_{n-1}x^{n-1}+\cdots+c_1x_1+c$ and
        \begin{align*}
            f(Qcx)&=c_n(Qcx)^n+c_{n-1}(Qcx)^{n-1}+\cdots+c_1(Qcx)+c \\
            &=c[c_n(Qx)^nc^{n-1}+c_{n-1}(Qcx)^{n-1}c^{n-2}+\cdots+c_1Qx+1] \\
            &=cg(x),
        \end{align*}
        where $g(x)\in\mathbb{Z}[x]$ is of the form $1+b_1x+b_2x^2+\cdots+b_{n-1}x^{n-1}+b_nx^n$. \par
        Now, $Q|c_i$ in for each $c_i$ in $g$. Additionally, $g\in\mathbb{Z}[x]$ must have at least one prime divisor, $p$, by the argument presented above. \par
        Finally, $p|g$ implies that $p|f$ and thus $p|Q$. However, this is impossible, because $p|Q$ also implies that $p|1$ (in order for $p$ to be a prime divisor of $g$), which is a contradiction. Therefore $f$ has infinitely many prime divisors.
    \end{proof}
    This is a useful result that can be extended even further.
    \subsection{Infinite of Common Prime Divisors of Two Polynomials}
    It is also possible to prove that any two non-constant polynomials with integer coefficients share an infinite number of prime divisors. But first, some supporting lemmas:
    \begin{lemma}
        If $ax+b\in\mathbb{Z} [x]$ and $p$ is a prime such that $p\nmid a$, then $p$ is a prime divisor of $ax+b$. Hence, all but finitely may primes are divisors of $ax+b$.
    \end{lemma}
    \begin{proof}
        Let $ax+b$ be such that $a\neq0\pmod{p}$. Then there is a $c$ such that $ac\equiv-b\pmod{p}$. Now, let $x=p+c$. Then
        \begin{align*}
            ax+b&=a(p+c)+b \\
            &=ap+ac+b \\
            &\equiv0-b+b\pmod{p} \\
            &\equiv0\pmod{p}.
        \end{align*}
        Thus $p$ is a prime divisor of $ax+b$. The only primes for which this is not the case are the finite set that make up the prime factorization of $a$, and therefore there are only a finite number of primes that are not divisors of $ax+b$.
    \end{proof}
    This lemma naturally leads to the following result:
    \begin{corollary}
        If $f(x)=ax+b$ and $g(x)$ is any polynomial, then $f$ and $g$ have infinitely many common prime divisors.
    \end{corollary}
    The effect of this corollary is that we can assume in what follows that $\deg f$, $\deg g\geq2$.
    \begin{lemma}[\cite{Nagell}\cite{Loreaux}]
        When proving whether or not two polynomials $f(x)$ and $g(x)$ with degrees $N$ and $M$ have infinitely many common prime divisors, one can assume that $N>M$.
    \end{lemma}
    \begin{proof}
        Assume that $f(x)$ and $g(x)$ both have degree $N$, and construct a new function $h(x)$ such that $h(x)=af(x+c)-bg(x)$, where $a,b,c\in\mathbb{Z}$. If $f(x)=r_Nx^N+r_{N-1}x^{N-1}+\cdots+r_1x+r_0$ and $g(x)=s_Nx^N+s_{N-1}x^{N-1}+\cdots+s_1x+s_0$, then $a$ and $b$ in $h$ can be chosen so that the leading term in $f$ and $g$ drop out ($ar_Nx^N=bs_Nx^N$), and thus guaranteeing that the degree of $h(x)$ is at most $N-1$. \par
        Now, choose a $c$ and $c_1$ ($c\neq c_1$) so that $$af(x+c)-bg(x)=k,$$ $$af(x+c_1)-bg(x)=k_1,$$ where $k$ and $k_1$ are both constants. Subtracting these two quantities yields $$a(f(x+c)-f(x+c_1))=k-k_1,$$ which is also a constant. However, this is not possible, because when $N\geq2$, $f(x)$ is not linear, and thus the $N-1$ term of $a(f(x+c)-f(x+c_1))$ is not zero. So, $a(f(x+c)-f(x+c_1))$ cannot be a constant. \par
        As a result, if it is proven that $h(x)$ and $f(x)$ have infinitely many prime divisors, then $bg(x)$ and $f(x)$ do as well, because any prime divisor of $h(x)$ and $f(x)$ is a prime divisor of $bg(x)$. And because the constant $b$ has only a finite number of prime divisors, there would also therefore be an infinite number of prime divisors shared by $f(x)$ and $g(x)$.
    \end{proof}
    \begin{lemma}[\cite{Mohamed}]
    Let $f(x)$ and $g(x)$ be two non-constant polynomials with integer coefficients, and let $b$ be the leading coefficient of $g$ and $i\geq\max\{0,1+deg(f)-deg(g)\}$. Then $b^if(x)=g(x)h(x)+r(x)$ for some $h,g_1\in\mathbb{Z}[x]$ where $deg(r)<deg(g)$.
    \end{lemma}
    \begin{proof}
        This proof will be done by induction on $i$. As a base case, consider when $i=0$. In this situation, $h(x)=0$ and $r(x)=f(x)$ fulfill the necessary requirements. \par
        Now, let $i>0$ and assume that the lemma holds for all polynomials $f_0(x),g_0(x)\in\mathbb{Z}[x]$ such that their corresponding $i_0=\max\{0,1+deg(f_0)-deg(g_0)\}$ is less than $i$. Note that $i=1+deg(f)-deg(g)$, and let $N,M$ and $a,b$ be the degrees and leading coefficients of $f$ and $g$, respectively. Define $$f_1(x)=bf(x)-ax^{N-M}g(x),$$ and $$g_1(x)=g(x).$$ Note that the leading terms in $bf(x)$ and $ax^{N-M}g(x)$ are both $abx^N$, and so $f_1(x)$ has degree at most $N-1$. This also means that the corresponding $i_1=1+deg(f_1)-deg(g_1)<i$. Thus, based on our assumption, there exists polynomials $h_1(x)$ and $r_1(x)$ such that $$b^{i_1}f_1(x)=q_1(x)g(x)+r_1(x),$$ with $deg(r_1)<deg(g)$. Then
        \begin{align*}
            b^{i_1}f_1(x)&=q_1(x)g(x)+r_1(x) \\
            b^{i_1}(bf(x)-ax^{N-M}g(x))&=q_1(x)g(x)+r_1(x) \\
            b^{i_1+1}f(x)&=(q_1(x)+b^{i_1}ax^{N-M})g(x)+r_1(x) \\
            b^if(x)&=(b^{i-i_1-1}q_1(x)+ab^{i-1}x^{N-M})g(x)+b^{i-i_1-1}r_1(x),
        \end{align*}
        and letting $q(x)=b^{i-i_1-1}q_1(x)+ab^{i-1}x^{N-M}$ and $r(x)=b^{i-i_1-1}r_1(x)$, we finally have $b^if(x)=g(x)h(x)+r(x)$, where $h,r\in\mathbb{Z}[x]$ and $deg(r)<deg(g)$.
    \end{proof}
    \begin{lemma}[\cite{Nagell}\cite{Loreaux}]
        Let $f(x)$ and $g(x)$ be polynomials with integer coefficients such that $b^if(x+c)=g(x)h(x)+g_1(x)$, where $c\in\mathbb{Z}$ and $i=\max\{0,1+deg(f)-deg(g)\}$. If $g_1(x)$ has degree $M>1$, then there are only a finite number of values of c for which $g_1(x)$ is constant relative to x.
    \end{lemma}
    \begin{proof}
        Let $c$ be a value such that $g_1(x)=k(c)$, which is a polynomial only depending on $c$. Furthermore, let $\eta$ be a root of $g(x)=0$. Then the expression $b^if(x+c)=g(x)h(x)+g_1(x)$ can be written as $$b^if(\eta+c)=k(c).$$
        Now, if $\eta'$ is another root of $g(x)=0$, then we also have $$b^if(\eta'+c)=k(c).$$
        Finally, we can can construct $$f(\eta+c)-f(\eta'+c)=0,$$
        which, given $f(x)$, $\eta$, and $\eta'$, can only have a finite number of solutions in c. Therefore, there are infinitely many values of $c$ for which $g_1(x)$ is not constant.
    \end{proof}
    Finally, all of the above lemmas can be used to proof the following result:
    \begin{theorem}[Infinitely Many Common Prime Divisors Theorem \cite{Nagell}\cite{Loreaux}]
        There exist infinitely many common prime divisors of any two polynomials.
    \end{theorem}
    \begin{proof}
        Let $f(x)$ and $g(x)$ be any two polynomials with integer coefficients with degrees $N$ and $M$, respectively. By Lemma 3.3, we can assume that $N>M$. \par
        The remainder of the proof will be done through complete induction. If either polynomial is linear, then by Corollary 3.2.1, they share an infinite number of prime divisors. Thus, degrees of $N=2$ and $M=1$ provide our base case. \par
        Now, assume that the theorem is true for all pairs of polynomials whose highest degree is less that $N$. Again, consider $f(x)$ of degree $N$ and $g(x)$ of degree $M$. If $M=1$, apply Corollary 3.2.1. Then suppose $N>M>1$, and construct $$b^if(x+c)=g(x)h(x)+g_1(x),$$ where $f$, $b^i$, $g$, $g_1$, and $c$ follow the conditions of lemmas 3.2-3.5, including a choice of $c$ so that $g_1(x)$ is not constant. \par
        Let $y=x+c$. Note that $g(x)$ and $g_1(x)$ can be rearranged into functions of $x+c$. Call these new functions $g_2(y)$ and $g_3(y)$, respectively, where $g_3$ has degree at most $M-1$ and both $g_2(y)$ and $g_3(y)$ have coefficients that are polynomials in $c$. Based on our assumption, since both $g_2(x)$ and $g_3(y)$ have degree less than $N$, the theorem holds for these two polynomials. Furthermore, if a prime $p$ is one of the common prime divisors of $g_2$ and $g_3$, then it must also be a prime divisor of $b^if(x+c)=b^if(y_0)$. Thus, because Lemma 3.5 guarantees that there are an infinite number of values of $c$ for which this argument holds, and since $b^i$ has only a finite number of prime divisors, $f$ and $g$ have infinitely many common prime divisors.
    \end{proof}
    \section{Limits of the Euclidean Argument}
    While the results of the results of the preceding section are essential to achieving our primary goal, we will still need to make use of two more results. Their proofs are outside of the scope of this paper and will therefore be omitted.
    \begin{theorem}[\cite{MurtyandThain}]
        Let $H$ be a subgroup of $(\mathbb{Z}/k\mathbb{Z})$*. Then there is an irreducible polynomial $f$ so that all the prime divisors of $f$, with a finite number of exceptions, belong to the residue class of $H$. Any such prime divisor belonging to any residue class of $H$ divides $f$.
    \end{theorem}
    As an example, consider the subgroup $H=\{1,3\}$ in $(\mathbb{Z}/k\mathbb{Z})$* and the irreducible polynomial $f(x)=4x+3$. Any prime $p$ that divides $f$ is either $1\pmod{4}$ or $3\pmod{4}$ (with only a finite number of exceptions). In addition, if any prime is $1\pmod{4}$ or $3\pmod{4}$, it is guaranteed to divide $f$. \par
    There is also one specific case of of this theorem that will be needed in the final proof. Recall that the roots of the $k$-th cyclotomic polynomial $\phi_k$ are exactly the primitive $k$-th roots of unity. We then have the following:
    \begin{corollary}
        If $\phi_k$ is the $k$-th cyclotomic polynomial, then all of the prime divisors of $\phi_k$ are $\equiv 1\pmod{k}$ or divide $k$. 
    \end{corollary}
    An immediate consequence of Corollary 4.1.1 is that there are infinitely many prime divisors of $\phi_k$ that are congruent to $1\pmod{k}$. This is because there are only a finite number of primes that divide $k$, and we have already proven that $\phi_k$ must have infinitely many prime divisors. Combining this logic with that of Theorem 3.6, because any two polynomials have an infinite number of common prime divisors, \textit{any} polynomial with integer coefficients must have infinitely many prime divisors that are congruent to $1\pmod{k}$. With this remarkable result in hand, we finally have the tools necessary to prove to define the limits of ``Euclidean'' proofs. The proof that follows is very close to the one given by Murty and Thain, as some of the techniques that are used are very sophisticated.
    \begin{theorem}[\cite{MurtyandThain}]
        If $l^2\equiv1\pmod{k}$ then there are infinitely many primes $\equiv l\pmod{k}$, provided there is at least one.
    \end{theorem}
    \begin{proof}
        Let $l$ be an integer. If $l\equiv1\pmod{k}$, apply Corollary 4.1.1. Thus we are left with the case in which $l$ is not congruent to $1\pmod{k}$. \par
        We will now consider two groups: the group $(\mathbb{Z}/k\mathbb{Z})$*, which is the integers modulo $k$, and one of its subgroups $H=\{1,l\}$. Now, letting $\zeta$ be a primitive $k$-th root of unity, construct the term $h(\zeta)=(u-\zeta)(u-\zeta^l)$, with $u$ to be chosen momentarily. If $m_1,m_2,\dots,m_s$ are the coset representatives of $H$ in $(\mathbb{Z}/k\mathbb{Z})$*, then we want to choose $u$ so that $h(\zeta^{m_i})$ is distinct for $i=1,2,\dots,s$. The case in which they are not distinct is only possible for a finite number of choices of $u$. Then, according to Theorem 4.1 with subgroup $H$ and $\eta=h(\zeta)$, there exists a polynomial $$f(x)^2=\prod_{(a,k)=1}(x-(u-\zeta^a)(u-\zeta^{la})),$$ whose prime divisors, except for a finite number, are congruent to $1$ or $l\pmod{k}$. Additionally, $f(0)=\phi_k(u)$, where $\phi_k(u)$ is the $k$-th cyclotomic polynomial. If we then let $u$ be a non-zero multiple of $k$, then $f(0)=\phi_k(u)\equiv1\pmod{k}$. Thus every prime divisor $p$ of $f(0)$ is such that $p\equiv1\pmod{k}$, because Corollary 4.1.1 guarantees that every prime divisor of $\phi_k$ is either congruent to $1\pmod{k}$ or is a multiple of $k$. \par
        We will now consider a prime $p\equiv l\pmod{k}$ that does not divide the discriminant of $f$. By Theorem 4.1, $p\mid f(b)$ for some $b\in\mathbb{Z}$. If $p^2\mid f(b)$, then $f(b+p)=f(b)+pf'(b)\equiv pf'(b)\pmod{p^2}$. However, $f'(b)\neq 0\pmod{p^2}$, because $p\nmid D(f)$ implies that $f$ can have no double roots modulo $p$. Thus, it follows from $f(b)\equiv 0\pmod{p^2}$ that $f(b+p)\neq 0\pmod{p^2}$. In this case, replace $b$ with $b+p$ so that the choice of $b$ is always such that $p^2\nmid f(b)$. \par
        Finally, we proceed with a ``Euclidean'' argument: assume there are a finite number of primes congruent to $l$ modulo $k$, $p,p_1,\dots,p_m$. Additionally, let $q_1,q_2,\dots,q_t$ be the prime divisors of $D(f)$ and $$Q=p_2p_3\cdots p_mq_1q_2\cdots q_t.$$ Note that $p^2$ and $kQ$ are relatively prime, and thus by the Chinese Remainder Theorem there exists a $c$ such that $c\equiv b\pmod{p^2}$ and $c\equiv 0\pmod{kQ}$. This also implies that $f(c)\equiv f(b)\pmod{p^2}$ and $f(c)\equiv f(0)\pmod{kQ}$. As already mentioned, all but a finite number of the prime divisors of $f$ are congruent to either $1$ or $l$ modulo $k$. This remaining finite set of primes must either divide $k$ or the discriminant of $f$. Because $f(0)$ is only divisible by primes that are congruent to $1$ modulo $k$, so is $f(c)$. Also $p^2\nmid f(c)$, which implies that $f(c)\equiv l\pmod{k}$. But $f(c)\equiv f(0) \equiv1 \pmod{k}$, which is a contradiction. Therefore, there must be infinitely many prime numbers congruent to $l$ modulo $k$.
    \end{proof}
    This theorem has established the cases in which the conditions exist for the creation of a ``Euclidean'' proof for the infinitude of arithmetic progressions of prime numbers. While it is unfortunate that this argument cannot be universally applied, it still provides a relatively simple and elegant method of proof for many progressions. As a final demonstration of this fact, we will return to the proof of Theorem 2.1 ($3\pmod{4}$ primes) and restructure it to use the methods of the above proof. The same basic method can be applied to any progression that is guaranteed to work by Theorem 4.2.
    \begin{proof}
        We are considering the subgroup $H=\{1,3\}$ of $(\mathbb{Z}/4\mathbb{Z})$*. First, note that $3^2=9\equiv1\pmod{4}$, which is why we can use the methods of Theorem 4.2 to reprove this result. Let $\zeta=i$ and construct the polynomial
        \begin{align*}
            f(x)&=x-(u-\zeta)(u-\zeta^3) \\
            f(x)&=x-(u-i)(u-i^3) \\
            f(x)&=x-(u^2-iu+iu+1) \\
            f(x)&=x-u^2-1.
        \end{align*}
        Since $1$ and $2$ are the coset representatives of $H$, we must choose a $u$ such that $f(\zeta^1)=f(i)$ and $f(\zeta^2)=f(-1)$ are distinct. This is clearly the case for $u=4$, so we now have $f(x)=x-17$. \par
        Now, notice that $2$ is not a prime divisor of the translation $f(4x+20)=4x+3$, and so all of its prime divisors are either $1\pmod{4}$ or $3\pmod{4}$. Additionally, $f(4x+20)\equiv3\pmod{4}$, so not all of its prime divisors are $1\pmod{4}$. Suppose that $f(4x+20)$ has a finite number of prime divisors congruent to $3\pmod{4}$ and let $Q$ be their product. Then consider $f(4Q+20)=4Q+3$, which is clearly $3\pmod{4}$. But, $Q$ and $4Q+3$ are coprime, so it has no prime divisor that is $3\pmod{4}$. This is a contradiction, and we have thus proven the infinitude of $3\pmod{4}$ primes.
    \end{proof}
    \section{Conclusions}
    Euclid, when proving that there is an infinite number of prime numbers, formulated an argument whose utility remained untapped for many years. Throughout this paper, that utility has been demonstrated by proving the infinitude of different categories of prime numbers, including the abstract case. Murty and Thain established that these proofs can only be constructed for a progression $l\pmod{k}$ if $l^2\equiv1\pmod{k}$. However, despite this limit, the Euclidean technique provides both elegant and relatively simple proofs when compared to alternative methods, and at the same time demonstrates that proof techniques can be have many useful applications beyond their original use.
    
    \begin{thebibliography}{2}
        \bibitem{Silverman} Joseph Silverman, \textit{A Friendly Introduction to Number Theory} p.83-140, Pearson, Boston, 4th edition, 2011.
        \bibitem{MurtyandThain} M.R. Murty; N. Thain, \textit{Prime Numbers in Certain Arithmetic Progressions}, Funct. Approx. Comment. Math. 35 (2006), 249-259.
        \bibitem{wolfram} Eric W. Weisstein. \textit{Cyclotomic Polynomial}. \\ URL: http://mathworld.wolfram.com/CyclotomicPolynomial.html.
        \bibitem{Nagell} T. Nagell, \textit{Sur les diviseurs premiers des polyn\^omes}, Acta Arith, 15(1969), 2 35–244.
        \bibitem{Loreaux} T. Nagell; Jireh Loreaux, \textit{On the prime divisors of polynomials}, 2020.
        \bibitem{Mohamed} Mohamed Ayad; Omar Kihel; Jesse Larone, \textit{When Does a Given Polynomial with Integer Coefficients Divide Another?}, The American Mathematical Monthly (2016), 123:4, 376-381, DOI: 10.4169/amer.math.monthly.123.4.376
    \end{thebibliography}
\end{document}