   SEARCH HOME Math Central Quandaries & Queries  Question from nick, a student: while im doing prime factorization for one number and it can't be divided 2,3 or five so what next? Hi Nick,

You continue dividing by primes. The next prime is 7 so divide by 7, then try 11 and so on. But when do you stop?

Let's try with the number 127. Is it a prime?

It's not divisible by 2, 3 or 5. Then I tired 7 which didn't divide 127 and next 11 which also didn't divide 127. I claim that now I can stop and conclude that 127 is a prime. The reason I can stop is that the next prime after 11 is 13 and 13 × 13 = 169 which is larger than 127. Thus if 13 divided 127 then 127 = 13 × "some integer" and this integer must be smaller than 13. But I know that no prime smaller than 13 divides 127 so no integer smaller than 13 divided 127. Thus 13 can't divide 127. The same argument works for any prime larger than 11 so 127 is a prime.

So in answer to your question you keep dividing by primes but you can stop as soon as you reach a prime whose square is larger than the number you are working with.

I hope this helps,
Penny     Math Central is supported by the University of Regina and The Pacific Institute for the Mathematical Sciences.