Proth Numbers

Today I turned 25857 days old and was surprised to come across a number property in Numbers Aplenty that I hadn't encountered before. Or so I thought. The property referred to Proth Numbers and the previous such number was 25601 that occurred on May 7th 2019. On that occasion, I'd chosen to ignore it for whatever reason.

Proth numbers are named after a French mathematician François Proth (1852–1879). He was a French self-taught mathematician farmer who lived near Verdun, France. He doesn't earn an entry in the MacTutor History of Mathematics archive. However, David Wells mentions him in his book Prime Numbers: The Most Mysterious Figures in Math. Figures 1 and 2 contain the reference:

Figure 1

He continues on the next page:

Figure 2

In the case of 25857, the number can be represented as \( 101 \times 2^8 + 1 \) but it is not prime because it factorises to \( 3^2 \times 13^2 \times 17 \). The previous Proth number 25601 however, is a Proth prime and can be represented as \( 25 \times 2^{10}+1 \). I downloaded the proth.exe program referred to in Wells' book and ran it on my Mac using Wine. The program hasn't been updated since May of 2004 but it still does the job. A result, identifying 25601 as a prime, is shown in Figure 3:

Figure 3

The \( a =19\) refers to the fact that when N is prime, then:$$ a^{\frac{N-1}{2}}+1 \equiv 0 \mod{N}$$So when \(N = 25601\) we have:$$ 19^{\frac{25601-1}{2}}+1 \equiv 0 \mod{25601}$$The Wikipedia page on Proth primes has some interesting references including the following in reference to the primality test:

This test is a Las Vegas algorithm: it never returns a false positive but can return a false negative; in other words, it never reports a composite number as "probably prime" but can report a prime number as "possibly composite".

The Wikipedia link to the Las Vegas algorithm states that:

Las Vegas algorithms were introduced by László Babai in 1979, in the context of the graph isomorphism problem, as a dual to Monte Carlo algorithms. Babai introduced the term "Las Vegas algorithm" alongside an example involving coin flips: the algorithm depends on a series of independent coin flips, and there is a small chance of failure (no result). However, in contrast to Monte Carlo algorithms, the Las Vegas algorithm can guarantee the correctness of any reported result.

The next Proth number after today's 25857 is 26113 and it is also a Proth prime with \(a=7\). This will occur on Wednesday, September 30th 2020. Thus:$$7^{\frac{26113-1}{2}}+1 \equiv 0 \mod{26113}$$