%%%%%%%%%%%%%%%%%%%%% PACKAGE IMPORTS %%%%%%%%%%%%%%%%%%%%%
\documentclass[11pt]{article}
\usepackage{amsmath, amsfonts, amsthm, amssymb}
\usepackage{lmodern}
\usepackage{microtype}
\usepackage{fullpage}
\usepackage{romannum}

\usepackage[x11names, rgb]{xcolor}
\usepackage{graphicx}

\usepackage{etoolbox}
\usepackage{enumerate}
\usepackage{enumitem}
\usepackage{listings}
\usepackage{array}
\usepackage{probsoln}

%%%%%%%%%%%%%%%%%%%%%%%% QUESTION # %%%%%%%%%%%%%%%%%%%%%%%%
%% This part helps number your questions and creates a    %%
%% new page with each question for the aesthetics.        %%
%% It also creates parts that helps you answer questions  %%
%% To use do: \begin{question} ... \end{question}         %%
%% and: \begin{part} ... \end{part}                       %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\setlength{\parindent}{0pt}
\setlength{\parskip}{5pt plus 1pt}

\providetoggle{questionnumbers}
\settoggle{questionnumbers}{true}
\newcommand{\noquestionnumbers}{
    \settoggle{questionnumbers}{false}
}

\newcounter{questionCounter}
\newenvironment{question}[2][\arabic{questionCounter}]{%
    \addtocounter{questionCounter}{1}%
    \ifnum\value{questionCounter}=1 {} \else {\newpage}\fi%
    \setcounter{partCounter}{0}%
    \vspace{.25in} \hrule \vspace{0.5em}%
        \noindent{\bf \iftoggle{questionnumbers}{Question #1: }{}#2}%
    \vspace{0.8em} \hrule \vspace{.10in}%
}

\newcounter{partCounter}[questionCounter]
\renewenvironment{part}[1][\alph{partCounter}]{%
    \addtocounter{partCounter}{1}%
    \vspace{.10in}%
    \begin{indented}%
       {\bf (#1)} %
}{\end{indented}}

\def\indented#1{\list{}{}\item[]}
\let\indented=\endlist
\def\show#1{\ifdefempty{#1}{}{#1\\}}

%%%%%%%%%%%%%%%%%%%%%%%% SHORT CUTS %%%%%%%%%%%%%%%%%%%%%%%%
%% This is just to improve your quality of life. Instead  %%
%% of having to type long things, you can type short      %%
%% things. Ex: \IMP instead of \rightarrow to get ->      %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\IMP{\rightarrow}
\def\AND{\wedge}
\def\OR{\vee}
\def\BI{\leftrightarrow}
\def\DIFF{\setminus}
\def\SUB{\subseteq}

\newcolumntype{C}{>{\centering\arraybackslash}m{1.5cm}}
\renewcommand\qedsymbol{$\blacksquare$}
\newcommand{\pred}[1]{\textsf{#1}}

%%%%%%%%%%%%%%%%%%%%%%%%%%% TITLE %%%%%%%%%%%%%%%%%%%%%%%%%%
%% This is shows the homework number, your name, your     %%
%% collaborators, and the day. If you'd prefer to not so  %%
%% your name, just comment out the "\maketitle" below     %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\title{\vspace{-2cm}Homework 5\vspace{-0.3cm}}
\author{Insert Your Name}
\date{\vspace{-0.3cm}\today\vspace{-1cm}}

%%%%%%%%%%%%%%%%%%%%%%%% WORK BELOW %%%%%%%%%%%%%%%%%%%%%%%%
\begin{document}
\maketitle

%%%%%% QUESTION 1 %%%%%
\begin{question}{Collaborators}
% Please list your collaborators here; or state that you worked alone.

\end{question}

%%%%%% QUESTION 2 %%%%%
\begin{question}{Euclid's algorithm [10 points]}
\setcounter{section}{2}

Compute each of the following using Euclid's Algorithm. Show your intermediate results both as a sequence of $\gcd()$ calls. For your own understanding (and potentially for grading partial credit), we recommend writing out the tableau of intermediate values.

\begin{part}
$\gcd(225, 65)$ [4 points]

\begin{solution}
% Your solution here
\end{solution}

\end{part}


\begin{part}
$\gcd(354,123)$ [5 points] 

\begin{solution}
% Your solution here
\end{solution}

\end{part}

\begin{part}
$\gcd(3^{30}+1, 3)$ [1 point]

\begin{solution}
% Your solution here
\end{solution}

\end{part}

\end{question}

%%%%%% QUESTION 3 %%%%%
\begin{question}{Inverses [20 points]}

\begin{part}
Compute a multiplicative inverse of 15 $\pmod{103}$. Use the Extended Euclidean algorithm, showing the tableau and the sequence of substitutions. [5 points]


\begin{solution}
% Your solution here
\end{solution}

\end{part}

\begin{part}
Find \textbf{all} integer solutions to \[ 15x \equiv 11 \pmod{103} \] You must show \textbf{all} your work for this part. See lecture 15 for an example of the work needed. [8 points]

\begin{solution}
% Your solution here
\end{solution}

\end{part}

\begin{part}
Prove there are no integer solutions to \[ 10x \equiv 3 \pmod{15} \] Note: it's not enough to say that $10$ does not have a multiplicative inverse $\pmod{15}$. If that were enough, then you could say the same for $10x\equiv 10 \pmod{15}$, but $x=1$ is a solution to that equivalence. \\
You'll want to use proof by contradiction (suppose that there is an integer solution and go from there). [7 points]

\begin{solution}
% Your solution here
\end{solution}

\end{part}

\end{question}

%%%%%% QUESTION 4 %%%%%
\begin{question}{GCD proof [6 points]}
Show that if $a \equiv b \pmod{m}$ and $a \equiv c \pmod{n}$ then $b \equiv c \pmod{d}$ where $d = \gcd(m,n)$.

\begin{solution}
% Enter your solution here...
\end{solution}

\end{question}

%%%%%% QUESTION 5 %%%%%
\begin{question}{A Proof By Contradiction [7 points]}
Let $p$ be a prime number, show that $\sqrt{p}$ is irrational. You may want to adapt the proof that $\sqrt{2}$ is irrational (see the section of week 4, problem 3.(c)). You can use the following fact without proof: For integers $a,b$ and a prime number $p$: if $p \mid (ab)$ then $p \mid a$ or $p \mid b$.  

\begin{solution}
% Enter your solution here...

\end{solution}

\end{question}

%%%%%% QUESTION 6 %%%%%
\begin{question}{Unique in Division [7 points]}
Recall that the division theorem states that for any integers $a$ and $m$ with $m \geq 1$, there exist unique integers $q$ and $r$ such that $0 \leq r<m$ and $a = qm + r$. In this problem, you will show one part of this theorem --- that the pair $(q,r)$ is unique. More concretely, prove that the following holds: Suppose there exists integers $q_1,r_1,q_2,r_2$ satisfying $a=q_1 m + r_1$ and $a = q_2 m + r_2$ with $0 \leq r_1 < m$ and $0 \leq r_2 < m$, then $q_1=q_2$ and $r_1=r_2$.

\begin{solution}
% Enter your solution here...

\end{solution}

\end{question}

%%%%%% QUESTION 7 %%%%%
\begin{question}{Find The Bug [16 points]}

\subsection{I'm not FIBbing}
Your friend is doing a proof with the Fibonacci numbers. The function $f$ is defined by $f(0) = f(1) = 1$ and for all $n\geq 2$, and $f(n) = f(n-1) + f(n-2)$. 

They are trying to show that $f(4) = 5$ -- here is the proof they show you:
\begin{align*}
	f(4) &= 5\\
	f(3)+f(2) &= 5\\
	[f(2)+f(1)]+f(2) &= 5\\
	2f(2) + 1 &= 5\\
	2f(2) &= 4\\
	2(f(1) + f(0)) &= 4\\
	2(1+1) &= 4\\
	4 &= 4
\end{align*}

\begin{part}
Clearly explain why the proof is incorrect. Your explanation must deal with the proof directly, not just the statement they are showing (e.g. just providing a counter-example is not sufficient for this part). [3 points]

\begin{solution}
    % Enter your solution here...
\end{solution}

\end{part}

\begin{part}
If the statement is correct, then write a correct proof. If it is incorrect, provide a counter example. [5 points]

\begin{solution}
    % Enter your solution here...
\end{solution}

\end{part}

\subsection{Well...maybe I'm fibbing}
Another friend wishes to show $(x-3)(-x+4) = x^2-7x+12$ is true for all $x$. They show you their proof:
	
\begin{align*}
	&(x-3)(-x+4) = x^2-7x+12\\
	&[(x-3)(-x+4)]^2 = (x^2-7x+12)^2\\
	&(x^2-6x+9)(x^2-8x+16) = (x^4 - 7x^3 +12x^2) + (-7x^3 +49x^2 -84x) + (12x^2 -84x + 144)\\
	&(x^4 -8x^3 +16x^2) + (-6x^3 +48x^2 - 96x) + (9x^2 - 72x + 144) = x^4 - 14x^3 +73x^2 - 168x + 144 \\
	&x^4 - 14x^3 + 73x^2 - 168x + 144 =x^4 - 14x^3 +73x^2 - 168x + 144 \\
\end{align*}

\setcounter{partCounter}{0}
\begin{part}
Clearly explain why the proof is incorrect. Your explanation must deal with the proof directly, not just the statement they are showing (e.g. just providing a counter-example is not sufficient for this part). [3 points]

\begin{solution}
    % Enter your solution here...
\end{solution}

\end{part}

\begin{part}
If the statement is correct, then write a correct proof. If it is incorrect, provide a counter example. [5 points]

\begin{solution}
    % Enter your solution here...
\end{solution}

\end{part}

\end{question}

%%%%%% QUESTION 8 (EXTRA CREDIT) %%%%%
%%%%%% DELETE IF YOU ARE NOT DOING THIS PROBLEM) %%%%%
\begin{question}{Extra Credit: Exponentially increasing fun [0 points]}
Since $a \% n \equiv a \pmod{n}$, we know that we can reduce the base of an exponent in $\pmod{n}$ arithmetic. That is: $a^k \equiv (a \% n)^k \pmod{n}$. But the same is \textbf{not} true of the exponent! That is, we cannot say that $a^k \equiv a^{k \% n} \pmod{n}$. Consider, for instance, that $2^{10} \,\%\, 3 = 1$ but $2^{10 \% 3} \,\%\,3= 2^1 \,\%\,3 = 2$. The correct way to simplify exponents is quite a bit more subtle. In this problem you'll prove it in steps.

\begin{part}
Let $R = \{ t \in \mathbb{Z} : 1 \leq t \leq n-1 \wedge \gcd(t,n) = 1\}$. Define the set $aR = \{ ax \% n : x \in R\}$. Prove that $aR=R$ for every integer $a > 0$ with $\gcd(a,n) = 1$. 

\begin{solution}
    % Enter your solution here...
\end{solution}

\end{part}

\begin{part}
Consider the product of all elements in $R$ (taken $\% n$) and consider the product of all the elements in $aR$ (again, taken $\%n$). By comparing these two expressions, conclude that for all $a \in R$ we have $a^{\varphi(n)} \equiv 1 \pmod{n}$ where $\varphi(n) = |R|$. 

\begin{solution}
    % Enter your solution here...
\end{solution}

\end{part}

\begin{part}
Use the previous part to show that for any $b\geq 0$ and $a \in R$ we have $a^b \equiv a^{b \% \varphi(n)} \pmod{n}$.

\begin{solution}
    % Enter your solution here...
\end{solution}

\end{part}

\begin{part}
Now suppose that $y = x^e \pmod{n}$ for some $x$ with $\gcd(x,n) = 1$ and $e$ some integer $\geq 0$ such that $\gcd(e, \varphi(n))=1$. Let $d=e^{-1} \pmod{\varphi(n)}$. Prove that $y^d \equiv x \pmod{n}$. 

\begin{solution}
    % Enter your solution here...
\end{solution}

\end{part}

\begin{part}
Prove the following two facts about $\varphi$: First, if $p$ is prime then $\varphi(p) = p-1$. Second, for any positive integers $a$ and $b$ with $\gcd(a,b) = 1$, we have $\varphi(ab) = \varphi(a)\varphi(b)$. 

\begin{solution}
    % Enter your solution here...
\end{solution}

\end{part}

\bigskip
These facts together are the basis for the most-widely used ``public
key encryption system.'' One chooses $n = pq$ for large primes $p$ and
$q$, and a value of $e$. The numbers $n$ and $e$ are made public to
anyone who wants to send a message securely. To send a message $x$,
the sender computes $y = x^e \,\%\, n$ and sends $y$ (the ``encrypted
text''). To decrypt, one computes $y^d \,\%\, n$ (note that the recipient
must be the one who chose $p,q$ so they can calculate $d$). The
security of the system relies on it being hard to compute $d$ from
just $e$ and $m$.

\end{question}


%%%%%% FEEDBACK %%%%%
\begin{question}{Feedback}
\begin{part}{How many hours did you spend working on this assignment?} %% (a) %%
\end{part}

\begin{part}{Which problem did you spend the most time on?} %% (b) %%
\end{part}

\begin{part}{Which problem did you find to be the most confusing?} %% (c) %%
\end{part}

\begin{part}{Any other feedback for us?} %% (d) %%
\end{part}

\end{question}

\end{document}
