\documentstyle[12pt]{report}
\newcommand{\sk}{\vskip 0.2in}
\newcommand{\GL}{{\bf GL}}
\newcommand{\F}{{\bf F}}
\newcommand{\Z}{{\bf Z}}
\newcommand{\fp}{{\mbox{FP}}}
\begin{document}
\begin{center}
{\Huge 189-346/377B: Number Theory} \\ \sk
{\Huge Assignment 2} \\ \sk
{\Large Due: Monday, January 31 }
\end{center}
\sk
\sk
\noindent
\noindent
1. Compute
the greatest common divisor of
$4655$ and $12075$ and
express the result as a linear combination with coefficients in
$\Z$ of these two integers.
\sk\noindent
2. Compute the multiplicative inverse of $2$ in $\Z/65537\Z$.
\sk\noindent
3. If $a$ and $b$ are two relatively prime integers,
and $p$ is an odd prime, show that
$a+b$ divides $a^p+b^p$, and
that $\gcd(a+b, (a^p+b^p)/(a+b))$ is equal either to
$1$ or $p$.
Suppose that $(a,b,c)$ is a solution to Fermat's equation
$a^p+b^p=c^p$, and that $p$ does not divide $c$.
What can you conclude about $a+b$?
\sk\noindent
4. The Euclidean algorithm
for computing the $\gcd$ of $a$ and $b$, with $a>b$,
relies on the fact that
$\gcd(a,b)=\gcd(a_n,b_n)$,
where the sequences $a_n$ and $b_n$ are defined recursively by
the conditions
$(a_0,b_0)= (a,b)$ and
$$
b_{n+1} = \mbox{ remainder in the division of } a_n \mbox{ by } b_n;
\quad a_{n+1} = b_n.$$
Show that $b_{n+2} \le b_n/2$, and conclude that the
Euclidean algorithm terminates before the $N$-th step, where
$N=2\log(|b|)/\log(2)$. (Recall the convention that
$\log $ is the natural
logarithm--to the base $e$--although this does not matter here.)
\sk\noindent
5. Let $f\in\Z[x]$ be a polynomial with coefficients in $\Z$.
Fix an integer $N$ and denote by
$[a]$ the remainder after deivision of $a$ by $N$.
Show that the sequence $[f(0)], [f(1)], [f(2)],\ldots,$ is
periodic and that its smallest
period divides $N$.
What about the exponential sequence $[a^1], [a^2], [a^3],\ldots$?
\sk\noindent
6. Show that if $N=2^p-1$, with $p$ a prime,
then $N$ divides $2^N-2$.
\sk\noindent
7. Let $N=2^{2^5}+1$. Find an integer $a$ such that
$a^2\equiv 1\pmod{N}$ but such that
$a\ne \pm 1\pmod{N}$.
\sk\noindent
8. Simplify the expression $\phi(1)+\phi(2) + \cdots + \phi(n)$,
where $\phi$ is the Euler $\phi$-function.
Deduce a simple formula (in terms of $n$)
for the number of fractions $a/b$ in lowest terms
satisfying $1\le a