prime numbers

[ncampbell44]

I was trying to find out if 191 was divisible by anything (turns out it's not). Is there any way to find out without dividing it by all the prime numbers up to that point? I have a Texas Instruments scientific calculator. Can that do it for me?

 

[lookagain]

I was trying to find out if 191 was [is] divisible by [any integer greater than one] anything (turns out it's not).


Is there any way to find out without dividing it by all the prime numbers up to that point? \(\displaystyle \ \ \ \ \) Yes.

You just need to check the prime numbers, p, such that \(\displaystyle p \ \le \ \sqrt{191}, \ \ to \ \ see \ \ if \ \ any \ \ will \ \ divide \ \ 191.\)

 

[Deleted member 4993]

I was trying to find out if 191 was divisible by anything (turns out it's not). Is there any way to find out without dividing it by all the prime numbers up to that point? I have a Texas Instruments scientific calculator. Can that do it for me?

For nice reference go to:

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

 

[JeffM]

You just need to check the prime numbers, p, such that \(\displaystyle p \ \le \ \sqrt{191}, \ \ to \ \ see \ \ if \ \ any \ \ will \ \ divide \ \ 191.\)

Actually, you can tell by inspection that 2 and 5 are not divisors of 191 because 191 is odd and because 191 does not end in 5.

So you need to test only primes < \(\displaystyle \sqrt{191}\) other than 2 or 5, namely 3, 7, 11, and 13.

 

[HallsofIvy]

As others have said, 13^2= 169< 191< 196= 14^2 so you only have to test 2, 5, 7, 11, and 13. If you really don't like dividing: you know the number is not divisible by 2 because it is not even. You know it is not divisible by 3 because the sum of the digits, 1+ 9+ 1= 11 is not divisible by 3. You know it is not divisible by 5 because it does not end in 5 or 0. You know it is not divisible by 7 because if we remove the last digit, 9, leaving 160, then subtract 2(9), 160- 18= 142 is clearly not divisible by 7, having remainder 2. It is not divisible by 11 because the sum of its "odd" digits, 1+ 1= 2, subtracted from the "even" digit, 9, is 7 which is not divisible by 11. Finally, it is not divisible by 13 because 4 times the last digit added to the other digits, 19+ 4(1)= 23 is not divisible by 13. http://en.wikipedia.org/wiki/Divisibility_rule#Divisibility_by_4

 

[lookagain]

... so you only have to test 2, 3, 5, 7, 11, and 13.

.