How to prove the inverse of : $(a,b)=1, a\mid c, b\mid c \implies ab\mid c$.

68 Views Asked by At

There is known the non-constructive proof for proving the above, but the inverse is not possible to be proved in the same (non-constructive approach).

The inverse would be : $(a,b)>1, a\mid c, b\mid c \nrightarrow ab\mid c$
Employing the indirect, or the contradiction approach, assume that $ab\mid c$.
Also, $\exists k,l \in \mathbb {Z+}, c=ka, c= lb.$
Next, let $\exists n \in \mathbb {Z+}, (a,b)=n \implies \exists a',b' \in \mathbb {Z+}, a= na', b=nb'$.
$c = ka'n = lb'n$.
But, $ab = a'b'n^2$; & nothing can be stated using this sort of argument about the relation between $a'b'n^2, ka'n$, or between $a'b'n^2, lb'n.$
If say $a'b'n^2 \nmid c$, then it is improper as nothing is known about the relation between the two terms as stated above.

So, what can be a proper way to describe the failure of this way of proving the inverse.

If need can give some example to support the obvious fact about 'any' sort of relationship that can occur between $ab=a'b'n^2$ & $c=ka'n=lb'n.$

1

There are 1 best solutions below

8
On BEST ANSWER

If you wrote your statement as:

$$\gcd(a,b)=1\implies\left(\forall c\left(a\mid c\land b\mid c\right)\implies ab\mid c\right)$$

Now, the inverse statement is a constructive consequence of:

$$\gcd(a,b)\neq 1\implies\exists c\left(a\mid c\land b\mid c\land ab\not\mid c\right)$$

That's because $\lnot \forall c(P(a,b,c))$ is a consequence of $\exists c(\lnot P(a,b,c))$ . and $\lnot(X\implies Y)$ is a consequence of $X\land \lnot Y.$

So, given $\gcd(a,b)\neq 1$, you can use $c=\frac{ab}{\gcd(a,b)}$ and deduce that $ab\not\mid c$ but $a\mid c$ and $b\mid c.$

So this constructively finds $c$, but the real question is whether the statement that $\lnot(X\implies Y)$ following from $X\land \lnot Y$ is constructive.