0
$\begingroup$

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?

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

$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.

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

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}\}$

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.