I want to know if my prove is correct.

My goal is proving:

Hypothesis: $a,b \in \mathbb Z$ and $a,b \notin \{-1, 0, 1\}$.

Thesis: for all $ a, b$, exist $a',b'\in \mathbb Z$ that verify $$\frac ab = \frac{a'}{b'}$$ and $a'/b'$ is irreductible, that is, $\gcd (a',b') = 1$.

I do it by reductio ad absurdum. I suppose that $\gcd(a', b') \neq 1$. That is, they've got some common factor.

Then I factorize $a$ and $b$ as a primer number product. So:

$$a = \varepsilon \cdot p_1^{a_1} p_2^{a_2} \cdots p_r^{a_r}$$ $$b = \gamma \cdot p_1^{b_1} p_2^{b_2} \cdots p_r^{b_r}$$ where $\varepsilon, \gamma = \pm 1$, $r \geq 1$, $a_i \geq 0$, $b_i \geq 0$ and every primer number $p_i$ is different.

So, I define $d$ as $\gcd(a,b)$, so, by definition: $$d = p_1^{\min(a_1, b_1)} \cdots p_r^{\min(a_r, b_r)}$$

So I deduce: $$\frac ab = \dfrac{\dfrac ad}{\dfrac bd} = \dfrac{\varepsilon \cdot\dfrac{ p_1^{a_1} p_2^{a_2} \cdots p_r^{a_r}}{p_1^{\min(a_1, b_1)} \cdots p_r^{\min(a_r, b_r)}}}{\gamma \cdot\dfrac{ p_1^{b_1} p_2^{b_2} \cdots p_r^{b_r}}{p_1^{\min(a_1, b_1)} \cdots p_r^{\min(a_r, b_r)}}} = \frac\varepsilon\gamma \cdot \dfrac{p_1^{a_1 - \min(a_1, b_1)} \cdots p_r^{a_r - \min(a_r, b_r)}}{p_1^{b_1 - \min(a_1, b_1)} \cdots p_r^{b_r - \min(a_r, b_r)}} $$

Then I set $$a' = \frac\varepsilon\gamma \cdot p_1^{a_1 - \min(a_1, b_1)} \cdots p_r^{a_r - \min(a_r, b_r)}$$ $$b' = p_1^{b_1 - \min(a_1, b_1)} \cdots p_r^{b_r - \min(a_r, b_r)}$$

so $a/b = a'/b'$.

Now, as I have supposed that $a'$ and $b'$ have a factor in common, then $\exists i, a_i = b_i$, $a_i \neq 0$ and $b_i \neq 0$.

So, $\forall i$, we see the behaviour of $a_i$ and $b_i$ by cases.

  • If $a_i = b_i = 0$, then they haven't got factor $p_i$ in common.
  • If $a_i > b_i$, then $\min(a_i,b_i) = b_i$.

    $a_i - \min(a_i,b_i) = a_i - b_i \neq 0$
    $b_i - \min(a_i, b_i) = b_i - b_i = 0$

    So $a_i \neq b_i$.

  • If $b_i > a_i$, by symmetry, also $a_i \neq b_i$.

We haven't found any $i$ that verify $\exists i, a_i = b_i$, $a_i \neq 0$ and $b_i \neq 0$, but we have supposed it previously! Contradiction.

So thesis is true.

  • $\begingroup$ Oops, that's true. I edit it. $\endgroup$
    – JnxF
    Commented Jan 14, 2016 at 0:35

1 Answer 1


Simpler: Let $c=\gcd(|a|,|b|)$. Then $a/b=(a/c)/(b/c)$ and $\gcd(|a/c|,|b/c|)=1$.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .