# Is there a positive integer $n$ where $14$ divide $30^n$? Explain why.

The lecturer has not taught us proofs yet, so I think the question is not looking for a rigorous proof. My attempt:

$$30 = 2 \times 3 \times 5$$ $$\frac{30^n}{14} = \frac{2^n \times 3^n \times 5^n}{2 \times 7} = \frac{2^{n-1} \times 3^n \times 5^n}{7}$$

Now I have written this in prime numbers, which I presume will make it easier to solve.
I feel that $$7$$ is not going to divide any power of $$2$$, $$3$$, or $$5$$.
This is as close as I can get to a proof.

• Yeah, it seems alright. Just take mod 7 on both sides and you're done. – Matti P. Mar 13 '19 at 11:15
• The proof is absolutely valid. – Peter Mar 13 '19 at 11:17

## 3 Answers

Your idea is fine, but you don't have to actually divide $$30^n$$ by $$14$$. Just note that $$30^n=2^n3^n5^n$$ (which you did) and that therefore, since there is no $$7$$ here (and since $$7$$ is prime), $$2^n3^n5^n$$ is not a multiple of $$7$$. In particular, it is not a multiple of $$14$$.

• My confusion is: How do we know $7$ cannot divide $2^n3^n$ or $2^n5^n$ $3^n5^n$, these combinations? – wingerse Mar 13 '19 at 11:35
• Because if a prime divides a product, it divides one of the factors. So, if $7\mid2^n3^n5^n$, then $7\mid2$, or $7\mid3$, or $7\mid5$. But this does not occur. – José Carlos Santos Mar 13 '19 at 11:38

You can also reason as follows:

• $$30^n = (2\cdot 14 + 2)^n = m\cdot 14 + 2^n$$ for a positive integer $$m$$
• It follows if $$14 | 30^n$$, then $$14| 2^n$$ which is impossible as $$7$$ is not a factor of any power $$2^n$$

We have $$30^n\equiv 2,4,8\mod 14$$ so exists no such exponent for $$n\geq1$$ and $$n\in\mathbb{N}$$