 Teacher resources and professional development across the curriculum

Teacher professional development and classroom resources across the curriculum  MENU          Session 6, Part B:
Looking for Prime Numbers

In This Part: Locating Prime Numbers | Necessary and Sufficient Conditions
Is This Number Prime?

Finding factors and checking if a large number is prime remains one of the most time-consuming tasks in mathematics. Even very powerful computers cannot do this task quickly. For this reason, prime numbers are very useful in cryptography. Secret messages are sometimes coded using large numbers that are the product of two large prime numbers.

Here are the rules you can use to find out whether a particular number is prime:

 • Pick a number n. • Start with the least prime number, 2. See if 2 is a factor of your number. If it is, your number is not prime. • If 2 is not a factor, check to see if the next prime, 3, is a factor. If it is, your number is not prime. • Keep trying the next prime number until you reach one that is a factor (in which case n is not prime), or you reach a prime number that is equal to or greater than . • If you have not found a factor less than or equal to , you can be sure that your number is prime.

Let's try a number; for example, 97. To check if 97 is a prime number, we start a list of factors, as above:

1 • 97
2 • (no number works here)
3 • (no number works here)
(4 is not prime; it doesn't need to be checked, because we know 2 didn't work)
5 • (no number works here)
(6 is not prime; it doesn't need to be checked, because 2 and 3 didn't work)
7 • (no number works here)
(8 is not prime; it doesn't need to be checked, because 2 and 4 didn't work)
(9 is not prime; it doesn't need to be checked, because 3 didn't work)

This brings us to 10. Ten is greater than the square root of 97, and therefore its partner on the right would have to be less than 10. Since we've already checked every number less than 10, we know that none of them are factors of 97. Therefore, 97 is prime.  Problem B5 a. Why don't you need to check any prime numbers greater than 11 to see if 127 is prime? b. Can you explain the rule for where to "stop?" Problem B6 a. Use this method to determine if 257 is prime. b. What is the greatest prime you need to check? Problem B7 Use this method to determine if 359 is prime.   Video Segment In this video segment, Liz and Jeanne try to determine whether a large number is prime. They apply divisibility rules and computational shortcuts to solve the problem. Watch this segment after you've solved Problems B5-B7. Were the methods you came up with similar or different? If you are using a VCR, you can find this segment on the session video approximately 16 minutes and 50 seconds after the Annenberg Media logo.    In Part A of this session, we looked for prime factors of numbers. Using this method, the prime factorization of 72 is 2 • 2 • 2 • 3 • 3, or 23 • 32. In Part B, we listed all the factors of the number 72 in ascending order: 1, 2, 3, 4, 6, 8, 9, 12, 18, 24, 36, and 72. Notice that these two lists are very different. The prime factorization, which the fundamental theorem of arithmetic says is unique, lists only the prime factors of 72 and lists each factor as many times as it appears. In contrast, the list of all factors lists all numbers that are factors of 72, many of which are not prime. When doing problems, make sure to think about this distinction. Next > Homework  Session 6: Index | Notes | Solutions | Video

© Annenberg Foundation 2017. All rights reserved. Legal Policy