What Is an Efficient Way to Identify Composite Numbers?

[Iccanui]

Thank you for the warm welcome.

I am now wondering where i should ask my questions at, which forum. Its pre-algabra so i don't want to bother anyone with some really basic things that they don't care to see/For example, the question i have right now is a method for simply finding a composite number. I am 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 can't ask anyone is that i don't 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 I am going about it all wrong.

thank you for any advice.

 

[fluidistic]

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 can't ask anyone is that i don't 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 I am going about it all wrong.

thank you for any 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.

 

[cepheid]

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

Thank you for the warm welcome.

I am now wondering where i should ask my questions at, which forum. Its pre-algabra so i don't want to bother anyone with some really basic things that they don't care to see/For example, the question i have right now is a method for simply finding a composite number. I am 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 can't ask anyone is that i don't 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 I am going about it all wrong.

thank you for any advice.

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.

 

[coolul007]

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.

 

[Iccanui]

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 :)

 

[haruspex]

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.

 

[Devils]

http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes