# Primality test based on the properties of Pascal Triangle sum of a given row

I will list the properties of a row of Pascal triangle that will be used in the test.

1-Every number of a given row $$n$$ is divisible by the row number $$n$$ if the row number is a prime except of course the first and last number $$1$$.
2-The sum of all the elements of any given row with row number n, including the first and last $$1$$, is $$2^n$$. This result is valid for a row number $$n$$ prime or composite. This means that we do not need to add all the elements of a row to know the total value of the sum. We can just write it down for a given row with a given row number $$n$$.

Test: The test consists in evaluating the following quantity: $$T=(2^n -2)/n$$. If the result is an integer then we can conclude that $$n$$ is a prime. If the result is not an integer, we can conclude that $$n$$ is a composite number. This test bypasses the calculation and summation of the binomial coefficients to get the sum of all the elements of a given row $$n$$.

Examples:

1-For row number $$7$$, we have $$T=(2^7-2)/7=126/7=18$$ and integer so $$7$$ is a prime
2-For row number $$15$$, we have $$T=(2^{15}-2)/15=32766/15=2184.40$$ so $$15$$ is not a prime.

Can this result be proven?

I can imagine a situation where, for large numbers, we run into $$2$$ or more elements of a given row $$n$$, initially not individually divisible by $$n$$ adding up to a sum that is divisible by $$n$$. I don't know enough to prove this will never happen for large numbers.

Is this a case of "too good to be true"?

• @EthanBolker, possibly but my calculator cannot go that far and I cannot program. Sorry. Feb 20, 2022 at 16:54
• Fermat's little theorem guarantees that $2^{n-1}\equiv 1\mod n$ holds for every odd prime. So, if an odd number does not satisfy this congruence, it cannot be prime. Some composites however pass this test as well (see anwer below) , but actually most primality tests start with such a Fermat-test. There are many refinements , the best known efficient test with no known counterexample is the BPSW-primality test. Feb 22, 2022 at 10:00
• @Peter, which test is fatser? Fermat's little theorem or the one above for large numbers. Feb 22, 2022 at 13:10
• Your test is equivalent to the Fermat-test with base $2$. We have $n\mid 2^n-2$ iff $2^{n-1}\equiv 1\mod n$ , if $n$ is odd. Feb 22, 2022 at 13:34
• The Fermat test is faster in the sense that $2^{n-1}\equiv 1\mod n$ can be verified without actually dividing $2^{n-1}-1$ by $n$ with remainder. Note that for large $n$ , $2^n-2$ is too large to check the divisibility directly , instead repeated squaring is used to determine $2^{n-1}$ modulo $n$. Feb 22, 2022 at 13:57

The smallest base-2 Fermat pseudoprime is 341. It is not a prime, since it equals 11·31, but it satisfies Fermat's little theorem: $$2^{340} ≡ 1 \pmod{341}$$ and thus passes the Fermat primality test for the base 2.
• Does it also pass the test $T=(2^{341}-2)/341$ equal an integer? Feb 20, 2022 at 17:00
• Yes, because $2^{341} - 2 = 2(2^{340} - 1)$. Feb 20, 2022 at 17:10