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.


Let aZ denote the set of all integer multiples of a, bZ denote the set of all multiples of b.

1. Prove that b|a implies aZbZ

Suppose b|a, then a=bk for some integer k by the definition of divisibility. Let eaZ so that e=am for some integer m by the definition of aZ. Then e=(bk)m by substitution. Hence e=b(km) by associative law. Thus ebZ as desired since kmZ.

2. Prove that aZbZ implies b|a

Suppose for every e in aZ, e is also in bZ. By the definition of aZ, e=ak for some integer k for every e in aZ. Similarly, e=bm for some integer m since aZ is a subset of bZ. Then e=ak=bm. In particular, if we choose e=a, then a=bn for some integer n. Hence b|a as desired.

Since 1 and 2 are both proven, we have shown that aZbZ if and only if b|a. Q.E.D.