Results 1 to 6 of 6

Math Help - Prime Numbers

  1. #1
    Junior Member
    Joined
    Oct 2008
    From
    Maine
    Posts
    70

    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?
    Last edited by Jman115; November 17th 2011 at 05:42 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Aug 2007
    From
    USA
    Posts
    3,110
    Thanks
    2

    Re: Prime Numbers

    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?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Apr 2005
    Posts
    15,319
    Thanks
    1294

    Re: Prime Numbers

    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.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,281
    Thanks
    673

    Re: Prime Numbers

    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.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Oct 2008
    From
    Maine
    Posts
    70

    Re: Prime Numbers

    Thanks guys, great explanations.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Super Member TheChaz's Avatar
    Joined
    Nov 2010
    From
    Northwest Arkansas
    Posts
    600
    Thanks
    2

    Re: Prime Numbers

    Quote Originally Posted by HallsofIvy View Post
    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!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: October 22nd 2011, 12:37 PM
  2. Prime numbers
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: April 26th 2010, 06:35 PM
  3. Prime- numbers
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: March 27th 2010, 11:04 PM
  4. prime numbers
    Posted in the Algebra Forum
    Replies: 1
    Last Post: September 5th 2009, 07:39 AM
  5. which numbers are prime
    Posted in the Algebra Forum
    Replies: 2
    Last Post: March 9th 2008, 07:51 PM

/mathhelpforum @mathhelpforum