# How to show that $A_1 = A_2$?

supposition: $A_1=\{k \in \mathbb{Z}\ \colon\ k | (bc +a) \text{ and }k |b\}$, $A_2=\{k \in \mathbb{Z}\ \colon\ k|a \text{ and }k|b\}$
claim: $A_1=A_2$

(my) proof: Let's show that $A_1 \implies A_2$. Let $k \in A_1$, so $k \mid (bc +a)$ and $k \mid b$. Now if $k \mid (bc+a)$, then $k \mid 1 \cdot (bc+a) -bc$ $\implies$ $k \mid a$. So $A_1 \implies A_2$.

I'm not sure how to show $k \mid 1 \cdot (bc+a) -bc$?

-
One does not usually write that a set implies another set. Rather, one write "$A_1\subseteq A_2$", and "$A_2\subseteq A_1$". –  Arturo Magidin Oct 14 '11 at 16:26
Since $k|b$, then $k|bc$. Since $k|(bc+a)$ and $k|bc$, then $k|(bc+a)-bc$. Will you be accepting any more of the 45 questions you've asked so far, or just the 7 you accepted so far (including today's acceptance of a question that was last modified on November 2, 2010)? –  Arturo Magidin Oct 14 '11 at 16:29
If $k \mid x$ and $k\mid y$ then $k\mid (x-y)$. Let $x=bc+a$, $y=bc$. We are told that $k \mid x$. We are also told that $k\mid b$, which implies $k\mid bc$, that is, $k \mid y$. –  André Nicolas Oct 14 '11 at 16:31
Explicitly, what is needed is the following: If $k|u$ and $k|v$, then $k |(au + bv)$, for all integers $a,b$. –  JavaMan Oct 14 '11 at 18:01
@alvoutila: Are you really having a hard time figuring out how $k|b$ implies $k|bc$? $k|b$, and $b|bc$, so by transitivity $k|bc$. Yes, you could go by the definition, but you are just repeating the proof that "divides" is transitive. –  Arturo Magidin Oct 15 '11 at 19:23

I think you just needed a reminder of the definition of $|$, but here are the ideas in a more spelled-out form than the comments had:

Showing $A_1\subseteq A_2$

For this part, we just have to show $\left(k∣bc+a \text{ and } k∣b\right)\Rightarrow k|a$, since the other condition for $A_2$, $k|b$, is included in the definition of $A_1$.

If $k∣bc+a$ and $k∣b$, then $(bc+a)/k$ and $b/k$ are integers, by the definition of "$|$". Multiplying the second of those by the integer $c$ tells us that $cb/k=bc/k$ is an integer, too.

But then $$\frac{bc+a}k-\frac{bc}k=\frac{a}k$$ is an integer because it's just a difference of integers.

Finally, $a/k$ being an integer means $k|a$, by definition.

Showing $A_2\subseteq A_1$

For this part, we just have to show $k|b\text{ and }k|a\Rightarrow k∣bc+a$, because $k|b$ is included in the defintion of $A_2$.

If $k∣b$ and $k∣a$, then $b/k$ and $a/k$ are integers, so "$c$ times the first plus the second" is an integer, too. But that number is $(bc+a)/k$, so $k|(bc+a)$.

Conclusion

Since $A_1\subseteq A_2$ and $A_2\subseteq A_1$, $A_1=A_2$. (If you had an element in one set but not the other to contradict the equality, it would contradict one of the two subset statements, too.)

-