# 645 Four Consecutive Odd Numbers Pass a Prime Number Test

There is a quick test to see if an odd number is prime: Plug in the number for x in the equation y = 2^x (mod x). If y = 2, then x is VERY LIKELY a prime number. I call that equation the quick prime number test.

The smallest composite number that gives a false positive to this test is 341. Click on that number to see an in depth description of this quick prime number test and how it relates to Pascal’s triangle. This is only a picture of a calculator.

The second smallest number to give a false positive is 561. Click on that number to see MANY false positives for other tests for that composite number.

645 is not usually tested to see if it is prime because it ends with a 5 and the sum of its digits is a multiple of 3. From those two divisibility rules, we know that 645 is a composite number divisible by both 3 and 5.

Still 645 is the third smallest number to give a false positive to the quick prime number test.

Here is a chart of the quick prime number test applied to the odd numbers from 343 to 681. (A similar chart for odd numbers up to 341 can be seen here.) Whenever y equals 2, I’ve made that 2 red. Prime numbers have been highlighted in yellow. Pseudoprimes 561 and 645 are in bold print. There are 119 numbers less than or equal to 561 that pass this prime number test, and only 3 of those numbers are composite numbers that give a false positive. Amazing.

Perhaps you noticed something else that’s pretty amazing: 641, 643, 645, and 647 are FOUR consecutive odd numbers that pass the quick prime number test, and 645 is the only composite number of the four. Those are the smallest four consecutive odd numbers that pass the test.

It makes me wonder if longer strings of numbers that pass the test are possible. As almost everybody knows 3, 5, and 7 are the only consecutive odd numbers that are also prime numbers. All other strings of three or more consecutive odd numbers contain at least one composite number that is a multiple of 3. Including pseudoprimes like 645 certainly opens up the possibility of longer strings of prime and pseudoprime numbers.

I also continue to be fascinated by the amount of times on the chart that y equals an odd power of 2 (2, 8, 32, 128, 512).

Interesting observation: All three of these pseudoprimes are of the form 4n + 1. All prime numbers of the form 4n + 1 can be written as the sum of two square numbers that have no common factors. 341, 561, and 645 cannot be written as such a sum so they cannot be prime numbers.

______________________________________

645 is the hypotenuse of the Pythagorean triple 387-516-645. What 3-digit number is the greatest common factor of those three numbers?

• 645 is a composite number.
• Prime factorization: 645 = 3 x 5 x 43
• The exponents in the prime factorization are 1, 1, and 1. Adding one to each and multiplying we get (1 + 1)(1 + 1)(1 + 1) = 2 x 2 x 2 = 8. Therefore 645 has exactly 8 factors.
• Factors of 645: 1, 3, 5, 15, 43, 129, 215, 645
• Factor pairs: 645 = 1 x 645, 3 x 215, 5 x 129, or 15 x 43
• 645 has no square factors that allow its square root to be simplified. √645 ≈ 25.39685. # 341 is the smallest composite number that gives a false positive for this Quick Prime Number Test

• 341 is a composite number.
• Prime factorization: 341 = 11 x 31
• The exponents in the prime factorization are 1 and 1. Adding one to each and multiplying we get (1 + 1)(1 + 1) = 2 x 2 = 4. Therefore 341 has exactly 4 factors.
• Factors of 341: 1, 11, 31, 341
• Factor pairs: 341 = 1 x 341 or 11 x 31
• 341 has no square factors that allow its square root to be simplified. √341 ≈ 18.466 341 is a composite number that sometimes acts like a prime number. To understand why, we need to understand a little bit about modular arithmetic:

When one number is divided by another, sometimes there is a remainder. Modular arithmetic is all about the remainders. We don’t care how many times one number divides into another number; we only care about the remainder.

Something very curious happens when the equation in the chart below is applied to a prime number greater than 2: The remainder is always 2. It really is! For example, 2^5 = 32 and 32 divided by 5 is 6R2. We say that 32 (mod 5) = 2 or 2^5 (mod 5) = 2 because 2 is the remainder. The fact that the remainder for prime numbers applied to this equation is always 2 is amazing, and can be a QUICK TEST to see if an odd number might be a PRIME NUMBER! If the remainder isn’t 2, that odd number is definitely NOT prime! QUICK PRIME NUMBER TEST (Please, excuse my using = instead of ≡, the “equal sign” that is usually used in modular arithmetic. I think = looks less intimidating.)

Passing the remainder test is a necessary but not a sufficient indicator that a number is prime: Even though 341 is not a prime number, the quantity 2^341 divided by 341 also has a remainder of 2. Since 341 = 11 x 31, but passes the remainder test, it is known as a pseudoprime number.  341 is the smallest composite number that passes this particular test, so 341 is an amazing number!

Also in the chart above, 2 is the most common remainder, followed by 8, then 32, then 128. All of those numbers are odd powers of 2. The even powers of 2 do not appear on the chart at all! That is a very curious phenomenon as well. (However, if x is an even number, it appears that y will usually be an even power of 2.)

Earlier mathematicians have written equivalent expressions and algorithms, but I prefer using “2^x (mod x)” because it takes very few keystrokes to enter into a calculator before hitting the equal sign:

Look at the first two images from this link on Pascal’s Triangle.  The first demonstrates that in prime numbered rows, the numbers in that row can be divided evenly by that prime number (not counting the 1’s at the beginning and ending of each row).

• For a composite number, such as 15, at least one of the numbers in the row will NOT be divisible by that composite number. In row 15, 1 is the 0th term, 15 is the 1st term, 105 is the 2nd term, 455 is the 3rd term, and 1365 is the 4th term and so forth.
• Terms that are divisible by 15 are the 1st term (15), the 2nd term (105), the 4th term (1365), the 7th term (6435), the 8th term (6435), the 11th term (1365), and the 13th term (105). All of those term numbers, 1, 2, 4, 7, 8, 11, and 13, do NOT have factors in common with the number 15.
• The terms that are NOT divisible by 15 are the 3rd term (455), the 5th term (3003), the 6th term (5005), the 9th term (5005), the 10th term (3003), and the 12th term (455). All of those term numbers, 3, 5, 6, 9, 10, and 12, have at least one factor in common with the number 15. If we could see the VERY large numbers for the 341st row, and if they weren’t expressed in Scientific Notation, we could note that the following terms would NOT be divisible by 341: terms numbered 11th, 22nd, 33rd, 44th, and so forth and the terms numbered 31st, 62nd, 93rd and so forth. However, if you add those terms together, that very large sum would be divisible by 341. That is so amazing, even though 341 is not prime!

The second image from Pascal’s Triangle demonstrates that the sum of the numbers in any row of Pascal’s triangle equals two raised to the second number in that row. These two images work together so that 2^p (mod p) will always be 2 for every prime number greater than 2 because every number in the prime numbered rows can be evenly divided by that prime number. (Except the 1 at the beginning of the row and the 1 at the end of the row; Note 1 + 1 = 2)

Now that is why this amazing test for prime numbers works as well as it does while giving just a few false positives!