integers.tex

\documentclass{article}
\begin{document}

\textbf{Divisibility facts}
\begin{enumerate}
\item Prove that for any  integers $ a, b, ab = 0 \Rightarrow a = 0 \lor b = 0 $

\begin{enumerate}
\item Suppose $ ab = 0 $ for some integers a, b
\item Suppose $ a \neq 0. $ Then, there exists an integer $ a^{-1} $ such that $aa^{-1} = 1 $
\item Then, $a^{-1} a b = b = 0 $
\item Similarly, $ b \neq 0 \Rightarrow a = 0 $. Proved.
\end{enumerate}

\item Prove that if x,y are positive, then $ x \mid y \Rightarrow x \leq y $
\begin{enumerate}
\item By definition, there exists integer m such that mx = y
\item Since y is positive, m and x are either both negative or both positive.
\item Since x is positive, m must be positive
\item $ m \geq 1 $
\item Multiplying by x on both sides, $ mx \geq x $
\item Since mx = y, $ mx = y \geq x $
\end{enumerate}

\item Prove that if x, y are negative, then $ x \mid y \Rightarrow y \leq x $

\item If n divides 1, $ n = \pm 1 $
\begin{enumerate}
\item Since n divides 1, xn = 1 for some integer x
\item Either both x and n are positive, or both are negative.
\item Suppose both are positive. Then, $ 0 \leq n $ and by previous result, $ n \leq 1 $
\item Thus, n must be 1
\item Suppose both x and n are negative. Then, $ (-x)(-n) = 1 $. By preceding
deduction, -n = 1
\item This means n = -1
\item Thus, $ n = \pm 1 $
\end{enumerate}

\item For any nonzero integer x, if d divides x, then $ -|x| \leq d \leq |x| $
\begin{enumerate}
\item Suppose x is positive.
\item If d is positive, then $ -|x| < 0 \leq d \leq |x| $
\\ Hence, $ -|x| \leq d \leq |x| $
\item If d is negative, then -d is positive and also divides x, implying that $ -|x| \leq -d \leq |x| $
\\ Hence, $ -|x| \leq d \leq |x| $
\item Suppose x is negative.
\item If d is negative, then $ x = -|x| \leq d < 0 < |x| $
\item Hence, $ -|x| leq d \leq |x| $
\item If d is positive, then -d is negative and also divides x, implying that $
-|x| \leq -d \leq |x| $
\\ Hence, $ -|x| \leq d \leq |x| $
\end{enumerate}

\item For any nonzero integer x, integer d divides x iff -d divides x
\begin{enumerate}
\item Suppose d divides x. i.e. x = md, for some integer m
\item Then, x = (-d)*(-m). Thus, -d divides x
\item The same logic can be applied in the converse direction.
\end{enumerate}

\item For any nonzero integer x, its set of divisors is finite.
\item For the integer 0, the set of divisors is countably infinite.

\item Every non zero integer x has at least 1 positive divisor: 1

\item When we add a set of $k$ integers are added, the sum is odd $\iff$ there
is an odd number of odd integers in the set.
\begin{enumerate}
\item To prove odd number of odd integers $\Rightarrow$ odd sum, note that
adding any number of even integers gives an even sum, and adding odd number of odd
integers gives an odd sum, and adding a single odd integer with any number of
even integers gives an odd sum.
\item To prove odd sum $\Rightarrow$ odd number of integers, note that there
must be at least 1 odd integer in the set. Then, show that the number of odd
integers cannot be even.
\end{enumerate}

\end{enumerate}

\textbf{Greatest common divisor facts}

\begin{enumerate}
\item For any 2 integers x and y, their gcd is a positive integer
\begin{enumerate}
\item The proof stems from fact that any integer has at least 1 positive divisor (namely, the integer 1).
\item Hence, if there are no divisors > 1, 1 will be the greatest common divisor
\end{enumerate}

\item For any integers x, y, we know there exists unique q and r, such that x = qy + r
\\ In general, it is not true that if a is a common divisor of x and r, then a divides y
\\ For example, 6804 = 7(930) + 294. Then, 42 is common divisor of (6804, 294) but does not divide 930

\item k is a common divisor of integers a, b iff $ k \mid gcd(a, b) $
\begin{enumerate}
\item We know from lecture that if k is a common divisor, then $ k \mid gcd(a,b) $
\item If $ k \mid gcd(a, b) $, then k divides a and b, by transitivity of divisibility
\end{enumerate}


\item Show if c divides x, y and z, then c divides gcd(x, y) and z
\begin{enumerate}
\item If c divides x and y, then c divides gcd(x, y). This was proved in lecture
\end{enumerate}

\item Show that $ gcd(x, y, z) \leq gcd(gcd(x,y), z) $
\begin{enumerate}
\item Let d = gcd(x, y, z)
\item Since d divides x and y, then by previous result, it divides gcd(x, y)
\item Since d divides gcd(x, y) and z, then d divides gcd(gcd(x,y), z) [By the same result]
\item We know d are gcd(gcd(x, y), z) are both positive
\item Hence, $ d \mid gcd(gcd(x,y), z) \Rightarrow d = gcd(x, y, z) \leq gcd(gcd(x,y), z) $
\end{enumerate}

\item Show that $ gcd(gcd(x, y), z) \leq gcd(x, y, z) $
\begin{enumerate}
\item We will show that gcd(gcd(x, y), z) is a positive divisor of x, y and z
\item We already know gcd(gcd(x, y), z) is positive and divides z
\item gcd(gcd(x, y, z)) divides gcd(x, y) and since gcd(x, y) divides both x and
y, then by transitivity of divisibility, gcd(gcd(x, y), z) divides x and y
\item Hence, gcd(gcd(x, y), z) is a positive divisor of x, y and z
\item By definition of gcd, $ gcd(gcd(x, y), z) \leq gcd(x, y, z) $
\end{enumerate}

\item $ gcd(gcd(x, y), z) = gcd(x, y, z) $

\item If gcd(a, b) = 1, then $ a \mid bc \Rightarrow a \mid c $
\begin{enumerate}
\item Suppose ak = bc, for some integer k
\item We know there exist integers x, y such that ax + by = 1
\item Multiplying both sides by c, cax + cby = c
\item Simplifying, cax + aky = c = a(cx + ay)
\item Thus, $ a \mid c $ as $ cx + ay $ is an integer 
\end{enumerate}

\item If a, b are relatively prime integers, then there is no common prime
integer in the prime factorisation of a and b

\end{enumerate}

\end{document}