Homework11.tex

\documentclass[paper=letter, fontsize=11pt]{scrartcl} % Letter paper and 11pt font size

\usepackage{amstext, amsmath, amssymb}
\usepackage[T1]{fontenc} % Use 8-bit encoding that has 256 glyphs
\usepackage[english]{babel} % English language/hyphenation
\usepackage{amsmath,amsfonts,amsthm} % Math packages

\usepackage{fancyhdr} % Custom headers and footers
\pagestyle{fancyplain} % Makes all pages in the document conform to the custom headers and footers
\fancyhead{} % No page header
\fancyfoot[L]{} % Empty left footer
\fancyfoot[C]{} % Empty center footer
\fancyfoot[R]{\thepage} % Page numbering for right footer
\renewcommand{\headrulewidth}{0pt} % Remove header underlines
\renewcommand{\footrulewidth}{0pt} % Remove footer underlines
\setlength{\headheight}{13.6pt} % Customize the height of the header
\setlength\parindent{0pt} % Remove all indentation from paragraps.

%----------------------------------------------------------------------------------------
%	TITLE SECTION Problems Set V, #17, p. 273, Problem set VI, p. 296: 1, 7, 8, 9 
%----------------------------------------------------------------------------------------

\newcommand{\horrule}[1]{\rule{\linewidth}{#1}} % Create horizontal rule command with 1 argument of height

\title{	
\normalfont \normalsize 
\textsc{San Francisco State University} \\ [25pt]
\horrule{0.5pt} \\[0.4cm] % Thin top horizontal rule
\huge MATH 301 Assignment 4  \\ % The assignment title
\horrule{2pt} \\[0.5cm] % Thick bottom horizontal rule
}

\author{Omar Sandoval}

\date{\normalsize\today}

\begin{document}

\maketitle

%----------------------------------------------------------------------------------------
%	PROBLEM #17
%----------------------------------------------------------------------------------------
\textbf{17.} For each of the following relations on the set $X$ determine whether it is
reflexive, whether it is symmetric and whether it is transitive. For those which are
equivalence relations, describe the equivalence classes. \\

\textbf{(i)} For $X = \mathbb{Z}$, put $a \sim b \Leftrightarrow a b \not=0$.
\\

Reflexive: No, since $0 \sim 0 = 0$. \\
Symmetric: Yes. $\forall a,b \in X, a \sim b \Rightarrow b \sim a$. \\
Transitive: Yes. $\forall a,b,c \in X, a \sim b \text{ and } b \sim c \Rightarrow a \sim c$ \\
This is not an equivalence relation. \\

\textbf{(ii)} For $X = \mathbb{Z}$, put $a \sim b \Leftrightarrow a b \ge 0$.
\\

Reflexive: Yes. $\forall a \in X, a \sim a$. \\
Symmetric: Yes. $\forall a,b \in X, a \sim b \Rightarrow b \sim a$. \\
Transitive: No. Since $1 \sim 0 = 1, 0 \sim -1 = 1, 1 \sim -1 = -1$. \\
This is not an equivalence relation. \\

\textbf{(iii)} For $X = \mathbb{Z}^+$, put $a \sim b \Leftrightarrow a b > 0$.
\\

Reflexive: Yes. $\forall a \in X, a \sim a$. \\
Symmetric: Yes. $\forall a,b \in X, a \sim b \Rightarrow b \sim a$. \\
Transitive: Yes. $\forall a,b,c \in X, a \sim b \text{ and } b \sim c \Rightarrow a \sim c$. \\
This is indeed an equivalence relation. \\ 
It's equivalence class would only be $\mathbb{Z}^+$
\\

\textbf{(iv)} For $X = \mathbb{Z} - \{0\}$, put $a \sim b \Leftrightarrow a b > 0$.
\\

Reflexive: Yes. $\forall a \in X, a \sim a$. \\
Symmetric: Yes. $\forall a,b \in X, a \sim b \Rightarrow b \sim a$. \\
Transitive: Yes. $\forall a,b,c \in X, a \sim b \text{ and } b \sim c \Rightarrow a \sim c$. \\
This is indeed an equivalence relation. \\
It's equivalence class would only be $\mathbb{Z}^+$ and $\mathbb{Z}^{-}$
\\

\textbf{(v)} For $X = \mathbb{Z}^+$, put $a \sim b \Leftrightarrow a b < 0$.
\\

Reflexive: No. See $1 \sim -1$. \\
Symmetric: Yes. $\forall a,b \in X, a \sim b \Rightarrow b \sim a$. \\
Transitive: Yes. $\forall a,b,c \in X, a \sim b \text{ and } b \sim c \Rightarrow a \sim c$.
And notice that $a \not\sim b \forall a,b \in \mathbb{Z}^+$. \\
Not an equivalence relation. \\

\textbf{(vi)} For $X = \mathbb{Z} - \{0\}$, put $a \sim b \Leftrightarrow a b < 0$.
\\

Reflexive: No. Notice $1 \not\sim 1$. \\
Symmetric: Yes. $\forall a,b \in X, a \sim b \Rightarrow b \sim a$. \\
Transitive: No. Notive $1 \not\sim -1$ and $-1 \sim 1$ but $1 \not\sim 1$. \\ 
Not an equivalence relation. \\

%----------------------------------------------------------------------------------------
%	PROBLEM #1
%----------------------------------------------------------------------------------------
\textbf{1.} Find the prime factorizations of 3450 and 4284 and hence find their greatest
common divisor. Compare the amount of work with the solution of Problem IV, Question 6(ii).
\\

\begin{tabular}{|l|l|}
\hline
3450 & 2  \\ \hline
1725 & 3  \\ \hline
575  & 5  \\ \hline
115  & 5  \\ \hline
23   & 23 \\ \hline
1    &    \\ \hline
\end{tabular}
\begin{tabular}{|l|l|}
\hline
4284 & 2  \\ \hline
2142 & 2  \\ \hline
1071 & 3  \\ \hline
357  & 3  \\ \hline
119  & 7  \\ \hline
17   & 17 \\ \hline
1    &    \\ \hline
\end{tabular}
\\

$3450 = 2 \cdot 3 \cdot 5^2 \cdot 23$ \\
$4284 = 2^2 \cdot 3^2 \cdot 7 \cdot 17$ \\

Thus, $gcd(3450,4284) = 2 \cdot 3 = 6$.
\\

%----------------------------------------------------------------------------------------
%	PROBLEM #7
%----------------------------------------------------------------------------------------
\textbf{7.} Prove that if $a$ and $b$ are coprime, and $a$ and $c$ are coprime, then $a$
and $bc$ are coprime.
\\

We know that $gcd(a,b) = gcd(a,c) = 1$. \\
If we were to try and divide $a$ by $bc$, we get, $\dfrac{a}{bc} = (\dfrac{a}{b}) \times
(\dfrac{1}{c})$. This is a contradiction unless $a$ and $b$ are both $1$, but we know that
cannot be the case since $gcd(a,b) = 1$, which tells us $a$ is not a multiple of $b$. \\

From that, we also get the statement $\dfrac{a}{bc} = (\dfrac{1}{a}) \times (\dfrac{a}{c})$.
That statement is also a contradiction. Since $gcd(a,c) = 1$, which tells us that a is not 
$a$ multiple of $c$.
\\

%----------------------------------------------------------------------------------------
%	PROBLEM #8
%----------------------------------------------------------------------------------------
\textbf{8.} Prove that, if $a$ and $b$ are coprime, then $ab$ is a perfect square if and
only if $a$ and $b$ are both perfect squares.
\\

If $a$ has a prime factorization, then we have;
\begin{center}
    $a = p_1^{l_1} \cdot p_2^{l_2} \cdot \dots \cdot p_n^{l_n}$
\end{center}
and if $b$ has a prime factorization, then we have;
\begin{center}
$a = q_1^{k_1} \cdot q_2^{k_2} \cdot \dots \cdot q_n^{k_n}$
\end{center}
So, if $ab$ has a prime factorization;
\begin{center}
    $ab = p_1^{l_1} \cdot p_2^{l_2} \cdot \dots \cdot p_n^{l_n} \cdot
    q_1^{k_1} \cdot q_2^{k_2} \cdot \dots \cdot q_n^{k_m}$
\end{center}
We can see that there are no $p_i = q_j$ since $a$ and $b$ are coprime. Since $a b$
is a perfect square, all $l_i$ and $k_i$ are even. 
\\

%----------------------------------------------------------------------------------------
%	PROBLEM #9
%----------------------------------------------------------------------------------------
\textbf{9.} Prove that if $m_1$ and $m_2$ are coprime positive integers, then,

\begin{center}
$a \equiv b \text{ mod } m_1 m_2 \Leftrightarrow a \equiv b \text{ mod } m_1
\text{ and } a \equiv b \text{ mod } m_2$
\end{center}


\end{document}