# How to prove all numbers which divided by square numbers are also divided by square numbers of prime?

I'm solving algorithm problem. In this problem, there are max and min.

Between max and min, which number is not divided by square number? is problem.

When I solving this problem, many users solved using square numbers of a prime number.

But I don't understand why I can use square numbers of a prime number instead of normal square numbers.

EX) MAX = 10, MIN = 20

Normal square numbers = $10^2, 11^2 ... 20^2$

Prime square numbers = $11^2, 13^2 ... 19^2$

Users said that I can solve which numbers are not divided by square numbers using prime square numbers.

Can you explain why it can be?

• Actually, from $10$ to $20$, you want to test which are not divisible by $2^2$, $3^2$ or $4^2$, since $5^2=25 >20$ is too high. But there is no need to test division by $4^2$ as it is a multiple of $2^2$, so you only need to test division by squares of those prime numbers less than or equal to the square root of the maximum Commented Mar 28, 2018 at 10:45
• @Henry I understand your saying. but it is not strict proof. Commented Mar 30, 2018 at 2:10
• @haram Please remember that you can choose an answer among the given if the OP is solved, more details here meta.stackexchange.com/questions/5234/…
– user
Commented Apr 1, 2018 at 8:23

HINT

By FTA $\forall n\in \mathbb{N}$ we have that $n=\prod p_i^{a_i}$.

• I don't know that sign of right side. Can you explain more easily? Commented Mar 28, 2018 at 10:44
• Take a look to the link en.wikipedia.org/wiki/…
– user
Commented Mar 28, 2018 at 10:44

If $m^2|n$, take $p$ prime, $p|m$. Then $p^2|m^2$ and $p^2|n$.

• Can you explain more easily? Commented Mar 30, 2018 at 2:13
• @haram, every integer $m >1$ has a prime factor $p$ and the relation "... divides ..." is transitive. Commented Mar 30, 2018 at 14:09