\documentclass[12pt]{amsart}
\usepackage{amsfonts}
\setlength{\topmargin}{0in}
\setlength{\textheight}{10in}
\setlength{\oddsidemargin}{0in}
\setlength{\evensidemargin}{0in}
\setlength{\textwidth}{6.5in}
\parskip0.4em
\thispagestyle{empty}
\def\rr{\mathbb{R}}
\def\Z{\mathbb{Z}}
\def\Q{\mathbb{Q}}
\renewcommand{\phi}{\varphi}

\begin{document}
\begin{center}
{\bf Math 113 Homework 1, due 2/5/2019}
\end{center}
\medskip

{\bf 1.}
Write down a solution to the ``important exercise'' at the end of page 6 of Paulin's notes.

\

{\bf 2.} 
Imagine a race of aliens that understands integers (positive and negative) and the logic of sets but does not know about real or rational numbers. We explain to them that rational numbers are pairs of numbers written $(a : b)$ with $a\in \Z$ (any integer) and $b\in \Z^*$ (a nonzero integer). We can add these formally as fractions: to add two pairs we use the usual formula for addition of fractions: $$(a : b) + (c : d) = (ad + bc : bd).$$ Now to avoid redundancies in our notation we could require all fractions to be in reduced form. The problem is that even if $(a : b)$ and $(c : d)$ are in reduced terms, their sum might not be. For instance, our formula gives $(1:2) + (1:2) = (2:2).$ So instead we allow all pairs $(a: b)$ (so long as $b\neq 0$) and identify certain pairs by imposing an equivalence relation, $(a:b) \sim (a':b')$ if and only if $a\cdot b' = b\cdot a'$. 

(a) Pretending you're an alien, check using our formal rules (and without using rational numbers) that if we first compute $(a:b) + (c:d)$ for two different pairs of integers (with $b, d\neq 0$) and then replace $(a:b)$ by any equivalent pair $(a': b')$ (such that $ab' = a'b$) then $(a':b') + (c : d)$ gives an answer equivalent to $(a:b) + (c:d).$

(b) Since addition is commutative, this immediately implies that if $(c : d)\sim (c': d')$ then $(a:b) + (c:d) \sim (a:b)+ (c':d').$ By combining these two results, deduce that if $(a:b)\sim (a':b')$ and $(c:d)\sim (c':d')$ then $$(a:b) + (c:d) \sim (a':b') + (c':d').$$ In other words, replacing each of two fractions by an equivalent fraction replaces their sum by an equivalent sum. The technical term for this is that after imposing this equivalence relation, ``addition is well-defined''.

(c: extra credit) Check that $(a:b) \sim (a':b')$ via our equivalence formula if and only if we have equality of actual rational numbers, $a/b=a'/b'$ after reducing both sides. 

\noindent {\bf Hint}: every integer can be uniquely factorized as $\pm p_1\cdot p_2 \cdot \cdots \cdot p_n$ for $p_1, p_2,\ldots, p_n$ primes (possibly with repetitions): for example, $12 = 2\cdot 2\cdot 3.$ A fraction is in reduced terms if and only if no prime appears both in the numerator and the denominator, and the denominator is positive. % If $a/b$ is a fraction in reduced terms then any other fraction $c/d$ has $c = \big(Na: Nb \big),$ where the same (positive or negative) integer $N$ appears in both the numerator and the denominator. Now look at the prime factorization of $N$. 

\

{\bf 3.} Now you want to explain arithmetic modulo $4$ to the same aliens. You could say that every number has residue either $0, 1, 2$ or $3$ modulo $4$, but this makes addition modulo $4$ behave in a complicated way. Instead, you tell the alien that numbers modulo $4$ can be represented by any integer, except for two integers $a, b\in \Z$ we declare $a\sim b$ (i.e. they are equivalent) if $4\mid a-b$.

(a) Show that if $a, b$ are any integers, and $a'$ is any integer equivalent to $a$ (i.e.\ $4\mid a'-a$) and $b'$ is any integer equivalent to $b$ (i.e.\ $4\mid b'-b$) is an integer equivalent to $b$ then $a+ b \sim a'+ b'.$

(b) Show that $a\sim a'$ if and only if they have the same remainder when divided by $4$. (Note: there are four possible remainders, $0, 1,2,$ or $3$. To find the remainder of a number $a$ you find the largest multiple of $4$ which is $\le a$ and subtract it. For example if $a = -1$ the largest multiple of $4$ which is $\le a$ would be $-4$ and $a\mod 4$ would then be $-1 - (-4) = 3.$)
\end{document}