DIVISIBILITY | GCD

[rough crystal]

try to apply the lemma of bezout

[digital lava]

allright

[velvet cloud]

check

[uneven trout]

,rcw

[vague jacinth]

Given, $\gcd(a, b) = 1$
To prove that $\gcd(a + b, a\cdot b) = 1$
Let $\gcd(a + b, ab) = k \text{s.t.} k \ne 1$
$$\implies \frac{a + b}{k} \in \mathbb{N}, \frac{a\cdot b}{k} \in \mathbb{N}$$
From here we can safely assume that $k$ must be a factor of $a\cdot b$
Which would imply that either $a$ can be re-written as some number $\alpha \cdot k$ or $b$ can be re-written as some number $\beta \cdot k$ such that $k \ne 1$ and, both of them can't be re-written that way because if they could be that would imply that $\gcd(a, b) = k$ which we already know isn't true.

Re-writing $a$ as $\alpha \cdot k$ in $\frac{a + b}{k}$ we get the expression $\frac{\cancel{k} \cdot \alpha}{\cancel{k}} + \frac{b}{k}$

[blissful arrow]

HitenTandon

[vague jacinth]

$$\because \alpha, b, k \in \mathbb{N}, k \ne 1, k \nmid b, \alpha + \frac{b}{k} \notin \mathbb{N}$$

[blissful arrow]

HitenTandon

[vague jacinth]

Similarly,
If we try re-writing b as $\beta \cdot k$, we get, $\frac{a}{k} + \frac{\cancel{k} \cdot \beta}{\cancel{k}}$

[blissful arrow]

HitenTandon

[vague jacinth]

Where the same logic applies $\because a, \beta, k \in \mathbb{N}, k \ne 1, k \nmid a \implies \frac{a}{k} + \beta \notin \mathbb{N}$

[blissful arrow]

HitenTandon

[vague jacinth]

$$\blacksquare$$

[blissful arrow]

HitenTandon

[digital lava]

Hello! Thanks for the answer. You assumed that either a or b will have k as a factor, but you did not consider the case where we take m prime factors q of a and n prime factors p of b such that: k = p1p2...pm.q1.q2...qn. In other words, neither a nor b will have k as a factor.

[vague jacinth]

Oh yea I missed that however it is fairly trivial to prove as well.

Assume that $a$ can be re-writren as $\alpha \cdot k_1$ and b can be re-writren as $\beta\cdot k_2$

[blissful arrow]

HitenTandon

[vague jacinth]

Then, we know that $\gcd(k_1, k_2) = 1$

[blissful arrow]

HitenTandon

[vague jacinth]

Note that neither $k_1$ nor $k_2$ can equal 1

[blissful arrow]

HitenTandon

[vague jacinth]

Because if they were, then the other would've been gcd

So now, for $k_1\cdot k_2$ to be gcd

[blissful arrow]

HitenTandon

[vague jacinth]

$\frac{a + b}{k_1 \cdot k_2} \in \mathbb{N}$

[blissful arrow]

HitenTandon

[vague jacinth]

$$\implies \frac{\cancel{k_1} \cdot \alpha}{\cancel{k_1} \cdot k_2} + \frac{\cancel{k_2} \cdot \beta}{\cancel{k_2} \cdot k_1} \in \mathbb{N}$$

[blissful arrow]

HitenTandon

[vague jacinth]

Sorry I'm in a lecture rn