/- Copyright 2026 The Formal Conjectures Authors. Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at https://www.apache.org/licenses/LICENSE-2.0 Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License. -/ module public import FormalConjecturesUtil

Proth primes

A Proth number is an integer $N = k \cdot 2^n + 1$ where $k$ is odd and $1 \le k < 2^n$. A Proth number that is prime is called a Proth prime. Proth proved in 1878 that a Proth number $N$ is prime if and only if $-1$ is an $((N - 1)/2)$-th power modulo $N$. It remains open whether infinitely many Proth primes exist, and in particular whether any fixed odd multiplier such as $k = 3$ produces infinitely many primes $3 \cdot 2^n + 1$.

References:

@[expose] public sectionnamespace ProthPrime

An integer $N$ is a Proth number if $N = k \cdot 2^n + 1$ for some odd $k$ and $n \ge 1$ with $k < 2^n$.

def IsProthNumber (N : ℕ) : Prop := ∃ k n : ℕ, Odd k ∧ 1 ≤ n ∧ k < 2 ^ n ∧ N = k * 2 ^ n + 1

A prime integer that is also a Proth number (OEIS A080076).

def IsProthPrime (N : ℕ) : Prop := N.Prime ∧ IsProthNumber N

$13 = 3 \cdot 2^2 + 1$ is a Proth prime.

@[category test, AMS 11] theorem isProthPrime_thirteen : IsProthPrime 13 := ⟨⊢ Nat.Prime 13 All goals completed! 🐙, 3, 2, ⟨1, rfl⟩, ⊢ 1 ≤ 2 All goals completed! 🐙, ⊢ 3 < 2 ^ 2 All goals completed! 🐙, ⊢ 13 = 3 * 2 ^ 2 + 1 All goals completed! 🐙⟩

$41 = 5 \cdot 2^3 + 1$ is a Proth prime.

@[category test, AMS 11] theorem isProthPrime_forty_one : IsProthPrime 41 := ⟨⊢ Nat.Prime 41 All goals completed! 🐙, 5, 3, ⟨2, rfl⟩, ⊢ 1 ≤ 3 All goals completed! 🐙, ⊢ 5 < 2 ^ 3 All goals completed! 🐙, ⊢ 41 = 5 * 2 ^ 3 + 1 All goals completed! 🐙⟩

$9 = 1 \cdot 2^3 + 1$ is a composite Proth number.

@[category test, AMS 11] theorem isProthNumber_nine_and_not_prime : IsProthNumber 9 ∧ ¬ IsProthPrime 9 := ⟨⟨1, 3, ⟨0, rfl⟩, ⊢ 1 ≤ 3 All goals completed! 🐙, ⊢ 1 < 2 ^ 3 All goals completed! 🐙, ⊢ 9 = 1 * 2 ^ 3 + 1 All goals completed! 🐙⟩, fun h => absurd h.1 (h:IsProthPrime 9⊢ ¬Nat.Prime 9 All goals completed! 🐙)⟩

$7 = 3 \cdot 2^1 + 1$ is prime, but is not a Proth number because $3 \not< 2^1$.

k:ℕn:ℕhk:Odd kleft✝¹:1 ≤ nleft✝:k < 2 ^ nheq:7 = k * 2 ^ n + 1hn_le:n ≤ 2⊢ False k:ℕn:ℕhk:Odd kleft✝¹:1 ≤ 1left✝:k < 2 ^ 1heq:7 = k * 2 ^ 1 + 1hn_le:1 ≤ 2⊢ Falsek:ℕn:ℕhk:Odd kleft✝¹:1 ≤ 2left✝:k < 2 ^ 2heq:7 = k * 2 ^ 2 + 1hn_le:2 ≤ 2⊢ False k:ℕn:ℕhk:Odd kleft✝¹:1 ≤ 1left✝:k < 2 ^ 1heq:7 = k * 2 ^ 1 + 1hn_le:1 ≤ 2⊢ Falsek:ℕn:ℕhk:Odd kleft✝¹:1 ≤ 2left✝:k < 2 ^ 2heq:7 = k * 2 ^ 2 + 1hn_le:2 ≤ 2⊢ False All goals completed! 🐙

If an odd multiplier $k$ is a Sierpiński number (Nat.IsSierpinskiNumber), then $k \cdot 2^n + 1$ is never a Proth prime for any $n \in \mathbb{N}$.

@[category API, AMS 11] theorem not_isProthPrime_of_isSierpinskiNumber {k : ℕ} (hk : k.IsSierpinskiNumber) (n : ℕ) : ¬ IsProthPrime (k * 2 ^ n + 1) := fun h => (hk.2 n).2 h.1

Proth's primality theorem [Pr1878, CP05]: a Proth number $N = k \cdot 2^n + 1$ ($k$ odd, $k < 2^n$) is prime precisely when some residue $a \in \mathbb{Z}/N\mathbb{Z}$ satisfies $a^{(N - 1) / 2} = -1$.

@[category textbook, AMS 11] theorem proth_primality_criterion (N : ℕ) (hN : IsProthNumber N) : N.Prime ↔ ∃ a : ZMod N, a ^ ((N - 1) / 2) = -1 := N:ℕhN:IsProthNumber N⊢ Nat.Prime N ↔ ∃ a, a ^ ((N - 1) / 2) = -1 All goals completed! 🐙

There are infinitely many Proth primes (OEIS A080076).

Reference: Wikipedia: Proth prime

@[category research open, AMS 11] theorem infinitely_many_proth_primes : {N : ℕ | IsProthPrime N}.Infinite := ⊢ {N | IsProthPrime N}.Infinite All goals completed! 🐙

There are infinitely many integers $n \ge 2$ such that $3 \cdot 2^n + 1$ is a Proth prime.

Primes of the form $3 \cdot 2^n + 1$ are also called Thabit primes of the second kind (Wikipedia: Thabit number). Their exponents are listed in OEIS A002253, which also includes $n = 1$ ($3 \cdot 2^1 + 1 = 7$ is prime, whereas $n \ge 2$ ensures $3 < 2^n$).

@[category research open, AMS 11] theorem infinitely_many_proth_primes_multiplier_three : {n : ℕ | 2 ≤ n ∧ (3 * 2 ^ n + 1).Prime}.Infinite := ⊢ {n | 2 ≤ n ∧ Nat.Prime (3 * 2 ^ n + 1)}.Infinite All goals completed! 🐙end ProthPrime