Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Finding composite numbers

  1. Aug 19, 2012 #1
    Thank you for the warm welcome.

    I am now wondering where i should ask my questions at, which forum. Its pre-algabra so i dont want to bother anyone with some really basic things that they dont care to see/


    For example, the question i have right now is a method for simply finding a composite number. Im going through the khan Academy exercises and they have this......


    Which of these numbers is composite?

    71, 79, 59, 91, 83



    Now i know what composite is ( a number that has a factor of itself, 1 and other numbers ), i know what prime is ( a number with a factor of 1 and itself ). But the thing i cant ask anyone is that i dont understand their method at arriving at the answer.


    The only way i can think to figure the answer is to do this for every number...

    71/1 = 71
    71/2 = 35r1
    71/3 = 23r2
    71/4 = 17r3
    71/5 = 14r1
    71/6 = 11r1
    71/7 = 10r1

    How long do i keep this up before i can say, yes this is a prime number and move on to the next number. The answer is given and its 91 is composite cause 1x71= 71 and 7x13= 91. But something tells me im going about it all wrong.

    thank you for any advice.
     
  2. jcsd
  3. Aug 19, 2012 #2

    fluidistic

    User Avatar
    Gold Member

    Re: Greetings and seeking advice.

    Only try to divide 71 by prime numbers. So try with 2, 3, 5, 7, etc. For this number as soon as you hit 7 you get that 71=7x13 so you're done. If I remember well there's a theorem that states that any number admits a factorization of prime number(s). So that any number is a product of prime numbers.
    And if I remember well again, you should go until you hit the square root of the number you're looking to divide, here 71. But don't use this tip for now, there's no need to use a calculator for this exercise.

    Edit: Whoops I see I made a mistake, 7 doesn't divide 71 but 91 as you've pointed out.
     
  4. Aug 19, 2012 #3

    cepheid

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Re: Greetings and seeking advice.

    You might want to start a new thread for this question, but anyway:

    By inspection, none of the numbers is even, so there is no point in trying to divide any of them by 2.

    In fact, there is no point in dividing any of the numbers by an even number, because in order for a number to be a multiple of an even number, it must be even. For example, if a number is divisible by 4, it will be divisible by 2 as well. Same goes for 6. The following probably doesn't qualify as a "proof", but I think it makes the point:

    We can represent any even number using the expression 2n (i.e. 2 x n) where n is an integer, integers being the following numbers: (0, ±1, ±2, ±3, ±4, ... etc.)

    So, let's say our mystery number (71 in this case) is denoted by 'x'. If x is divisible by an even number 2n, then that means that

    x/2n = m

    where m is an integer too (i.e. the quotient is a "whole number", basically). This means that

    x = 2nm

    Since nm is an integer, this says that x is even.

    Conclusion: there is no point in checking to see if x (71 in this case) is divisible by any even number, because, as we've shown above, in order for it to be divisible by an even number, it would have to be even itself.

    That leaves the odd numbers. It's not divisible by 5, because if it were, its last digit would be a 0 or a 5. You've shown that it's not divisible by 3, which means it's not divisible by any multiple of 3 either (by a similar argument to the one I made above for divisibility by multiples of 2). You've also shown that it's not divisible by 7. Keep in mind that any number can be expressed as a product of its prime factors -- the factors being prime numbers that multiply together to make up that number. E.g. 91 = 7*13, both of which are prime. 42 = 6*7 = 2*3*7. So 2,3, and 7 are the prime factors of 42.

    For 71, you've already eliminated the first few prime factors (2, 3, 5, 7,), so it's beginning to look more and more likely that this number is prime. In fact, I think it's true that unless if this number is a multiple of other, higher prime numbers (like 11, 13, etc), it has to be prime.

    I sort of took a trial and error approach here. I'm sure that there are systematic ways of evaluating "primeness" and that this probably involves delving into some fairly advanced math, actually.
     
  5. Aug 19, 2012 #4
    Numbers only have to be tested for primes less than the square root of the number. if the sum of the digits are divisible by 3, the number is divisible by 3, to be divisible by 11, add the odd number digits and subtract the even number digits from the right. If that number is divisible by 11 then so is the number. example: 341 = +1-4+3 = 0, zero is divisible by 11.
     
  6. Aug 22, 2012 #5
    thank you everyone. it took a few days to sink in, but i seem to be having no problems finding it now and have passed the material :)
     
  7. Aug 22, 2012 #6

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    There are also tricks that can be used for some factors above 3. E.g. if the target number is 4 digits or more, you can reduce it modulo 1001 easily: remove the leading digit and subtract the same from the 4th digit. Since 1001 has factors 7, 11, 13, you can deal with all of those by analysis of the same 3 digit remainder.
     
  8. Aug 23, 2012 #7
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook