Rational number proposition **Prop.**Every $$r \in Q$$ can be written as r = m/n, where $$ m,n \in Z$$ such that n>0 and gcd(m,n) = 1 (r is in lowest terms)
If I start by saying that let $$r \in Q$$ Then there exist $$a,b \in Z$$ such that b≠0 and r = a/b, should I divide two cases of b? for b>0 and b<0 ?
Any help would be appreciated!
 A: Since $r \in Q$ there exist $m_1,n_1\in Z$ with $n_1\ne 0$ and $r=m_1/n_1.$ So $r=m_2/n_2$ where $n_2=|n_1|\in N,$ and $m_2=(n_1/|n_1|)m_1=\pm m_1\in Z.$ 
So r is an integer divided by a natural number, so there is a LEAST $n\in N$ such that some $m\in Z$ satisfies $r=m/n.$
Now if $p\in Z$ and $|p|>1$ we cannot have $p|m$ and $p|n.....$
.... otherwise we have $m'=m/|p|\in Z$ and $n>n'=n/|p|\in N,$ giving $r=m'/n'$ with $n'<n.$ But that would contradict the "LEAST"-ness of $n.$
A: If the denominator, $b<0$ then form the equivalent fraction by multiplying both numerator $a$ and denominator $b$ by $-1$.
So begin by saying something like '...it is only necessary to consider $b>0$ since negative denominators can be made positive by forming an equivalent fraction etc, etc, ...' Hope this is clear.
A: Let $\frac{a}{b}\in\mathbb{Q}$ (with $(a,b)\in\mathbb{Z}\times\mathbb{Z_{>0}}$).
If $a=0$, then $\frac{0}{1}$ does the job.
Otherwise, $a\neq0$ and we consider the set
$$
E:=\left\{c\in\mathbb{Z}:\exists d\in\mathbb{Z}_{>0}\text{ s.t. }\frac{c}{d}=\frac{a}{b}\right\}
$$
First, $a\in E$, so $E$ is not empty. Also, remark that $\frac{a}{b}=\frac{c}{d}$ is possible only if $a$ and $c$ are both positive or both negative.
Hence, if $a>0$, then $E$ has the lower bound $0$ and so $E$ has a minimum, let's say $c_{\min}$, for which there exists $d_{\min}\in\mathbb{Z}_{>0}$ such that $\frac{a}{b}=\frac{c_{\min}}{d_{\min}}$. This last representation does the job. In effect, we must have $\text{pgcd}(c_{\min},d_{\min})=1$, because, otherwise, it is easy to verify that we would have
\begin{align*}
c_{\min}&=\alpha_1\cdot\text{pgcd}(c_{\min},d_{\min})\\
d_{\min}&=\beta_1\cdot\text{pgcd}(c_{\min},d_{\min})
\end{align*}
with $\alpha_1<c_{\min}$ and $\frac{a}{b}=\frac{\alpha_1}{\beta_1}$, contradicting the minimality of $c_{\min}$ in $E$.
If $a<0$, then $E$ has the upper bound $0$ and so $E$ has a maximum, let's say $c_{\max}$, for which there exists $d_{\max}\in\mathbb{Z}_{>0}$ such that $\frac{a}{b}=\frac{c_{\max}}{d_{\max}}$. This last representation does the job. In effect, we must have $\text{pgcd}(c_{\max},d_{\max})=1$, because, otherwise, it is easy to verify that we would have
\begin{align*}
c_{\max}&=\alpha_2\cdot\text{pgcd}(c_{\max},d_{\max})\\
d_{\max}&=\beta_2\cdot\text{pgcd}(c_{\max},d_{\max})
\end{align*}
with $\alpha_2>c_{\max}$ and $\frac{a}{b}=\frac{\alpha_2}{\beta_2}$, contradicting the maximality of $c_{\max}$ in $E$.
Remarks


*

*It can be shown that this representation is unique.

*A constructive proof of existence would show that the reduced form of $\frac{a}{b}$ is $\frac{c}{d}$ where
\begin{align*}
a=c\cdot\text{pgcd}(a,b)\\
b=d\cdot\text{pgcd}(a,b)
\end{align*}
Since Euclid's algorithm permits us to calculate $\text{pgcd}(a,b)$, we can calculate the reduced form of any rational number.
