Cfrgtkky

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

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

• You wrote that what's to be proved is that$$stimes a + ttimes b = c iffgcd(a,b)times p = c.$$It is not. It is:$$(exists s,tinmathbb{Z}):stimes a+ttimes b=ciff(exists pinmathbb{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 $stimes a+ttimes b=c$ assuming that there is an integer $p$ such that $gcd(a,b)times p=c$. You did no such thing.