Quiz question on prime factorization

Last year many of us at the University of Nottingham created Moodle quizzes for our students to practise on. I had some fun with the technical aspects of this, and may post on that another time. Typically my FPM quizzes would have a few relatively routine questions, followed by a "challenge" question (clearly labelled as such) which was intended to stretch them. Quite often we would discuss the challenge questions in the "live" sessions. I also made a small number of "challenge quizzes" (clearly labelled again) where all of the questions were challenge questions.

Here is a Piazza post I made to explain one of the "relatively routine" quiz questions related to prime factorization.

FPM First quiz on Prime Factorization: question 3

Hi everyone,

I have been asked about this quiz question, from the First quiz on Prime Factorization.

This is really all about divisibility by primes, and highest powers of primes dividing natural numbers.

First let's see why (a) is correct.

Let $k\in\mathbb{N}$ and suppose that $k^3$ is divisible by $25$.
Then certainly $5|k^3$ and so, since $5$ is prime, $5|k$ too.
So there is an integer $n$ with $k=5n$, and then we have $k^2=25n^2$ so (since $n^2$ is an integer) we have $25|k^2$.
This shows that (a) is true for all positive integers $k$.

Another way to think about this is as follows. Let $m \in \mathbb{N} \cup \{0\}$ be the highest power of $5$ dividing $k$.  (Note that $k \in\mathbb{N}$, so this makes sense.)
Then the highest power of $5$ dividing $k^3$ is $3m$. (As we saw in Workshop 5.)
But $k^3$ is divisible by $25=5^2$, so we must have $3m \geq 2$, and so $m \geq 2/3$. But $m$ is an integer, so $m \geq 1$. Finally, the highest power of $5$ dividing $k^2$ is $2m$, and $m \geq 1$, so $2m \geq 2$, and so we obtain $5^2|k^2$, as required.

Well, maybe that wasn't very exciting! But suppose that the question had used $625=5^4$ instead of $25$. Then in our argument above we would have had $m \geq 4/3$ instead. So, because $m$ is an integer, we would have had $m \geq 2$. In fact, you can use these ideas to prove that, for all natural numbers $k$, we have       $$5^4 | k^3 \Leftrightarrow 5^2 | k \Leftrightarrow 5^6| k^3\,.$$ [Exercise!]
Moreover, the same argument works for any other prime number, not just $5$. And if you play around with the argument you can establish some fairly general results.

OK, now (b) to (d) are supposed to be false (meaning here that there is at least one positive integer $k$ for which the relevant implication fails).
If we want to check this, we should look for counterexamples.
For example, for (b), $k=2$ gives a counterexample, because then $16\,|\,k^4$ but $k^3=8$ is not divisible by $16$.

I think I can leave it to you to find similar counterexamples for (c) and (d).

Best wishes,
Dr Feinstein