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

Comments

Post a Comment

Popular posts from this blog

Sums and integration against counting measure: Part I

-
For other posts in this series, see https://explaining-maths.blogspot.com/search?q=Sums+and+integration+against+counting+measure In case the MathJax mathematics below does not display properly in your browser, I have made a PDF of the main article available via my  WordPress blog  at  https://explainingmaths.files.wordpress.com/2023/08/sums-and-integration-against-counting-measure_-part-i.pdf Note added 30/8/23: I'm not quite sure when I started to say "integration against a measure". I'm not alone, but I think that "integration with respect to a measure" is a lot more common! However, I don't want to change the titles of my latest 10 blog posts, so I'll leave it as it is. I'll probably change back to "integration   with respect to a measure" in future though! It has been a while since I wrote a mathematical post! Here I thought I would say something about Measure and Integration which is relevant to my research. For these posts I as
Read more

Discussion of the proof that the uniform norm really is a norm

-
In response to a request on Piazza, I gave a detailed proof that the uniform really is a norm, including some comments and warnings on possible pitfalls along the way. Here (essentially) is what I said. Let’s have a look at \(\|\cdot\|_\infty\) on the bounded, real-valued functions on \([0,1]\) (but you can also work with bounded functions on any non-empty set you like, and the same proof will work). We define \(\ell_\infty([0,1]) = \{f: f \textrm{ is a bounded, real-valued function on }[0,1]\,\}\,,\) and this is the set/space we will look at. So we set \(Y=\ell_\infty([0,1])\). Then you can check for yourselves that \(Y\) really is a vector space over \(\mathbb{R}\) (using the usual "pointwise" operations for functions). Note that the zero element in this vector space is the constant function \(0\) (from \([0,1]\) to \(\mathbb{R}\)), which I'll denote by \(\mathbf{0}\) here for clarity. (We also used \(Z\) for this function in one of the exercises.) I'll first give
Read more

Revisiting liminf and limsup

-
This post is also available in PDF form from my WordPress Blog at  https://explainingmaths.wordpress.com/2023/09/01/revisiting-liminf-and-limsup/ My recent series of posts about Fatou's Lemma for sums was aimed primarily at mathematics students at 3rd-year undergraduate level or above. So I think I should write a post more suitable for first-year undergraduate students. So I'm going to have another look at the topic of $\liminf$ and $\limsup$ for bounded sequences of real numbers (though most of what I say can be generalised to sequences, or even nets, of extended real numbers). I said quite a lot about this in a previous post on my WordPress blog in the post https://explainingmaths.wordpress.com/2009/01/10/an-application-of-absorption-to-teaching-lim-inf-and-lim-sup/ and there was a lot of discussion in the comments below the post. In particular, in those comments, I discussed the $\liminf$ and the $\limsup$ of some examples of sequences $(x_n)$, including the following exam
Read more