# Prove that if $3\mid n$ and $5\mid n$, then $15\mid n$

Prove that if $3\mid n$ ($n$ is a multiple of $3$) and $5\mid n$, then $15\mid n$.

So far I have the following incomplete proof:

Suppose that $3\mid n$ and $5\mid n$, then $∃k,l∈ℤ$ such that $n=3k$ and $n=5l$.

Now, $3k=5l$ $...?$

From here, I struggle to deduce further to show that the conclusion is true. I know that I should show that $n$ is a multiple of $15$ in some way.

• What happens when $k <5$ or $l < 3$ in your analysis? – onetimething Mar 12 '18 at 19:23
• $$\frac1{15}=\frac25-\frac13.$$ – Angina Seng Mar 12 '18 at 19:24
• What can you conclude from $5\mid 3k$ and the fact that $5$ is prime? – Arthur Mar 12 '18 at 19:25
• In lack of something better, did you try induction? – Tal-Botvinnik Mar 12 '18 at 19:25
• Hint: According to Euclid's lemma, if a prime $p\mid ab$ then $p\mid a$ or $p\mid b$. Since $5l=3k$, we know that $3\mid 5l$. Can you show now that $3\mid l$ and hence $n=5l=15q$ for some $q\in\Bbb Z$ ? – Prasun Biswas Mar 12 '18 at 19:28

## 6 Answers

$\dfrac{n}{3}=m$ is an integer, and $\dfrac{n}{5}=k$ is another integer. From this we can conclude that $m-k = \dfrac{5n-3n}{5\cdot3} = \dfrac{2n}{15}$ is also an integer, and 2 and 15 have no common factors.

Let the prime factorisation of $n$ be $p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}$ where $p_i$ are primes and $a_i\ge0$ for $i=1,\cdots,k$.

Since $3\mid n$ and $3$ is prime, without loss of generality, we have $p_1=3$ and $a_1\ge1$.

Similarly, since $5\mid n$ and $5$ is prime, without loss of generality, we have $p_2=5$ and $a_2\ge1$.

Hence $$n=3\cdot3^{a_1-1}\cdot5\cdot5^{a_2-1}\cdots p_k^{a_k}=15(\color{red}{3^{a_1-1}\cdot5^{a_2-1}\cdots p_k^{a_k}})$$ and since the expression in red is an integer, we must have that $15\mid n$.

$n=5k=3l$ so that $3|5k$ (and $5|3l$). Hence $3|k$ (and $5|l$).

• \mid is a good replacement for |. – TheSimpliFire Mar 12 '18 at 19:47

$3$ does not divide $5$ and vice versa,

$\rightarrow n = 3^a \cdot5^b \cdot.......$, as:

• If n did not have $3$ as a prime factor then, as no primes divide each other, $n$ would not divide $3$. If it didn't have any prime factors of 3 then $n= 3k + 2$ or $n= 3k +1$ for integer $k$, and hence dividing by $3$ wouldn't give an integer.

-If $n$ did not have $5$ as a prime factor (the same logic can be applied)

Therefore $n = 3\cdot 5\cdot$(other prime factors) Therefore $n= 15\cdot ......$

Below is an easier approach to the solution that some has given to me.

As $n$ is divisible by $3$, it can be expressed as $3k$, where $k$ is some integer.

As $n$ is divisible by $5$, it can be expressed as $5k$, where $k$ is some integer.

Since $3$ and $5$ are relatively prime, if a number is divisible by $5$ and $3$, then it must be divisible by $15$.

To go in to a bit more detail:

$15k$ expresses a number $n$ which is divisible by $15$.

$15k=5\cdot 3\cdot k$

Therefore, a number which is divisible by $15$ must be divisible by $5$ and $3$.