%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%  Math 458 hw7
\documentclass[12pt]{article}

\usepackage{amsmath}
\usepackage{amsfonts} % to get \mathbb letters
\usepackage{hyperref}
\usepackage[height=10in]{geometry}

\DeclareMathOperator{\norm}{norm}

\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\GG}{\mathbb{G}} % for Gaussian integers
%create (mod n) macro
\newcommand{\mm}[1]{%
\ensuremath{(\text{mod } #1)}}

\title{Number Theory, hw7}
\date{ \today }
\author{Ethan\ D.\ Bolker}

\begin{document}
\maketitle

Here are some exercises that explore number theory in
the \emph{Gaussian integers}
%
\begin{equation*}
\GG = \{\ a+bi \  | \ a, b \in \ZZ \ \}.
\end{equation*}
%
They're interesting in their own right and will help you review
some number theory in $\ZZ$.

\begin{enumerate}
\item
Factor 29 and 101 in $\GG$.

Here's a hint you shouldn't need: each of those is a prime congruent
to $1 \mm{4}$ in $\ZZ$, so it's a sum of two squares.

\item Let $v$ and $w$ be the answers to the previous question that lie
  in the first quadrant (that is, $a$ and $b$ are positive). We know
  $v$ and $w$ are prime in $\GG$, so they are relatively prime. Use
  the Euclidean algorithm in $\GG$ to find Gaussian integers $x$ and
  $y$ such   that
%
\begin{equation*}
vx + wy = 1.
\end{equation*}

\item (Optional - I don't know the answer since I haven't looked at
  the question). You can use the Euclidean algorithm in $\ZZ$ to solve
  the Diophanine equation
\begin{equation*}
29x + 101y = 1.
\end{equation*}
%
Is there any relation between this solution and the one you found in
the previous problem?

\item You can do modular arithmetic in $\GG$ just the way you do in
  $\ZZ$: define
\begin{equation*}
v \equiv w \mm{z} \text{ when } z \text{ divides } v-w.
\end{equation*}

Then define the ring $\GG_z$ just the way we defined $\ZZ_n$.

Here's the first question about this new modular arithmetic. Let
$z = n + 0i \in \ZZ$. Show that every Gaussian integer is congruent
$\mm{z}$ to some $c+di$ with $0 \le c, d < n$. 

Then $\GG_n$ has $n^2$ elements.

Hint: you can do this if you think of division as repeated subtraction
whenyou also allow yourself to subtract $ni$.

\item (Optional. I can prove this, cleverly but not easily).

Show that $\GG_z$ has $\norm(z)$ elements.

(The previous problem does this when $z$ has zero imaginary part.

\item Figure out (and prove) Fermat's Little Theorem for modular
  arithmetic in the Gaussian integers.

If you can't see this right away in reasonably abstract terms you can
at least compute some examples. What happens with the Gaussian primes
$3$ and $2+i$?

\end{enumerate}
\end{document}
