\documentclass{article}[11 pts] 

\begin{document}

\centerline{\bf THEORY OF NUMBERS, Math 115 A}
\centerline{\bf Homework 3 Due Wednesday October 16}
\vskip 5pt

\begin{enumerate}

\item Use the Euclidean and extended Euclidean algorithms to find
the gcd of the following pairs of numbers and to represent them 
as a linear combination of the input data:

a) $(45,75)$, b) $(666,1414)$, c) $(102,222)$ d) $(20785,44350)$.

\item Let $m,n$ be positive integers and let $a$ be an integer
greater than 1. Show that $(a^m-1,a^n-1)=a^{(m,n)}-1$.

\item Show that every positive integer can be written as the product
of possibly a square and a square-free integer. Recall a {\em square
free} integer is an integer that is not divisible by any perfect square
other than 1.

\item Let $N(a+b\sqrt{-5})=a^2+5b^2$. Show that if $m=a+b\sqrt{-5}$ and 
$n=c+d\sqrt{-5}$, where $a,b,c,d$ are integer, then $N(nm)=N(n)N(m)$. 

\item Show that the numbers $1+\sqrt{-5}$ and $1-\sqrt{-5}$ are prime
numbers inside the set of special numbers $a+b\sqrt{-5}$. Hint: use
the previous exercise.

\item Find the least common multiple of each of the following pairs of
integers:

a)7,11 b) 101,303 c) 1331, 5005 d) 5040, 7700.

\item Show that $\sqrt{2}+\sqrt{3}$ is irrational.

\item Prove that there are infinitely many primes of the form $6k+5$, where
$k$ is a positive integer.


\end{enumerate}

\end{document}





