# 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=\left(bk\right)m$ by substitution. Hence $e=b\left(km\right)$ 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.