Prove that for integers $a,b$, if $3|ab$ with $15x+by = 1$ for some integers $x,y$ then $3|a.$

Question

Prove that for integers $a,b$, if $3 \mid ab$ with $15x+by = 1$ for some $x,y \in \mathbb{Z}$ then $3 \mid a$.

I know that I have to show that $a=3k$, where $k \in \mathbb{Z}$.

Also I see that $15x+by=1$ can be written as $3(5)x+by=1$.

I do not know what else to do to show that $a=3k$.

Answer 1

I have actully done it this way: ab=3p, where p is an integer I know that 15x + by=1

a(15x+by)=a

15ax+aby=a
a=3(5)xa+3py
a=3(5xa+py), where 5xa+py is an integer b/c x,a,y,p are integers

so a is divisible by 3

Answer 2

Because 3 is a prime number, then $3 \mid a$ or $3 \mid b$. If $3 \mid b$then $3 \mid 15x+by=1$, abs!

Answer 3

Hint $\ 3\mid \color{#c00}{ab}\,\Rightarrow\, 3\mid \color{#c00}a(\color{#c00}by\!+\!15x) = a$

Remark $ $ Notice that $\, by+15x = 1\,\Rightarrow\, \gcd(b,15)=1\,\Rightarrow\,\gcd(b,3)=1\ $ therefore

$\ \gcd(3,b)=1,\ 3\mid ab\,\Rightarrow\, 3\mid a\ $ by Euclid's Lemma (or by unique factorization).

The above is essentially a special case of a proof of Euclid's Lemma using the Bezout gcd identity.

Answer 4

If $3|b$ is the case, it implies $3|(15x+by)$, as $3|15$.

This leads to a contradiction, namely $3|1$.

So $3$ must divide $a$