Tuesday, January 1, 2013

Is 2013 a prime?


Definition: A prime number p is a positive integer that has exactly two factors, 1 and p itself.

Examples: 2, 3, 5, 7, 11, 13, 17 and 19 are all the primes less than 20. Primes keep going on forever, so no matter how large a number you choose, there are primes that are even larger.

Definition: In earlier times, 1 was considered a prime, but now it is called a unit, and it stands alone among the positive integers, since it has only one factor, namely itself.

Definition: Numbers bigger than 1 that are not prime are composite.

Examples: Here are the composite numbers that are less than or equal to ten.

4 has three factors: 1, 2 and 4
6 has four factors: 1, 2, 3 and 6
8 has four factors: 1, 2, 4 and 8
9 has three factors: 1, 3 and 9

Question: Is 2013 a prime number?

Explanation: It's "obvious" that 2012 couldn't be a prime number, because any even number greater than 2 is divisible by 2, so 2012 = 2 × 1006. More than two factors means composite not prime. For the same reason, 2014 isn't prime. It's also easy to see 2015 isn't prime, because it is divisible by 5. To be exact, 2015 = 5 × 403.

Okay, so what about 2013? It's not quite as obvious, but 2013 is not prime because it is divisible by 3. The rules for divisibility by 2 and 5 are simple and taught in schools everywhere. The method is only concerned with the final digit.

Rule for divisibility by 2: The last digit must be 0, 2, 4, 6 or 8.

Rule for divisibility by 5: The last digit must be 0 or 5.

Rule for divisibility by 3: This one takes a little arithmetic, but only a little. Add up the digits of a number. If that sum is divisible by 3, the original number is divisible by 3. And to the contrary, if the sum isn't divisible by 3, the original number isn't divisible by 3, either.

2013 = 3 × 671, so it has more than two factors and is not prime.

One step further: Every number can be broken down into a unique product of primes, known as a prime factorization.

Examples: 

We already know that 2012 = 2 ×1006, but 1006 isn't prime.
2012 = 2 × 2 × 503. It turns out that 503 is a prime number, so 2 × 2 × 503 is the prime factorization of 2012.

We already know 2013 = 3 × 671. Is 671 a prime? No, it is 11 × 61, so 3 × 11 × 61 is the prime factorization of 2013.

Tomorrow: How to determine if a number is prime or composite.

1 comment: