1
$\begingroup$

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

  • 2
    @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.2011-10-15

1 Answers 1

1

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