2018-11-18-090529.tex

\documentclass[12pt]{amsart}
\usepackage{amsmath,amsthm,amsfonts,amssymb,latexsym,verbatim,bbm}
\usepackage{amscd}
\usepackage[dvips]{graphicx}
\usepackage{graphicx}
\graphicspath{ {./images/} }
\input xy
\xyoption{all}
\usepackage{hyperref,multirow}
%\usepackage[notref,notcite]{showkeys}
\usepackage[shortlabels]{enumitem}
\usepackage{tikz, ifthen}
\usepackage[nomessages]{fp}
\usepackage{mathtools}
\usetikzlibrary{calc}
\usetikzlibrary{chains}
\usepackage{booktabs,caption}


%\usepackage[all]{xy}
%\CompileMatrices
%\usepackage{coordsys}

\newtheorem{thm}{Theorem}
\newtheorem{conj}{Conjecture}
\newtheorem{prop}{Proposition}
\newtheorem{lemma}[prop]{Lemma}
\newtheorem{claim}[prop]{Claim}
\newtheorem{alg}[prop]{Algorithm}
\newtheorem{cor}[prop]{Corollary}
\newtheorem{example}[prop]{Example}

\newtheorem*{thm*}{Theorem}
\newtheorem*{alg*}{Algorithm}
\newtheorem*{lemma*}{Lemma}

\theoremstyle{definition}
\newtheorem{question}{Question}
\newtheorem{bonus}{Bonus Question}

\theoremstyle{remark}
\newtheorem{rmk}[prop]{Remark}
\newtheorem*{rmk*}{Remark}
\newtheorem{notation}[prop]{Notation}
\newtheorem*{notation*}{Notation}

\theoremstyle{definition}
\newtheorem{defn}[prop]{Definition}

\newcommand{\GL}{\mathrm{GL}}
\newcommand{\SL}{\mathrm{SL}}
\newcommand{\dom}{\operatorname{dom}}
\newcommand{\ord}{\operatorname{ord}}

\newcommand{\mybf}{\mathbb}
\newcommand{\bH}{\mybf{H}}
\newcommand{\bP}{\mybf{P}}
\newcommand{\bR}{\mybf{R}}
\newcommand{\bRP}{\mybf{RP}}
\newcommand{\bCP}{\mybf{CP}}
\newcommand{\bC}{\mybf{C}}
\newcommand{\bN}{\mybf{N}}
\newcommand{\bZ}{\mybf{Z}}
\newcommand{\bQ}{\mybf{Q}}
\newcommand{\bF}{\mybf{F}}
\newcommand{\bA}{\mybf{A}}

\newcommand{\Q}{\mybf{Q}}
\newcommand{\Z}{\mybf{Z}}

\newcommand{\F}{\mathcal{F}}
\newcommand{\cA}{\mathcal{A}}
\newcommand{\cP}{\mathcal{P}}
\newcommand{\cB}{\mathcal{B}}
\newcommand{\cR}{\mathcal{R}}
\newcommand{\cS}{\mathcal{S}}
\newcommand{\cI}{\mathcal{I}}
\newcommand{\cL}{\mathcal{L}}
\newcommand{\cM}{\mathcal{M}}
\newcommand{\cF}{\mathcal{F}}
\newcommand{\cO}{\mathcal{O}}
\newcommand{\cU}{\mathcal{U}}
\newcommand{\cG}{\mathcal{G}}
\newcommand{\cK}{\mathcal{K}}
\newcommand{\cC}{\mathcal{C}}
\newcommand{\cH}{\mathcal{H}}
\newcommand{\cT}{\mathcal{T}}
\newcommand{\cV}{\mathcal{V}}
\newcommand{\cX}{\mathcal{X}}
\newcommand{\al}{\alpha}
\newcommand{\ep}{\epsilon}
\newcommand{\p}{\partial}

\newcommand{\ra}{\rightarrow}

\providecommand{\abs}[1]{\left\lvert#1\right\rvert}
\providecommand{\norm}[1]{\left\lVert#1\right\rVert}

\newcommand{\ON}[1]{\operatorname{#1}}
\addtolength{\hoffset}{-.25in} \addtolength{\textwidth}{.5in}

\usepackage{ifxetex}
\ifxetex
  \usepackage{fontspec}
\else
  \usepackage[T1]{fontenc}
  \usepackage[utf8]{inputenc}
  \usepackage{lmodern}
\fi

\usepackage{bbding}
\usepackage{pifont}
\usepackage{wasysym}
\usepackage{amssymb}

\title{Number Theory Homework 10}
 \author{Stephanie Carroll}

% Enable SageTeX to run SageMath code right inside this LaTeX file.
% http://mirrors.ctan.org/macros/latex/contrib/sagetex/sagetexpackage.pdf
% \usepackage{sagetex}

\begin{document}
\maketitle

\begin{question}
\begin{enumerate}[(a)]
\item 

$p=3 \Rightarrow A=1, B=2$

$p=5 \Rightarrow A=5, B=5$

$p=7 \Rightarrow A=7, B=14$

$p=11 \Rightarrow A=22, B=33$

$p=13 \Rightarrow A=39, B=39$

$p=17 \Rightarrow A=68, B=68$

$p=19 \Rightarrow A=76, B=95$

\item
Since QR's and NR's make up all of the numbers in each mod, we can say that $A+B = 1+2+\cdots +(p-1)$. We can also write this as an equation $A+B= \frac{p(p-1)}{2}$

$p=3, A+B = 2+1 = 3$

$p=5, A+B = 4+3+2+1 = 10$

$p=7, A+B = 6+5+4+3+2+1 = 21$

We know that $A+B= \frac{p(p-1)}{2}$ is always a multiple of p because $\frac{(p-1)}{2}$ is an integer multiplied by p.

\item
$p=3, A(mod 3) = 1 (mod 3), B=2(mod3)$

$p=5, A=0 (mod5), B= 0 (mod 5)$

$p=7, A=0(mod7), B= 0(mod 7)$

$p=11, A= 0 (mod 11), B= 0(mod 11)$

For all primes larger than 3, both A and B are congruent to $0 (mod p)$. Since the number of QR's and NR's are the same we also know that the numbers added to get A and the numbers added to get B are also the same. This means that to find A we would have the equation $\frac{1}{6} \frac{p-1}{{2}} \frac{p+1}{2}p$ and this is a multiple of p so our A and B must be both divisible by p.

\item 

$p=23 \Rightarrow A=92, B=161$

$p=29 \Rightarrow A=203, B=203

When the prime is of the form $1 (mod 4)$ then $A=B$.

\end{enumerate}
\end{question}

\begin{question}
\begin{enumerate}[(a)]
\item $5987$ is a prime of the form $3 (mod 4)$ which means that it does not have a solution

\item We can see that $6780 \equiv -1 (mod 6781)$, and 6781 is a $1 (mod 4)$ prime so there is a solution.

\item If we use the quadratic formula to find our solutions we get 

$x \equiv \frac{1}{2}(64 \pm \sqrt{336})$. We know that $\frac{1}{2}$ exists because we are working mod p. Now if $sqrt{336}$ exists then a solution will exist. Notice that $336 \equiv -1 (mod 337)$ and 337 is a $1 (mod 4)$ prime so there are solutions.

\item Again we will use the quadratic formula to get $x \equiv \frac{1}{2}(64 \pm \sqrt{324})$. WE just have to check that $\sqrt{324}$ is a real number, and it is $18^2$ so this equation has solutions.
\end{enumerate}
\end{question}


\begin{question}
$p=17 \Rightarrow (2*17)^2+1 =1157=13*89$

$p=13 \Rightarrow (2*17*13)^2+1=195365=5*41*953$

$p=5 \Rightarrow (2*17*13*15)^2+1=4884101$
\end{question}

\begin{question}
If we reduce the list mod 12 then we have 

QR=$-1,1,-1,1,-1,1, \ldots$

NR$=5,7,5,7,5,7 \ldots$
\end{question}


\begin{question}
\begin{enumerate}[(a)]
\item Case 1:

$p \equiv 1 (mod 8)$ 

We can write $p=8k+1$. To find our list of numbers $2,4,6, \ldots , p-1$. Set $p-1=8k+1-1 \Rightarrow 8k$, so $\frac{p-1}{2}= \frac{8k}{2} \Rightarrow 4k$. This tells us that there are $4k$ numbers in our list $2,4,6,\ldots , 4k+2,4k+4, \ldots , 8k$. If we look halfway, there are $2k$ numbers in the list $2,4,6, \ldots 4k$ and $2k$ after. Now we can use Euler's formula to say $2^{\frac{p-1}{2}} \equiv (-1)^{\frac{p-1}{2}} (mod p)$. Simplify to get $2^{\frac{p-1}{2}} \equiv 1 (mod p)$. 

\item Case 2:

$p \equiv 5 (mod 8)$

We can write $p=8k+5$. To find our list of numbers $2,4,6, \ldots , p-1$. Set $p-1=8k+5-1 \Rightarrow 8k+4$, so $\frac{p-1}{2}= \frac{8k+4}{2} \Rightarrow 4k+2$. This tells us that there are $4k+2$ numbers in our list $2,4,6,\ldots , 4k+2,4k+4,4k+6, \ldots , 8k+4$. If we look halfway, there are $2k+1$ numbers in the list $2,4,6, \ldots 4k+2$ and $2k+1$ after. Now we can use Euler's formula to say $2^{\frac{p-1}{2}} \equiv (-1)^{2k+1} (mod p)$. Simplify to get $2^{\frac{p-1}{2}} \equiv -1 (mod p)$. 
\end{enumerate}

\end{question}


\end{document}