3

When doing factorization, I have always taught kids to work from the outside in. So for the number $28$, you start with $1$ and $28$, then $2$ and $14$, then $4$ and $7$. And once you reach the middle, you are finished. Because $5$, $6$, and $7$, will not go into $28$. A student of mine asked that on the upper side, the $7$, $14$, $28$, if that first one, the $7$ is a prime number can you stop. I have been working out factors for a few hours and have yet to find the factors going lower than the prime number. Does this work for every factorization?

David K
  • 98,388
Ken Lemos
  • 31

2 Answers2

1

If I'm reading you right, then 12 would be a counterexample, as the "high" numbers are 12, 6, and 4 without a prime number there at all. (If you mean, "if a prime appears in the high position you are done", that might be correct, although I'd have to double-check the very quick counting argument in my head to be sure.)

My counting argument is something like this: if $p$ is the largest prime in the factorization, then for each factor $m$ below it (prime or composite, other than $1$), $p\times m$ will be a factor larger than $p$ in the table, and therefore $p$ must be in the middle pair. Looking over it, I'm pretty sure that works, so that would confirm.

tabstop
  • 1,598
  • Yes, just IF you get to a prime number on the high end, you are done. I am a middle school teacher and have always taught that you have to get to the "center" to make sure there are no other factors. Such as 122. You get 122 and 1, then 2 and 61. 61 is prime so you do not have to keep going from 3 to 60 to find any other factors. – Ken Lemos Feb 03 '14 at 18:22
  • @KenLemos I edited in my counting argument, so I think you're right. – tabstop Feb 03 '14 at 18:25
  • Thank you very much. This will do it. I can start teaching the kids a new method that will make it easier for them to believe and understand. – Ken Lemos Feb 03 '14 at 18:59
1

Let me first rephrase to make certain that I understand you correctly: If we go through the factor pairs of a positive integer $n$ as you describe, and come upon a pair of factors $j,p$ with $p$ prime, $j\le p,$ and $n=jp,$ then your student wishes to know if we have found all the factor pairs.

The answer is, yes, we have, assuming that we didn't skip any factor pairs along the way. Note that $p$ is the largest prime factor of $n,$ since all the rest are factors of $j,$ and $j\le p.$ If $n=km$ for some positive integers $k,m,$ then since $p$ is a prime factor of $n=km,$ it follows that $p$ is a factor of $k$ or a factor of $m$. We may as well assume that $p$ is a factor of $m,$ so that $p\le m$ and $$k=\frac{n}{m}\le\frac{n}{p}=j.$$ Hence, by the time we reach the pair $j,p,$ we have already encountered the pair $k,m$.

Cameron Buie
  • 102,994