\documentclass[11pt]{article} % 

\setlength{\oddsidemargin}{-0.15in}
\setlength{\topmargin}{-0.5in}
\setlength{\textwidth}{6.5in}
\setlength{\textheight}{9in}

\newcommand{\cP}{{\cal P}}
\newcommand{\N}{{\bf N}}
\newcommand{\Z}{{\bf Z}}
\newcommand{\R}{{\bf R}}
\newcommand{\Q}{{\bf Q}}
\def\mod{{\rm mod}\,}
\newcommand{\points}[1]{{\it (#1 Points)}}
\newcommand{\tpoints}[1]{{\bf #1 Total points.}}

\begin{document} 
\openup 1 \jot
{\bf Math 214 Foundations of Mathematics \quad  Homework 6 \hfill Your name}

\centerline{Solve the following problems.  Ten points each.}

\begin{enumerate}



 
\item (a) Let $n \in \N$ with $n > 1$.
Suppose $a \equiv r \ (\mod n)$ and $b \equiv s \ (\mod n)$. 
Show that 

\medskip\hskip 1in 
$a+b \equiv r+s \ (\mod n)$ and $ab \equiv rs \ (\mod n)$.

Recall that $\Z_n = \{[0], \dots, [n-1]\}$
such that $[r] = \{nx + r: r \in \Z\}$.
The above results show that if $[a] = [r]$ and $[b] = [s]$, then
$[a+b] = [r+s]$ and $[ab] = [rs]$. 
 
(b) Show that

(b.1) $3^{2016} \equiv 1 (\mod 10)$. \qquad (b.2) 
$3^{2016} + 5^{2016} \equiv 2 (\mod 28)$.

 
\item 
(a) Find $\gcd(51, 288)$ and $m, n \in \Z$ such that $\gcd(51,288) = 51n + 288m$
using the Euclidean Algorithm.

(b) Show that $n+1$ and $3n+2$ are coprime. 

\item 
(a)  Let $a,b,c$ be integers. Prove that if $3| (abc-1)$, then $3| (a-1)$,  $3| (b-1)$, 
or $3| (c-1)$. 

(b) Let $d={\rm gcd}(a,b)$. If $a=da'$ and $b=db'$, show that ${\rm gcd}(a',b')=1$. 

\item (a) Find a pair of integers $(x, y)$ such that 
$3x+2y = 1$, and show that $(x_n,y_n) = (x+2n,y-3n)$ also satisfies
$3x_n + 2y_n = 1$ for every $n \in \Z$.


(b) Let $a,b\in \Z$ such that $ab \ne 0$.  
Show that there are infinitely many pairs $x,y$ of integers such 
that ${\rm gcd}(a,b)=ax+by$. 


\item Use the Fundamental Theorem of Arithmetic to 
prove that $\sqrt[3]{3}$ and $\log_{10} 234$ are irrational numbers. 

[Hint: If $\sqrt[3]{3} = p/q$, then 
$3q^3 = p^3$. Then ....]


\item (Extra credits) For integers $a$ and $b$, let ${\rm lcm}(a,b)$ 
be the least positive multiplier of $a$ and $b$.

(a) Express ${\rm gcd}(a,b)$ and ${\rm lcm}(a,b)$ in terms of
prime factors of $a$ and $b$.

  
(b) Show that ${\rm lcm}(a,b)\cdot {\rm gcd}(a,b)=ab$. 

[Hint: Let $p_1, \dots, p_k$ be the list of all prime factors of $a$ and $b$.
Then $a = p_1^{r_1} \cdots p_k^{r_k}$ and $b = p_1^{s_1} \dots p_k^{s_k}$.
Express (with proofs) the gcd and lcm of $a$ and $b$ in terms of $p_1, \dots, p_k$.
Then ... ]


\end{enumerate}
   


  


\end{document}


