Proth's theorem

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

Proth's theorem

G H J

Reveal topic tags

modular arithmetic

number theory unsolved

L

G H BBookmark kLocked kLocked NReply

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

979 posts

#1 h Jan 22, 2008, 3:28 PM • 2 Y

Y by Adventure10, Mango247

How to prove: Let $n = h\cdot 2^k + 1, h < 2^k, 2\nmid h$ . Then $n$ is prime if and only if $a^ {(n - 1)/2}\equiv - 1\pmod n$ for some integer $a$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1677 posts

#2 h Jan 23, 2008, 5:10 AM • 2 Y

Y by Adventure10, Mango247

If $n$ is prime, then any nonsquare $a$ will satisfy $a^\frac{n-1}{2}\equiv -1\pmod{n}$ . It remains to show the converse.

If $a^\frac{n-1}{2}\equiv -1\pmod{n}$ , then let $p$ be a prime divisor of $n$ . We must have $a^\frac{n-1}{2}\equiv -1\pmod{p}$ so the order of $a$ modulo $p$ must divide $2^k$ and be divisible by $p-1$ . This gives $p\equiv 1\pmod{2^k}$ .

Now $p$ is of the form $1+a\cdot 2^k$ . Also, $\frac{n}{p}\equiv 1\pmod{2^k}$ , so we have $n=(1+a\cdot 2^k)(1+b\cdot 2^k)$ for some $b$ .

This means $h=a+b+ab\cdot 2^k$ . If $b=0$ , then $n=p$ , a prime. Suppose otherwise. Then $b\geq 1$ , and we cannot have $a=b=1$ since $h$ is odd. This means
$a+b\geq 3,ab\geq 2\Rightarrow h\geq 3+2^{k+1}$
an absurd contradiction for $h<2^k$ . So $n$ prime.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1 post

Pirer

#3 h Nov 12, 2013, 5:33 PM • 1 Y

Y by Adventure10

I think that there is a mistake in the proof:

When you have $a^{\frac{n-1}{2}} \equiv -1\pmod{p}$ , you can deduce that
$\text{ord}_p(a)$ divides $n-1 = h2^k$ , and
$\text{ord}_p(a)$ divides $p - 1$ .

Nevertheless, you can't deduce than $\text{ord}_p(a)$ is divided by $p-1$ , so you can't deduce that $p-1$ divides $\text{ord}_p(a)$ and, thus, divides $h2^k$ .

I think that to aviod it we can deduce $\text{ord}_p(a) = 2^\alpha$ , for any $\alpha \in {0,\ldots, k}$ and then write $p = a\cdot 2^\alpha +1$ . If so,

$N/p \equiv 1/(-1) \equiv -1 \pmod{2^\alpha} \Rightarrow N/p = b\cdot 2^\alpha +1$

Then,

$h\cdot 2^k = N = (N/p)\cdot p = (a\cdot 2^\alpha + 1)\cdot (b\cdot 2^\alpha + 1)$

I suppose that I should try to use that $h < 2^k$ so $h\cdot 2^k < 2^{2k}$ , but I don't know how to continue...

PD. I know that this is an old post, but I'm trying to find a correct proof of Proth's Theorem and I can't find it anywhere!

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a