3
$\begingroup$

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"?

$\endgroup$
6
  • $\begingroup$ @EthanBolker, possibly but my calculator cannot go that far and I cannot program. Sorry. $\endgroup$
    – user25406
    Feb 20, 2022 at 16:54
  • 1
    $\begingroup$ 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. $\endgroup$
    – Peter
    Feb 22, 2022 at 10:00
  • $\begingroup$ @Peter, which test is fatser? Fermat's little theorem or the one above for large numbers. $\endgroup$
    – user25406
    Feb 22, 2022 at 13:10
  • $\begingroup$ 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. $\endgroup$
    – Peter
    Feb 22, 2022 at 13:34
  • 1
    $\begingroup$ 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$. $\endgroup$
    – Peter
    Feb 22, 2022 at 13:57

1 Answer 1

5
$\begingroup$

Nice observation, but not quite. It is indeed too good to be true.

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.

$\endgroup$
2
  • $\begingroup$ Does it also pass the test $T=(2^{341}-2)/341$ equal an integer? $\endgroup$
    – user25406
    Feb 20, 2022 at 17:00
  • 4
    $\begingroup$ Yes, because $2^{341} - 2 = 2(2^{340} - 1)$. $\endgroup$
    – mathmandan
    Feb 20, 2022 at 17:10

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .