Prime Numbers

David wants to determine whether or not the number 73 is a prime number. He has already determined that the prime numbers, 2, 3, *EDIT (5), and 7 are not factors of 73. Does david need to test any other numbers to see if 73 is a prime number? (HINT: 7 x ? = 73)


I know there are various methods to deducing if a number is prime. I just know that 73 is. What method are they referring to in this problem? They want me to use it later in a different problem to determine if 437 is prime. What is so special about 7?

I'm a little puzzled that '4' was attempted. Are you SURE this shouldn't be '5'?

Factors come in pairs (if you count perfect squares as 2 copies of the same thing). Example: When finding factors of 36, one mighy try '3'. Yes! 3*12. Is there, then, a need to check to see if '12' is a factor?

What's special about 7: 7 is the largest prime number less than the square root of 73.

Did you "answer" the hint? 73/7= 10.4284.... so 73= 7*10.4285... The point is that if we have x= ab and also x= cd where c> a, then d< b- if you increase one factor, you must decrease the other to have the same product.

If 73 had any factor larger than 10, the other factor would have to be less than 7. We already know that 73 has no factor less than 7 so also cannot have any factor larger than 10. But we don't have to test 8, 9, or 10 because they are not prime.

Another way of looking at that is that 73 lies between 64 and 81: its square root lies between 8 and 9. If 73 had a factor larger than 9, the other factor would have to be less than 8- but we know there are no factors less than 8.

In general, to find all factors of an integer, you only have to try prime numbers less than or equal to the square root of the integer.

the question of whether or not 437 is prime is more interesting. i do not (as yet) know the answer to this question, but i will find out as i write this post.

20*20 = 400, so the square root of 437 is more than 20.

21*21 = (20+1)(20+1) (yes, this is how i do arithmetic) = 400 + 40 + 1 = 441 > 437. so we only need to check for prime factors < 20 (since 20 isn't prime).

i don't really know the primes less than 20 off the top of my head, but if i think about it, for a bit, i guess i do:

2,3,5,7,11,13,17,19.

2 is out, since 437 is odd. 4+3+7 = 14, which is not divisible by 3, so 437 is not divisible by 3 (i forget where i learned this trick, but it sure is handy).

437 does not end in 5 (and we already determined it wasn't even, so it certainly doesn't end in 0) so it is not divisible by 5. so much for the "easy primes".

for 7, i have to divide. 437/7 = 62 + 3/17, so 7 doesn't divde 437.

437/11 = 39 + 8/11, so 11 doesn't divide 437 (there's a trick for 11, too, but i never bother with it).

437/13 = let's see....390 for 30 leaves 47 left over...minus 39 is 8, 437/13 = 33 + 8/13 (hmm...429 is divisible by 11 AND 13, interesting...)

437/17 = ugh. larger primes are no fun....ok, think: 340 for 20, 97 left over...guess 5? 17*5 = 85....that leaves 12, 437/17 = 25 + 12/17.

not divisible by 17.

ok, one more shot at divisibility: 437/19 = ...i can DO this! start with 20, that's 380....57 left over, 19*3 = 57, rats! it's not prime after all,

437 = 19*23 (confirming: 19*23 = (10+9)(20+3) = 200 + 30 + 180 + 27 = 230 + 207 = 437, yep, i'm convinced, how about you?)

disclaimer: no calculators were used, and no integers harmed during the making of this post. all rights reserved. for additional information contact your local math department.

Thanks guys, great explanations.

Quote:

---

Originally Posted by HallsofIvy

What's special about 7: 7 is the largest prime number less than the square root of 73.
...
In general, to find all factors of an integer, you only have to try prime numbers less than or equal to the square root of the integer.

---

Jman115: The above is worth repeating/emphasizing/internalizing. See if you can formulate (or find) a proof!