# For every integer $n$, $15\mid n$ iff $3\mid n$ and $5\mid n$

I'm trying to prove that for every integer $n$, $15\mid n$ iff $3\mid n$ and $5\mid n$. The first part of this bi-conditional was easy for me to prove, but I'm having problems with the second. Here is what I have so far:

Suppose $15\mid n$. Then we can let $k$ be some integer such that $15k=n$. Since $3(5k)=15k=n, 3\mid n$. Also, since $5(3k)=15k=n$, it follows that $5\mid n$.

Now I'm stuck trying to prove it the other way. I've assumed that for some integers $k$ and $j$, $3k=n$ and $5j=n$, and am trying to come up with something of the form $15p=n$ for some integer $p$, but I can only seem to come up with fractions, which seems wrong. Any hints?

It is a good start, not much more is needed.

You have $3k=n$ and $5j=n$. It follows that $3k=5j$.

Note that $3k=5j$ in particular says that $3$ divides $5j$. It is a standard fact of number theory that if a prime $p$ (here $p=3$) divides a product $ab$, then $p$ divides $a$ or $p$ divides $b$ (or both). Clearly $3$ does not divide $5$. So $3$ divides $j$.

Let $j=3w$. Then $n=5j=(5)(3w)=15w$.

Remark: $1.$ The fact that if a prime $p$ divides $ab$, then $p$ divides $a$ or $p$ divides $b$ is sometimes called Euclid's Lemma. Books VII to IX, and to a fair degree Book X of Euclid's Elements are number-theoretic in character.

$2.$ We do not really need Euclid's Lemma in this case. For we only want to show that if $3$ divides $5j$, then $3$ divides $j$. If $3$ does not divide $j$, then $j$ leaves a remainder of $1$ or $2$ on division by $3$. In either case, you can show that the remainder when $5j$ is divided by $3$ is not $0$.

• Ahh, Thanks! This problem is out of How to Prove it by Velleman, and I haven't actually had a chance to start studying number theory. I'll definitely remember this, thanks! – stochasm Mar 26 '13 at 22:07
• You are welcome. I added in the remarks a little something about doing it without euclid's Lemma, or more precisely proving euclid's Lemma in the case $p=3$. So we can actually write a detailed proof with no reference to other stuff. – André Nicolas Mar 26 '13 at 22:20

Hint $\rm\ \ 5,3\mid n\:\Rightarrow\: \dfrac{n}5,\,\dfrac{n}3\in\Bbb Z\ \Rightarrow\ 2\left(\dfrac{n}5\right)-\dfrac{n}3 \, =\, \dfrac{n}{15}\in\Bbb Z\:\Rightarrow\: 15\mid n$

$d \mid n$ means $\exists k, dk = n$.

So we want to prove that $\exists k, 15k = n$ iff $\exists h,l, 5h=3l=n$.

To do one direction write $15 = 3 \cdot 5$: there $\exists k, 3 \cdot 5 \cdot k = n$ so $5(3k)=3(5k)=n$ proves the implication with $h=3k$, $l=5k$.

In the other direction, we have $5h=3l=n$ so $3\mid h$ (and $5 \mid l$), put $k = h/3$ and you get $5 \cdot 3 \cdot k = n$.

Since $3|n$ then $n=3k$. But you also know $5|n$, that is, $5|3k$. Now, here use the fact that $5\not|3$.

By using that fact you get that $5|k$, so $k=5j$. Therefore $n=3k=3(5j)=15j$.

Now $15$ divides $3n$ and $5n$, and $n = 10n - 9n = 2 \cdot (5n) - 3 \cdot (3n)$ so..

This is basically using Bezout and the fact that $3$ and $5$ are coprime. When $a$ and $b$ are coprime, $xa + yb = 1$ for some integers $x$ and $y$. From this a more general theorem can be proven.

If $a$ and $b$ are coprime integers, both dividing $n$, then $n$ is divisible by $ab$.

Proof: $an$ and $bn$ are divisible by $ab$, so $n = xan + ybn$ is divisible by $ab$.

Your problem is the case $a = 3$, $b = 5$.