# How to prove or disprove that $\{ 12x + 25y | x , y \in \mathbb{Z} \} = \mathbb{Z}$. [duplicate]

For phone users, Prove or disprove that $$\{ 12x + 25y | x , y \in \mathbb{Z} \} = \mathbb{Z}$$ I'm not sure if the counterexample of this proof is $$12x+25y = 0$$ or not. I'm totally confused, would somebody please help me?

• How is that a counterexample? $12\times 25+25\times (-12)=0$, not to mention $12\times 0 +25\times 0 =0$. – lulu Oct 27 '19 at 12:13

## 2 Answers

$$25-2(12)=1$$. If $$n$$ is any integer then we can multiply the equation by $$n$$ to get $$n=25n-(12)(2n)=25y+12x$$ where $$y=n$$ and $$x=-2n$$. This proves that RHS is contained in LHS. Since the reverse inclusion is obvious we get the equality.

• Thank you. I'm looking for the answer for a week! – Supakorn Srisawat Oct 27 '19 at 14:00

By Bézout's Theorem, you can write $$12x + 25y = \gcd(12,25)$$ for some $$x,y \in \mathbb{Z}$$. Since, $$12 = 2^2 3$$ and $$25 = 5^2$$, what is the $$\gcd(12,25)$$? How do you use it to show that $$\mathbb{Z} \subset \{12x + 25y\mid x,y \in \mathbb{Z}\}$$