1

Let $n$ be an integer and assume that $30$ is a factor of $n^2$ and $15$ is a factor of $n$. Prove that $30$ is a factor of $n$.

I tried testing some numbers, e.g., $n = 30$ clearly works since $15|30$ and $30|30^2$. Also $n = 60$ works. But, how can I prove this generally?

user3184733
  • 79

2 Answers2

4
  1. Show that $2$ is a factor of $n^2$.
  2. From that, show that $2$ is also a factor of $n$.
  3. You then know that $15$ is a factor of $n$, and $2$ is a factor of $n$, and you should then easily be able to show that $30$ is a factor of $n$.
5xum
  • 123,496
  • 6
  • 128
  • 204
  • Thanks, that makes a lot of sense. Actually, I just realized, the assumption that $15$ is a factor of $n$ doesn't even need to be stated since it's implied from the statement "$30$ is a factor of $n^2$", right? Hence, $30$ being a factor of $n^2$ directly implies $30$ is a factor of $n$, correct? – user3184733 Nov 10 '16 at 11:01
  • @user3184733 Correct, because $30$ is a product of three primes to the first power. However in general, you cannot make the same conclusion. For example, $4$ is a factor of $n^2=36$, but it is not a factor of $n=6$ – 5xum Nov 10 '16 at 11:10
  • Yup, I realized because $4=2^2$, so you can only conclude that $2|n$ :) – user3184733 Nov 10 '16 at 11:11
  • @user3184733 Yup. So, if $p|n^2$ where $p$ is prime, then you can conclude $p|n$. And, if $30|n^2$, you see that $2,3,5|n^2$, and therefore $2,3,5|n$, and therefore $30|n$. – 5xum Nov 10 '16 at 11:13
0

This actually works more broadly. Prime numbers are defined in the following way:

We say that $p$ is prime if whenever $p$ divides $a \cdot b$ (written $p \mid a \cdot b$), then $p$ divides $a$ or $p$ divides $b$.

In particular, if $p \mid n^2$, then it follows that $p \mid n$.

Now, note that $30 = 2 \cdot 3 \cdot 5$ is a product of primes (none of which are to a higher power than one). It follows that if $30 \mid n^2$, then $2 \mid n^2$, $3 \mid n^2$, and $5 \mid n^2$. Hence...

Simon Rose
  • 6,793