How to prove an equivalence of two equations?

Question

Task: Prove that . $s \cdot a + t \cdot b = c$ has a solution $s, t \in \mathbb{Z}$ iff $c$ is a multiple of $ gcd(a,b) $.

I’m not sure whether my proof is correct or not, so pleas have a look on it:

It’s to show that $s \cdot a + t \cdot b = c \Leftrightarrow gcd(a,b) \cdot p = c$

“$\Rightarrow$”: Hypothesis: $s \cdot a + t \cdot b = c$ Consequence: Then $gcd(a,b) \cdot p = c$

Proof: $gcd(a,b) \cdot p = s \cdot a + t \cdot b$ $\Leftrightarrow p = s \cdot \frac{a}{gcd(a, b)} + t \cdot \frac{b}{gcd(a, b)} = s \cdot q + t \cdot r$ such that $q = \frac{a}{gcd(a, b)} \in \mathbb{Z}$ and $r = \frac{b}{gcd(a, b)} \in \mathbb{Z}$

So there exists a $p \in \mathbb{Z}$ for the equation so the implication is shown.

For the proof of “$\Leftarrow$” I’ll take a very similar way:

Hypothesis: $gcd(a,b) \cdot p = c$ Consequence: Then $s \cdot a + t \cdot b = c$

Proof: $s \cdot a + t \cdot b = gcd(a,b) \cdot p$ From here are the steps identical to the previous proof.

I could also use the proposition of Bézout for “$\Rightarrow$” and “$\Leftarrow$” which says: $s \cdot a + t \cdot b = gcd(a,b) $ Then I get for both proofs $p=1$.

So I’m not sure if my solution is correct, especially because the proofs for “$\Rightarrow$” and “$\Leftarrow$” are identical.

Could anyone please help?

Thanks

Best regards

Asg

Answer 1

No, it is not correct. There are several issues.

• You wrote that what's to be proved is that$$s\times a + t\times b = c \iff\gcd(a,b)\times p = c.$$It is not. It is:$$(\exists s,t\in\mathbb{Z}):s\times a+t\times b=c\iff(\exists p\in\mathbb{Z}):\gcd(a,b)\times p=c.$$
• The idea of the proof of $\implies$ is correct. The proof of $\Longleftarrow$ makes no sense. You cannot just say that “the steps are identical”. The goal is to prove that there are integers $s$ and $t$ such that $s\times a+t\times b=c$ assuming that there is an integer $p$ such that $\gcd(a,b)\times p=c$. You did no such thing.