# Prove that b | a iff every multiple of a is multiple of b

Prove that every multiple of some integer b is a multiple of another integer a if, and only if b divides a. This was one of homework problems in Introduction to Abstract Algebra I was in for two lectures.

## Proof

Let $$a\mathbb{Z}$$ denote the set of all integer multiples of a, $$b\mathbb{Z}$$ denote the set of all multiples of b.

### 1. Prove that $$b|a$$ implies $$a\mathbb{Z}\subseteq b\mathbb{Z}$$

Suppose $$b|a$$, then $$a=bk$$ for some integer k by the definition of divisibility. Let $$e\in a\mathbb{Z}$$ so that $$e=am$$ for some integer m by the definition of $$a\mathbb{Z}$$. Then $$e=(bk)m$$ by substitution. Hence $$e=b(km)$$ by associative law. Thus $$e\in bZ$$ as desired since $$km\in \mathbb{Z}$$.

### 2. Prove that $$a\mathbb{Z}\subseteq b\mathbb{Z}$$ implies $$b|a$$

Suppose for every e in $$a\mathbb{Z}$$, e is also in $$b\mathbb{Z}$$. By the definition of $$a\mathbb{Z}$$, $$e=ak$$ for some integer k for every e in $$a\mathbb{Z}$$. Similarly, $$e=bm$$ for some integer m since $$a\mathbb{Z}$$ is a subset of $$b\mathbb{Z}$$. Then $$e=ak=bm$$. In particular, if we choose $$e=a$$, then $$a=b\cdot n$$ for some integer n. Hence $$b|a$$ as desired.

Since 1 and 2 are both proven, we have shown that $$aZ\subseteq bZ$$ if and only if $$b|a$$. Q.E.D.