2
$\begingroup$

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.

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

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.