## You are here

HomeProth prime

## Primary tabs

# Proth prime

A Proth prime is a Proth number that is also a prime number. Given a Proth number $p$, if one can find a coprime integer $b$ such that

$b^{{\frac{p-1}{2}}}\equiv-1\mod p$ |

then $p$ is a prime, and specifically a Proth prime (this is a theorem first stated by François Proth). Thanks to this theorem, Yves Gallot created an algorithm used in a primality-testing program employed by the Seventeen or Bust project. The first few Proth primes are 3, 5, 13, 17, 41, 97, 113, 193, 241, 257, 353, 449, 577, 641, 673, 769, 929, etc. (listed in A080076 of Sloane’s OEIS). Konstantin Agafonov’s discovery of the Proth prime $19249\times 2^{{13018586}}+1\approx 1.484360328715661\times 10^{{3918989}}$ currently makes for the largest known prime that is not a Mersenne prime.

Major Section:

Reference

Type of Math Object:

Definition

Parent:

## Mathematics Subject Classification

11A51*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff
- Corrections

## Comments

## proth theorem extended

how do I add it to the Proth prime page ???

Proth theorem extended:

Let Q= k*2^n +1, where n=>3 is a odd natural number & k<= 2^n +1.

If for some 'a', a^((Q-1)/4) == +/-1(mod Q), then 'Q' is prime.

Proof:

If 'm' is from the set of natural numbers, then every odd prime

divisor 'q' of a^(2^(m+1))+/-1 implies that q == +/-1(mod a^(m+2))

[concluded from generalized Fermat-number 'proofs' by Proth along

with my replacing 'm' with 'm+1'].

Now, if 'p' is any prime divisor of 'R', then a^((Q-1)/4) = (a^k)^

(2^(n-2)) == +/-1(mod p) implies that p == +/-1 (mod 2^n).

Thus, if 'R' is composite, 'R' will be the product of at least two

primes each of which has minimum value of (2^n +1), and it follows

that...

k*2^n +1 >= (2^n +1)*(2^n +1) = (2^n)*(2^n) + 2*(2^n) +1; but the

1's cancel, so k*(2^n) >= (2^n)*(2^n) + 2*(2^n) and upon dividing

by 2^n... k>= 2^n +2.

(2^n -1)*2^n +1 = (2^n)*(2^n) - 2^n +1 >= (2^n -1)*(2^n -1)= (2^n)

*(2^n) - 2*(2^n) +1; but the 1's cancel again, so 1 >= 2 is a con-

tradiction, and the smallest product of at least two primes cannot

be derived using factors (2^n -1).

However, the first result is incompatible with our definition, so

if k<= 2^n +1 and a^((Q-1)/4) == +/-1(mod Q), then 'Q' is prime.

*QED

## Re: proth theorem extended

Just make it an article and attach it to the Proth prime page.

## Re: proth theorem extended

If leavemsg2 already knows how to use TeX, then this should be a snap. He would just make sure to remove the comment marker from the package for theorems and prooves, and it would be extremely straightforward for him to convert what he has written into proper TeX.

But if he doesn't know how to use TeX, then he should look for a tutorial. There's one here on PM, and there are others on the Web as well as in books.

## Re: proth theorem extended

gents

It gets better... let Q= k*2^n +1; prime n >= 5;

let A=(((Q-3)/2-1)/2-1)2; 2^A == (Q+/-1)/2 mod Q

it's even quicker and only misses a few potential

primes; base 2 tests of this sort are also immune

to the pseudo-prime effect.

I tried to script it in PFGW but to no avail.

can you help me discover a large prime number ???

Bill

## an absolute-perfect cuboid CANNOT exist

an 'absolute'-perfect cuboid CANNOT exist... (simple logic)

if you miss the logic, please re-read it ('til it sinks in)

i. it would have to appear before PT's exceed 2^3 < 3^2.

ii. a Pythagorean Triple's standard derivation:

m,n; m^2-n^2; 2mn; m^2+n^2

2,1; 3= 2^2-1^2 4=2*2*1 5= 2^2+1^2

3,2; 5= 3^2-2^2 12=2*3*2 13= 3^2+2^2

4,3; 7= 2^2-1^2 24=2*4*3 25= 4^2+3^2

iii. these 3 PT's also happen have a minimum expanse property:

2,1 3= 2+1 ... 5= 3*1+2

3,2 5= 3+2 ... 13= 5*2+3

4,3 7= 4+3 ... 25= 7*3+4

m,n = m+n = (m+n)n +m

no other PT's are of minimum expanse after 2^3 < 3^2,

so the idiosyncracy of finding an absolute perfect cube

becomes more absurd as the search is continued further.

logically, only a 'semi'-perfect cuboid could exist with

edges (3), (4), (12), and main diagonal (13); if it were

an absolute-perfect cuboid, then the other face diagonal

would have to be integral, as in (3), (4) & (5)'s case of

the first face; it's impossible; draw it out, if necessary.

iv. an absolute-perfect cuboid can't exist; it doesn't get

any simpler than that... enjoy.

think it through 'til you get it; no need to respond; an 8th

grader understood it... the first time!

## Re: an absolute-perfect cuboid CANNOT exist

What I don't understand is what this has to do with Proth primes. There's surely some connection, but I'm not sure what that connection is, much less whether it's something I need to include in the entry.

## Re: an absolute-perfect cuboid CANNOT exist

I tried to post and couldn't except to an existing post. The entry is out of place, but I wanted to be able to post it. sorry...