Discrete Math - Primes: For 127 & 133, explain why one need divide by <= 5 num. to...

[EvanCraft11]

Discrete Math - Primes: For 127 & 133, explain why one need divide by <= 5 num. to...

I'm not entirely sure what the question is asking, which is half the reason I'm having problems. Any ideas/suggestions/solutions on how to tackle this?

Question: For numbers 127 and 133, explain why one needs to divide by at most five numbers to determine whether the given number is prime. Apply this process to determine if 127 is prime and if 133 is prime.

Now I found out fairly fast 127 is prime and 133 is composite. However the first part of the question really mixes me up because I assumed the numbers would need to be divided only once to determine whether it's prime or not, not at max 5 times.

 

[stapel]

I'm not entirely sure what the question is asking, which is half the reason I'm having problems. Any ideas/suggestions/solutions on how to tackle this?

Question: For numbers 127 and 133, explain why one needs to divide by at most five numbers to determine whether the given number is prime. Apply this process to determine if 127 is prime and if 133 is prime.

Now I found out fairly fast 127 is prime and 133 is composite. However the first part of the question really mixes me up because I assumed the numbers would need to be divided only once to determine whether it's prime or not, not at max 5 times.

What do you mean by "(each of) the (given) numbers would need to be divided only once to determine whether it's prime or not"? Are you saying that, in all cases, the very first attempted division is, in all cases, successful in showing primality or not?

Hint: They say "at most five numbers". What have they told you about using square roots to find ceilings on primes you need to check? How many primes fit under that ceiling, for each of these numbers?

 

[HallsofIvy]

If X is any positive number, then \(\displaystyle X= \sqrt{X}\sqrt{X}\). That means that if \(\displaystyle X= ab\), where \(\displaystyle a> \sqrt{X}\) then b must be less than \(\displaystyle \sqrt{X}\). If X= 127, since \(\displaystyle 11^2= 121< 127\) and \(\displaystyle 12^2= 144> 127\), \(\displaystyle 11< \sqrt{127}< 12\) so if any number larger than 11 is a factor, there must be a factor less than or equal to 11. To determine whether or not 127 is prime we only need to try dividing by prime numbers less than or equal to 11. There are 5 of those: 2, 3, 5, 7, 11.

 

[Steven G]

If X is any positive number, then \(\displaystyle X= \sqrt{X}\sqrt{X}\). That means that if \(\displaystyle X= ab\), where \(\displaystyle a> \sqrt{X}\) then b must be less than \(\displaystyle \sqrt{X}\). If X= 127, since \(\displaystyle 11^2= 121< 127\) and \(\displaystyle 12^2= 144> 127\), \(\displaystyle 11< \sqrt{127}< 12\) so if any number larger than 11 is a factor, there must be a factor less than or equal to 11. To determine whether or not 127 is prime we only need to try dividing by prime numbers less than or equal to 11. There are 5 of those: 2, 3, 5, 7, 11.

Since 127 is odd, I would try the odd numbers less than 12 which are 3,5,7,9,11. Sure you can remove the 9 (9=3*3) but you can also remove your 2 as it will not be a factor of 127.

 

[Steven G]

I'm not entirely sure what the question is asking, which is half the reason I'm having problems. Any ideas/suggestions/solutions on how to tackle this?

Question: For numbers 127 and 133, explain why one needs to divide by at most five numbers to determine whether the given number is prime. Apply this process to determine if 127 is prime and if 133 is prime.

Now I found out fairly fast 127 is prime and 133 is composite. However the first part of the question really mixes me up because I assumed the numbers would need to be divided only once to determine whether it's prime or not, not at max 5 times.

And how did you find out that 127 is prime and 133 is composite?
Maybe you check that 2 does not go into 127, that 3 does not go into 127,.... My question is where did you stop? As HallsofIvy pointed out you need not go past \(\displaystyle \sqrt 127\lt\ 12\), which means you can stop at 11.