\documentclass[10pt]{article}

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{0in}
\setlength{\evensidemargin}{0in}

\usepackage{amsmath,amscd,amsthm,amsfonts,amssymb}

\theoremstyle{definition}
\newtheorem{rem}{Remark}
\newtheorem{com}{Comment}
\newtheorem{defn}{Definition}
\theoremstyle{plain}
\newtheorem{thm}{Theorem}
\newtheorem{lem}{Lemma}
\newtheorem{cor}{Corollary}
\newtheorem{prop}{Proposition}

\renewcommand{\P}{\mathbb{P}^1}
\renewcommand{\k}{\kappa}
\renewcommand{\H}{\mathbb{H}}
\newcommand{\F}{\mathbb{F}}
\newcommand{\M}{\mathfrak{M}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\C}{\mathbb{C}}
\newcommand{\CC}{\mathcal{C}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\G}[1]{\Gamma(#1)}
\newcommand{\GO}[1]{\Gamma_0(#1)}
\newcommand{\Gb}[1]{\bar{\Gamma}(#1)}
\newcommand{\PSL}[1]{\mathbf{PSL}_2(#1)}
\newcommand{\z}{\zeta}
\renewcommand{\t}{\theta}
\renewcommand{\r}{\rho}
\newcommand{\sfrac}{\genfrac{}{}{0pt}{}{}{+}}
\DeclareMathOperator{\deck}{Deck}
\DeclareMathOperator{\aut}{Aut}
\DeclareMathOperator{\id}{id}
\DeclareMathOperator{\gal}{Gal}
\DeclareMathOperator{\ord}{ord}
\DeclareMathOperator{\GL}{GL}
\DeclareMathOperator{\Hom}{Hom}
\DeclareMathOperator{\End}{End}
\DeclareMathOperator{\im}{Im}
\DeclareMathOperator{\lcm}{lcm}
\author{Bryden R. Cais}
\title{Math 575 Sample Midterm Problem Solutions}
\begin{document}
\maketitle

\begin{enumerate}
    \item \begin{enumerate}
            \item Without loss of generality we may assume that $i>j$.  Then
            $$E_i=E_j\prod_{\substack{0\leq k < n\\k\neq j}} E_k+1=E_j x+1.$$
            It follows that if $d|E_i,E_j$ then $d|1=E_j x-E_i$.

            \item We know that every integer has a prime factor.  Let $p_j$ be
            any prime factor of $E_j$.  Then $p_j\neq p_i$ for $i\neq j$
            since then $p_j|(E_i,E_j)$ which by part a) is impossible.
            Hence there are infinitely many primes.
            \end{enumerate}
    \item Suppose that $x\equiv a\mod m,x\equiv b\mod n$ has a solution with $m,n\geq 1$ and $(m,n)=g$.
        \begin{enumerate}
            \item Observe we have $x+um=a,x+vn=b$ for integers $u,v$.  Since $g|m,n$ we have
            $x\equiv a\mod g,x\equiv b\mod g $ and therefore $a\equiv b\mod g.$
            \item Now suppose that $a\equiv b\mod g$ and let $u,v$ be any integers satisfying
            $mu+nv=g.$  Observe that
            $$x=\frac{anv+bmu}{g}$$ is an integer since $g|m$ and $g|n$.
            We then have
            $$x-a=\frac{anv-ag+bmu}{g}=\frac{-amu+bmu}{g}=mu\frac{b-a}{g}$$
            and
            $$x-b=\frac{anv+bmu-bg}{g}=\frac{anv-bnv}{g}=nv\frac{a-b}{g}.$$
            Since $a\equiv b\mod g$, we see that $\frac{a-b}{g}$ is an integer
            and thus that $x-b\equiv 0\mod n,x-a\equiv 0\mod m$.

            \item By parts a),b) we begin by finding integers $u,v$ such that $30u+9v=3$, or equivalently,
            integers $u,v$ so that $10u+3v=1$.  Applying the Euclidean algorithm, we compute

            \begin{center}
            \begin{tabular}{rcccr}
            $i$ & $q_{i+1}$ & $r_i$ & $x_i$ & $y_i$\\
            \hline
            -1 & & 10 & 1 & 0\\
            0 & 3 & 3 & 0 & 1\\
            1 & 3 & 1 & 1 & -3\\
              &   &  0 &  &
            \end{tabular}
            \end{center}
            to find that $u=1,v=-3$ works.  We then set $$x=\frac{7\cdot 9\cdot (-3)+1\cdot 30\cdot 1}{3}=-63+10=-53.$$
            Therefore, every solution is given by
            $$-53+\lcm(m,n)k=-53+90k$$ for any integer $k$.
        \end{enumerate}

    \item The proof follows Euclid's proof of the infinitude of primes with a slight modification.  Suppose there were only
    finitely many primes congruent to $1$ modulo 4, say $p_1,\ldots,p_k$. Set
    $$n=(2\prod_{i=1}^k p_i)+1$$ and observe that $n\equiv 1\mod 4.$  Let $p$ be any prime divisor of $n$; since
    $n\equiv 1\mod p_i,$ the prime $p$ is distinct from every $p_i$.  Observe
    that since $p|n$, we have that $-1$ is a square modulo $p$ and hence that $p\equiv 1\mod 4$.

    \item \begin{itemize}
            \item $a$ is a primitive root modulo $m$ if and only if every unit $u$ modulo $m$ is some power of $a$.
            \item We know that the order divides $23-1=22.$  So it is one of $1,2,11,22.$  We can immediately
            rule out $1,2$, while a short calculation shows that $2^11=2048\equiv 1\mod 23$ so that the order of $2$
            modulo 23 is 11.
            \item Observe that $5^2\equiv 2\mod 23$.  Thus, $5^11\equiv 2^5\cdot 5\equiv 9\cdot 5\equiv -1\mod 23$.
            It follows that $5$ is a primitive root.  Notice that it isn't enough to argue that because $2$ has order
            11,  5 mush have order 22.  For example, 4 has order 11 but 2 is not a primitive root.
        \end{itemize}

    \item We compute
            \begin{center}
            \begin{tabular}{rccrr}
            $i$ & $q_{i+1}$ & $r_i$ & $x_i$ & $y_i$\\
            \hline
            -1 & & 69 & 1 & 0\\
            0 & 4 & 15 & 0 & 1\\
            1 & 1 & 9 & 1 & -4\\
             2 &  1 &  6 & -1 & 5\\
             3 &  2  &  3 &  2  & -9 \\
             4 &     &  0  &    &
            \end{tabular}
            \end{center}
    and therefore conclude that $x=2,y=-9$ is a solution.

    \item We want to find integers $x,y$ such that
    $$44x+17y=1,$$ so we use Euclid's algorithm to find
                \begin{center}
            \begin{tabular}{rccrr}
            $i$ & $q_{i+1}$ & $r_i$ & $x_i$ & $y_i$\\
            \hline
            -1 & & 44 & 1 & 0\\
            0 & 2 & 17 & 0 & 1\\
            1 &  1& 10 & -2 & 1\\
             2 &  1 &  7 & 3 & -1\\
             3 &  2  &  3 &  -5  & 2 \\
             4 &   3  &  1  &   13 & -5\\
             5 &      & 0   &      &
            \end{tabular}
            \end{center}
    and hence that 13 is the inverse of 17 modulo 44.

    \item Suppose that $dk=n$ for integers $d,k$ with $d,k>1$.  Then
    $$2^{n}-1=2^{dk}-1=(2^d-1)(2^{(k-1)d}+2^{(k-2)d}+\cdots + 2^d+1).$$
    Since $n>d>1,$ we see that $1< 2^d-1<2^n-1$ so that $2^n-1$ is composite.  This is the contrapositive of the
    statement of the problem.

    \item Yes.  Observe that $4010=2\cdot 5\cdot 401,$ and 401 is prime.  It is not hard to see that
    $$401=20^2+1^2,\ 5=2^2+1^2,\ 2=1^2+1^2,$$ so that
    $$4010=(20+i)(2+i)(1+i)(20-i)(2-i)(1-i)=(17+61i)(17-61i)$$
    so that $4010=17^2+61^2.$  (there are other representations, depending
    on which non-conjugate gaussian integers you choose from the above product.

    \item \begin{enumerate}
        \item The same proof that works in the integers works here.  Suppose not.  Let $S$ be the set of
        all elements of $E$ that do not have a prime factor and suppose that $S$ is nonempty.  Then
        $S$ has a least element by the well ordering principal, call it $r$.  Then since $r$ does not
        have a prime factor, $r$ is not prime.  So we write $r=ab$ with $a,b<r$ (and $a,b\in E$).
        Then since $a<r$, $a\not \in S$ so $a$ has a prime factor, say $p$.  Since $p$ divides $a$ and
        $a$ divides $r$, $p$ divides $r$.  This is a contradiction and $S$ is empty.  Now by induction
        you can show that every element of $E$ has a prime factorization.  Clearly, $2$ is the smallest element
        of $E$ and $2$ is prime, so it has a prime factorization.  Let $M$ be a positive integer and suppose that
        every element of $E$ that is less than $2M-1$ has a prime factorization.  We know that $2M\in E$ and $2M$ has
        a prime factor, say $p$.  Since $p\in E$, $p$ is at least $2$ so that $2M/p \leq M.$  By hypothesis,
        $2M/p$ has a prime factorization, say $2M/p=q_1\cdots q_k.$  Then $2M=pq_1\cdots q_k$ is a prime factorzation
        of $2M$ and we are done.
        \item We have $6\cdot 10=2\cdot 30.$
    \end{enumerate}

    \item Since 101 is prime, Wilson's theorem tells us that $100!\equiv -1\mod 101.$  Let us compute the inverse of
    $100$ modulo 101.  Observe that $100\equiv -1\mod 101$ so that $100^2\equiv 1\mod 101$.  It follows that the inverse of 100
    modulo 101 is 100 and hence that
    $$99!\equiv -100\equiv 1\mod 101.$$

    \item Since $99=9\cdot 11$, it suffices (by the chinese remainder theorem) to determine the number of solutions
    to $f(x)=45x^{10}-11x^2-1\equiv 0$ modulo $9$ and $11$.  The number of solutions modulo 99 is then the product the number of solutions
    modulo 9 and 11.  Observe that $f(x)\equiv x^2-1\mod 3$ and $f(x)\equiv x^10-1\mod 11.$  Since
    $f^{\prime}(x)\equiv 2x\mod 3$ is not zero for $x=\pm 1$, the number of solutions of $f(x)\equiv 0\mod 9$ is the same as the
    number of solutions of $f(x)\equiv 0\mod 3$; that is, 2.  Also, since $a^{10}-1\equiv 0\mod 11$ for all $a$ not divisible by $11$
    by Fermat's little theorem, we see that $f(x)\equiv 0\mod 11$ has 10 solutions.  Therefore, $f(x)\equiv 0\mod 99$ has 20 solutions.

    \item Since 401 is (still) prime, we know that we have a primitive root $g$ modulo 401.  Then $g$ has order 400.  An
    Since $g$ is a generator, an element $x$ has order $20$ if and only if $x\equiv g^{20k}\mod 401$ where $(k,20)=1$.  We need only
    consider $k<20$ since $g^{401}\equiv g\mod 401$.  Moreover, since $g$ has order $401$, $g^{20i}\not\equiv g^{20j}\mod 401$
    if $i,j<20$ unless $i=j$.  Therefore, the number of elements of order $20$ is the number of positive integers less than and
    relatively prime to 20; that is $\phi(20)=\phi(2^2\cdot 5)=\phi(2^2)\phi(5)=2(2-1)(5-1)=8$.

    \item False, in general.  It is true if we require that $m$ be prime.  For example, $8=2^2+2^2$ but the squares modulo $8$
    are $\{0,1,4\}$.

    \item Suppose that $(u,v)=1$ and that $u|vw$ for integers $u,v,w$.  Then we claim that $u|w$.  Since $(u,v)=1$, there
    exist integers $x,y$ such that $ux+vy=1$.  Hence, $uwx+vwy=w$.  Since $u|u$ and $u|vw$ we must have $u|w$ as claimed.
    Now if $a|bc$ then $a|b(a,c)c^{\prime}$, where $c^{\prime}=c/(a,c)$ is clearly relatively prime to $a$.  It follows from
    our claim that $a|b(a,c)$.  For the converse, simply note that $b(a,c)|bc$ since $(a,c)|c$.

    \item We take logs of both sides (to base 3) and obtain
    $2x\equiv 8\mod 16$ (Since 3 is a primitive root, we must have $3^{8}=-1$ since $3^8$ is either 1 or $-1$.
    Therefore, we must have $x\equiv 4\mod 8$ so $x\equiv 4,12 \mod 16$.

    \item Observe that $1199\equiv -1\mod 400$.  Since $3^{400}\equiv 1\mod 401$ we see that
    $3^{1199}\equiv 3^{-1}\mod 401$.  Since $402=3\cdot 134$ we see that $3^{-1}\equiv 134\mod 401$
    so that $3^{1199}\equiv 134\mod 401$.

    \item Let $m\geq 1$ be square free.  If $(a,m)=1$ we know by Euler's theorem that $a^{\phi(m)}\equiv 1\mod m$ and
    hence that $a^{\phi(m)+1}\equiv a\mod m$.  Otherwise, let $(a,m)=d$ and write $a=dc$ with $(a,c)=1$.
    Then
    $$a^{\phi(m)+1}\equiv d^{\phi(m)+1}c^{\phi(m)+1}\equiv d^{\phi(m)+1}c\mod m.$$  Since $m$ is square free, $(d,m/d)=1$.
    It follows that $d^{\phi(m/d d)}\equiv d^{\phi(m/d)\phi(d)}\equiv 1\mod (m/d),$ which implies that
    $d^{\phi(m)+1}\equiv d\mod m$ upon multiplication of the above identity by $d$.  As such,
    $(cd)^{\phi(m)+1}\equiv cd\mod m$, as required.

    \item We have
    $$\phi(1210)=\phi(2\cdot 5\cdot 11^1)=\phi(2)\phi(5)\phi(11^2)=(2-1)(5-1)11(11-1)=4\cdot 10\cdot 11=440.$$

    \item Since $10=(20,190)$ and $10|70$ there are 10 solutions.  To find one, reduce the equation to an equation modulo $190/10=19$:
    $$2x\equiv 7\mod 19.$$
    The inverse of 2 modulo 19 is easy to find: $20=2\cdot 10$ so that 10 is the inverse.  Hence, $x\equiv 7\cdot 10\equiv 13\mod 19$
    is a solution.  All ten solutions are then given by
    $$\{13,32,51,70,89,108,127,146,165,184\}$$

    \item Let us first solve $x\equiv 1\mod 7,x\equiv 5\mod 11.$  We first use Euclid's algorithm to solve
    the linear diophantine equation $7x+11y=1$.  We find (just as in problems 5 and 6) that $x=-3,y=2$ is a solution.
    Then using the technique of problem 2 we see that $x=-21\cdot 5+22\cdot 1=-105+22=-83\equiv -6\mod 77$ is a simultaneous solution.
    Observe that $-6\equiv 0\mod 6$ so that every simultaneous solution to the three congruences is given
    by $x=-6+(6\cdot 7\cdot 11)k=-6+462k$ for some integer $k$.

    \item To find the last two digits of any number, it suffices to compute the residue of that number modulo 100.
    Observe that $3^2=10-1$ so that
    $$3^{1000}=(10-1)^{500}=10^{500}-\binom{500}{1}10^{499}+\cdots +(-1)^{499} \binom{500}{499}10+1\equiv 1\mod 100.$$
    Hence, the last two digits of $3^{1000}$ are $01$.  Similarly, observe that
    $2^5=30+2$ so that
    $$2^{1000}=(30+2)^{200}=30^{200}+\binom{200}{1}30^{199}\cdot 2+\cdots+\binom{200}{199}30\cdot 2^{199}+2^{200}\equiv 2^{200}\mod 100.$$
    Repeating this trick, we find
    $$2^{200}=(30+2)^{40}=30^{40}+\binom{40}{1}30^{39}\cdot 2+\cdots+\binom{40}{39}30\cdot 2^{39}+2^{40}\equiv 2^{40}\mod 100.$$
    Repeating one last time gives
    $$2^{40}=(30+2)^{8}=30^{8}+\binom{8}{1}30^{7}\cdot 2+\cdots+\binom{8}{7}30\cdot 2^{7}+2^8\equiv 240\cdot 2^7+2^{8}\mod 100.$$
    But $2^7\equiv 28\mod 100$ and $240\equiv 40\mod 100$ while $2^8\equiv 56\mod 100$ so that, at last,
    $$2^{1000}\equiv 28\cdot 40+56\equiv 76 \mod 100.$$  Hence the last two digits of $2^{1000}$ are 76.

    \item We use Hensel's lemma.  Observe that there are two solutions $0,1$ modulo $2$.  Moreover, the formal derivative
    of $x^4-x$ is $-1$ which is never 0.  This tells us that there are precisely $2$ solutions modulo any power of $2$, in particular
    1024.

    \item Set $f(x)=x^2+ax+b$.  We will proceed by induction.  We already know that a polynomial of degree 2 has
    at most 2 roots modulo a any prime, so assume that $f(x)\equiv 0\mod p^{k-1}$ has at most $2$ roots and $k>2$.
    let $u_1,\ldots u_n$ be distinct solutions modulo $p^k$ to $f(x)\equiv 0\mod p^k$.
    Further suppose that $n>2$.  Then since every solution modulo $p^k$ gives a solution modulo $p^{k-1}$ by the pigeonhole
    principal and induction we must have $u_i\equiv u_j\mod p^{k-1}$ for some $i\neq j$.  Let $v_i$ be the unique
    integer between $0$ and $p^{k-1}$ with $v_i\equiv u_i\mod p^{k-1}$  We may write
    $u_i\mod p^k=v_i+a_i p^{k-1}$ where $0\leq a_i< p$.  It then follows that we have
    \begin{align*}
    (v_i+a_ip^{k-1})^2+a(v_i+a_ip^{k-1})+b&\equiv 0\mod p^k,\\
    \intertext{so that}
    -(v_i^2+av_i+b)\equiv (2v_i+a)a_ip^{k-1}\mod p^k.
    \end{align*}
    If $(2v_i+a)\not\equiv 0\mod p$ then this equation uniquely determines $a_i$ modulo $p$ and it follows that
    $u_i\equiv u_j\mod p^k$, a contradiction.  On the other hand, if $(2v_i+a)\equiv 0\mod p$ then we see that
    $v_i$ is a solution of $f(x)\equiv 0\mod p^k$ so that, since $v_i=v_j$ we actually have
    $u_i\equiv u_j\mod p^k$, again a contradiction.


    \item This is Hensel's lemma again.  Observe that $4^2\equiv 5\mod 11$ and $7^2\equiv 5\mod 11$.
    The formal derivative of $x^2-5$ is $2x$ which is not zero modulo 11 for $x=\pm 4$.  It follows that both solutions can be lifted
    and we find that the two solutions modulo $11^2$ are
    $$\pm 4\pm 4\cdot 11=\pm 48.$$  We can lift again and find the two solutions modulo $11^3$:
    $$\pm 48\pm 4\cdot 2299=\pm 9244\equiv \pm 1258 \mod 11^3.$$


\end{enumerate}

\end{document}