% 
% hw2.tex
%
%   This is LaTeX template to get you started
%   making problem-set solutions
%
 
\documentclass[11pt]{article}
\usepackage{amsthm,amsmath, amssymb}
\usepackage{color}
\setlength{\oddsidemargin}{0in}
\setlength{\evensidemargin}{0in}
\setlength{\textheight}{9.0in}
\setlength{\textwidth}{6.5in}
\setlength{\topmargin}{-0.5in}
\newcommand{\lcm}{\textrm{lcm}}




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\title{\bf Homework 7: due 2/26/2019\\[2ex]
       \rm\normalsize ECS 20 (Winter 2019)}
%\date{\today}
\author{Patrice Koehl\\koehl@cs.ucdavis.edu}

\begin{document}
\maketitle


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Exercise 1: 10 points} 
\begin{itemize}
\item [a)] Let $a$ be a natural number strictly greater than 1. Show that $\gcd(a,a-1) = 1$.
\item [b)] Use the result of part a) to solve the Diophantine equation $a + 3b = ab$ where $a$ and $b$ are two positive integers.
\end{itemize}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Exercise 2: 20 points (10 for a), 10 for b))} 

\begin{itemize}
\item [a)] Let $a$, $b$, and $c$ be three integers. Show that the equation $ax+by=c$ has at least one solution \textcolor{red}{in $\mathbb{Z}^2$} if and only if $\gcd(a,b) / c$.
\item [b)] A group of men and women spent \$100 in a store. Knowing that each man spent \$7, and each woman spent \$6, can you find how many men and how many women are in the group?
\end{itemize}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Exercise 3: 20 points (10 for a), 10 for b))} 

\begin{itemize}
\item [a)] Let $a$ and $b$ be two natural numbers. Show that if $\gcd(a,b)=1$ then $\gcd(a,b^2) = 1$.
\item [b)] Let $a$ and $b$ be two natural numbers. Show that if $\gcd(a,b)=1$ then $\gcd(a^2,b^2) = 1$.
\end{itemize}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Exercise 4: 10 points}

Let $n$ be a natural number such that the remainder of the division of 5218 by $n$ is 10, and the remainder of the division of 2543 by $n$ is 11. What is $n$?
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Exercise 5: 10 points}

Find all $(x,y) \in \mathbb{N}^2$ that satisfy the system of equations:
\begin{eqnarray*}
\begin{cases}
x^2-y^2 = 2340 \\
\gcd(x,y) = 6
\end{cases}
\end{eqnarray*}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Exercise 6: 10 points}

Let $n$ be a natural number. We define $A = n-2$ and $B = n^2 -6n + 13$. Show that $\gcd(A,B)=\gcd(A,5)$.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Exercise 7: 10 points}

Let $a$ and $b$ be two natural numbers. Solve the equations $a^2-b^2=13$.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section*{Extra Credit: 5 points}

Let $a$ and $b$ be two natural numbers. Solve $\gcd(a,b)+\lcm(a,b)=b+9$.


\end{document}