\documentclass[12pt]{amsart}

\begin{document}

\def\Z{{\mathbb Z}}
\def\Q{{\mathbb Q}}
\def\R{{\mathbb R}}
\def\lra{\longrightarrow}

\centerline{\bf Mathematics 361:  Number Theory}
\centerline{\bf Assignment C}

\bigskip

{\bf Reading:  }Ireland and Rosen, Chapter 3 (including the exercises)
and into Chapter~4

\bigskip

{\bf Problems:}

\bigskip

{\em The pigeonhole principle and congruences.}

1.  Let $m$ be a positive integer and $a_1$, \dots, $a_m$ be any integers, 
possibly repeating.  Show that for some nonempty subset $S$ of the indices 
$\{1, \dots, m\}$, $\sum_{i\in S}a_i\equiv0\pmod m$.  
(Hint:  pigeonhole the partial sums.)

\bigskip

{\em The fifth Fermat number is composite.}

2.  Fermat defined the numbers $F_n=2^{2^n}+1$ for $n\ge0$.  Thus 
\begin{align*}
&F_0=3, \quad F_1=5, \quad F_2=17, \quad F_3=257, \\
&F_4=65537,\quad F_5=4294967297,\quad \text{etc.}  
\end{align*}
He conjectured that all the $F_n$ are prime, as indeed $F_0$ through $F_4$ are.
Euler showed that $F_5$ is composite, using techniques that were actually 
available to Fermat and applied by him in similar situations.  Andr\'e Weil, 
in his book {\bf Number Theory:  An Approach Through History}, conjectures 
that Fermat tried these techniques on $F_5$, made an arithmetic error (as he 
apparently often did), and never rechecked them.  Following Euler, investigate
whether $F_5$ is composite.  To search for candidate prime factors $p$
of~$F_5$, reason as follows: $p\mid2^{32}+1$ is equivalent to
$2^{32}\equiv-1\pmod p$, showing that $2$  has order 64 in $(\Z/p\Z)^\times$.
It follows that $64\mid\phi(p)=p-1$, so $p$ must take the form $p=64k+1$.
Thus candidates for $p$ are
$$
193,\quad257,\quad449,\quad577,\quad641,\quad \text{etc.} 
$$
Testing whether each of these primes $p$ divides $F_5$ is easy.  As above,
we need to check whether $2^{32}\equiv-1\pmod p$, so simply compute $2$, $2^2$,
$2^4$, $2^8$, etc.\ modulo $p$ up to $2^{32}$.  Use this method to show that 
$193$ does not divide $F_5$.  Neither do 257, 449 or 577, but don't bother 
showing this.  Use this method to show that $641$ {\em does\/} divide $F_5$.

Note that this shows $F_5$ to be composite without ever computing it.

\bigskip

{\em Using algebra rather than arithmetic.}

3. The Fibonacci numbers are $u_0=0$, $u_1=1$, $u_n=u_{n-1}+u_{n-2}$ for
$n\ge2$ (this is slightly different indexing from earlier).  Read through
the following method to compute a closed form expression for $u_n$ via
linear algebra:

Let $A=\left[\begin{matrix}1&1\\1&0\end{matrix}\right]$.
Induction quickly shows that 
$A^n=\left[\begin{matrix}u_{n+1}&u_n\\u_n&u_{n-1}\end{matrix}\right]$
for $n\ge1$.
So to find $u_n$ in closed form it suffices to compute either off-diagonal 
entry of $A^n$.

To diagonalize $A$ with no mess, one easily computes that its characteristic 
polynomial is $\chi_A(\lambda)=\lambda^2-\text{tr}(A)\lambda+\det(A)
=\lambda^2-\lambda-1$.  We let $\tau$ and $\tilde\tau$ denote the roots of
$\chi_A$ but {\em we don't compute them yet\/}---the numerical values
only muddy the calculation.  The coefficients of the  characteristic
polynomial show that 
\begin{equation}
\tau+\tilde\tau=1, \qquad\tau\tilde\tau=-1.
\end{equation}
Note that the second relation in \thetag1 tells us that one root---say, 
$\tau$---is positive and the other negative.  Thus the roots are
distinct and  each corresponding eigenspace of $A$ has dimension~$1$.  
In particular, the matrix
$$
A-\tau I=\left[\begin{matrix}1-\tau&\phantom-1\\1&-\tau\end{matrix}\right]
$$
must have nullity~$1$ and therefore rank~$1$, meaning its two rows are
linearly  dependent so that any vector orthogonal to the second row
spans the matrix's nullspace.  For example,
$\left[\begin{matrix}\tau\\1\end{matrix}\right]$
works.  Continuing this argument shows that
\begin{align*}
&A^n=PJ^nP^{-1}\qquad\text{where }
J=\left[\begin{matrix}\tau&0\\0&\tilde\tau\end{matrix}\right]\text{ and }
P=\left[\begin{matrix}\tau&\tilde\tau\\1&1\phantom{'}\end{matrix}\right], \\
&\text{so }
P^{-1}=\frac1{\tilde\tau-\tau}\left[\begin{array}{rr}
1&-\tilde\tau\\-1&\phantom{-}\tau\phantom{'}\end{array}\right].
\end{align*}
To obtain a closed form expression for $u_n$, compute
that $(\tilde\tau-\tau)A^n$ is
$$
\left[\begin{matrix}\tau&\tilde\tau\\1&1\phantom{'}\end{matrix}\right]
\left[\begin{matrix}\tau^n&0\\0&\tilde\tau^n\end{matrix}\right]
\left[\begin{array}{rr}
1&-\tilde\tau\\-1&\phantom{-}\tau\phantom{'}\end{array}\right]
=\left[\begin{matrix}*&*\\1&1\end{matrix}\right]
\left[\begin{matrix}\tau^n&*\\-\tilde\tau^n&*\end{matrix}\right]=
\left[\begin{matrix}*&*\\\tau^n-\tilde\tau^n&*\end{matrix}\right],
$$
and so
\begin{equation}
u_n=\frac{\tau^n-\tilde\tau^n}{\tau-\tilde\tau}.
\end{equation}
Finally, since $\tau,\tilde\tau=(1\pm\sqrt{5})/2$, we have
{\em Binet's formula}
$$
u_n=\frac{((1+\sqrt{5})/2)^n-((1-\sqrt{5})/2)^n}{\sqrt5}.
$$
Note how clean the calculation is when one ignores the numerical value of 
$\tau$ until the end.

(a) Use relations \thetag1 and the convention $\tau>0$ to show that 
$|\tilde\tau|<\tau$.  

(b) Now use \thetag2 to show that $\lim_{n\to\infty}(u_{n+1}/u_n)=\tau$.  
(None of (a) or (b) requires the numerical value of $\tau$.)

\bigskip

4. Ireland and Rosen exercises 3.24, 3.25, 3.26.  Note: 3.25 is
technical; roughly $\lambda$ is a square root of~$3$ and therefore a
fourth root of~$9$, and so the condition $\alpha=1\ (\lambda)$
suggests that $\alpha^3=1\ (\lambda^3)$, but the issue is to
finagle one more power of~$\lambda$ to get to $\alpha^3=1\ (\lambda^4)$;
and problem 3.24 can tell us that one of three elements must be a
multiple of~$\lambda$.

\bigskip

5. Work a selection from Ireland and Rosen exercises 3.1, 3.4, 3.8--3.10, 
3.12--3.13, 3.16, 3.17, 3.18, 3.23.

\bigskip

{\em Optional alternate problems.}

6. Use Hensel's Lemma to show that for distinct odd primes $p$
and~$q$, the $2$-adic equation
$$
px^2+qy^2=z^2,\quad x,y,z\in\Z_2
$$
has a nonzero solution if at least one of $p$ and~$q$ is $1$
modulo~$4$ but not if both are $3$ modulo~$4$.

\medskip

7. Let $a,b\in\Q$ be nonzero.  Show that the inhomogeneous condition
$$
aX^2+bY^2=1\quad\text{has a solution in~$\Q^2$}
$$
and the homogeneous condition
$$
aX^2+bY^2=Z^2\quad\text{has a nonzero solution in~$\Z^3$}
$$
are equivalent.

\end{document}
