How can I prove a rational number can be expressed as a ratio of two integers, with at least one of them odd?

Question

The proof for $\sqrt{2}$ being irrational relies on the fact that any rational number can be expressed as the ratio of two integers, which means that for every rational number $x$ it is possible to find two integers $p$ and $q$ so that $x = \frac{p}{q}$.

It then sounds fairly obvious that it is possible to express $x$ as the ratio of two integers with at least one of them being an odd number. As a matter of fact it is so obvious that my manual does not bother giving any sort of proof or explanation.

Still, how can I prove that any rational number can be expressed as the ratio of two integers, with at least one of them odd?

Answer 1

By definition a rational number can be expressed as a ratio of two integers a and b. If a and b are both even we can divide both by two giving two integers with the same ratio. We can repeat this process until a is odd or b is odd.

Answer 2

So, aided by your comments, I think I was able to come up with a reasonable proof. Please let me know if the reasoning is wrong or superfluous.

For any $k \in \mathbb Z^*$, let us consider the set of all the positive integral powers of $2$ that divide $k$.

$2^0 \times k = k$ so the set contains $0$ and thus is not empty. In addition, according to the Archimedean property, $\exists n \in \mathbb N \quad 2 \times n \ge k \implies \exists n \in \mathbb N \ 2^n \ge k$ which means $2$ raised to the power of any integer greater than or equal to this $n$ cannot divide $k$, so the set has a majorant. As it is a subset of $\mathbb Z$ and it is not empty, it has a maximal element that we note $n_k$.

$k$ can then be written as $k = 2^{n_k} \times i$, with $i$ being an odd integer. Indeed, if it wasn’t, then there would exist an integer $j$ so that $k = 2^{n_k + 1} \times j$ which would mean $n_k+1$ belonged in the set, which is not possible because $n_k$ is the maximal element of the set.

Let $n \neq 0$ be a rational number. $$ \begin{align} n \in \mathbb Q^* \iff &\exists (p, q) \in \mathbb Z^2 \quad n = \frac{p}{q}\\ \implies &\exists (i, j) \in \mathbb Z^2 \quad n = \frac{2^{n_p} \times i}{2^{n_q} \times j} \end{align} $$ $n$ is then either equal to $\frac{i}{2^{n_q - n_p} \times j}$ (if $n_q \ge n_p$) or $\frac{2^{n_p - n_q} \times i}{j}$ (if $n_p \ge n_q$). In both cases, the numerator or denominator is odd.

If $n = 0$, then $n = \frac{0}{1}$ and $1$ is odd.

This proves that any rational number can be written as the ratio of two integers with at least one of them odd.