1
$\begingroup$

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?

$\endgroup$
6
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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! $\endgroup$ – stochasm Mar 26 '13 at 22:07
  • $\begingroup$ 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. $\endgroup$ – André Nicolas Mar 26 '13 at 22:20
5
$\begingroup$

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$

$\endgroup$
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.