7
$\begingroup$

In this question someone previously asked

They presented the problem:

Given that the number 8881 is not a prime number, prove by contradiction that it has a prime factor that is at most 89.

One of the answers was this:

If all prime factors where superior to 89, they would be at least 97. Counting them with their multiplicity, if there was only one such factor it would be 8881, which contradicts the given fact that 8881 is not prime. If there are at least two (possibly equal) factors a and b, then ab≤8881 but ab≥97∗97>8881, contradiction.

I understand it until

Counting them with their multiplicity, if there was only one such factor it would be 8881

What does it mean to count numbers with their multiplicity and in this case why would the only factor be 8881.

Moreover another answer states

You're on the right lines. If 8881 is not prime, it must have at least one prime factor not equal to itself. If it has no prime factors less than or equal to 89, then it must have only prime factors greater than or equal to 97, which is the next prime up from 89. You've already found the smallest natural number which has prime factors greater than or equal to 97 (in reference to the proposed solution to the question where they state that smallest number composed of only 97 is 97^2

However wouldn't the smallest natural number which has prime factors greater than or equal to 97 be 97?

Thank you and sorry if this seems like a stupid question.

$\endgroup$
7
$\begingroup$

When we say that we are counting with multiplicity, we mean that we are counting objects which might "repeat" themselves, and we want to count all of those repetitions as distinct objects. For example, the number $8$ has only one prime factor: $2$. However, if we count the number of prime factors of $8$ with multiplicity, there are $3$ such factors: $2$, $2$, and $2$ (since $8 = 2^3$).

I imagine that most students are more familiar with this term in the context of roots of polynomials (since this topic is usually taught to students relatively early in their mathematical careers). For example, the polynomial $$ (x-1)^2(x-2) $$ has two distinct roots, but three roots if we count with multiplicity. This is because the root $x=1$ has multiplicity $2$.

This notion is discussed a little further on Wikipedia:

In mathematics, the multiplicity of a member of a multiset is the number of times it appears in the multiset...

The notion of multiplicity is important to be able to count correctly without specifying exceptions (for example, double roots counted twice). Hence the expression, "counted with multiplicity".

If multiplicity is ignored, this may be emphasized by counting the number of distinct elements, as in "the number of distinct roots"...

$\endgroup$
  • $\begingroup$ Thank you, I think I understand it now, so the proof is essentially saying if we start by counting the prime factors with their multiplicity the only one that can appear in the multiset of 8881's prime factors by itself is 8881 which contradicts the fact that it is prime, and if we carry on counting to two prime factors the smallest we can start with would be 97 and 97 however their product is > 8881, which is also a contradiction. And we can't count further with multiplicity as the prime factors would be < 97 to get anywere close to 8881 which is another contradiction. I think I get it now! $\endgroup$ – Moajiz Hussain Sep 5 at 14:59
  • 1
    $\begingroup$ Yes, that seems to be a reasonable summary of the argument. $\endgroup$ – Xander Henderson Sep 5 at 15:20
  • 1
    $\begingroup$ The term "frequency", in the context of discrete statistics, is also a synonym: if you have observations 2,2,2,5,5 you have 2 with frequency 3 and 5 with frequency 2. $\endgroup$ – Acccumulation Sep 5 at 20:28
4
$\begingroup$

Conversationally, the multiplicity of a factor is "the number of times" it divides into the number. For instance, $48=2^4\cdot3$ has both $2$ and $3$ as prime factors, but $2$ has a multiplicity of 4.

The point of the proof is that if $8881$ is not prime, it has at least two prime factors. We need to balance the assumption that those factors are greater than $89$ with the fact that $\sqrt{8881}\approx92.4$. So whatever those two prime factors are, they can't both be greater than $89$.

$\endgroup$
  • $\begingroup$ Good call, @XanderHenderson. I don't know what the community feeling is, but I have never been the slightest bit offended when someone with the rep edited one of my answers to make it clearer or more correct, and it would save you a lot of effort as well! $\endgroup$ – Matthew Daly Sep 5 at 13:08
0
$\begingroup$

How many prime factors does $8$ have? The only prime factor of $8$ is $2$, so you might say $8$ has one prime factor. But the prime factorization is $8=2\cdot2\cdot2$, and if you count the number of factors that appear, there are three of them. The latter method of counting -- counting without tossing out repeated values -- is called counting with multiplicity.

The claim about the smallest natural number with all prime factors $\geq97$ is indeed a small inaccuracy and should specify that it is finding the smallest non-prime natural number with all prime factors $\geq97$. Since $8881$ is given to be non-prime, this suffices.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.