3
$\begingroup$

$Proth$ $theorem$ simply depends on a result which proved by pocklington ;

The result says :

Let $N-1=q^nR$ where $q$ is prime, $n\ge1$ , and $q$ doesn't divide $R$. Assume that there exists an integer $a \gt 1$ such that :

$(1)\ \ a^{N-1} \equiv 1 \pmod N$; and

$(2)\ \ \gcd(a^{(N-1)/ q}-1, N)=1$

Then each prime factor of $N$ is of the form $mq^n+1$ with $m\ge1$

$Proth$ $theorem$ says ;

Let $N=2^nh+1$ with $h$ odd and $2^n \gt h$. Assume that there exists an integer $a\gt 1$ such that $a^{(N-1)/2}\equiv -1\pmod N$ then $N$ is prime

$Proof$ :

$N-1=2^nh$, with $h$ odd, $\,\gcd(2^n , h)=1$ and $a^{N-1} \equiv 1\pmod N$. Since $N$ is odd, then $\gcd(a^{(N-1)/2}-1,N)=1$. By the above result, each prime factor $p$ of $N$ is of the form $p=2^nm+1 \gt 2^n$. But $N=2^nh+1\lt 2^{2n}$, hence $\sqrt N \lt 2^n \lt p$ and so $N$ is prime.

The confusing part of the proof - and the part that I want someone to explain - why does

$$\gcd(a^{(N-1)/2}-1,N)=1\ \ ???????\qquad $$

$Resource$ (the new book of prime number records pages 51 52)

$\endgroup$
3
$\begingroup$

If $\,p \mid (N,\,a^{\large (N-1)/2}\!-\color{#c00}1)\,$ then $\bmod p\!:\ \color{#c00}1\equiv \overbrace{a^{(N-1)/2}\equiv\color{#0a0}{-1}}^{\large\rm by\ \color{#0a0}{hypothesis}}\,$ so $\,p\mid 2,\,$ contra $\,p\mid N\,$ odd.

Update $ $ Per request in comments we elaborate. If the gcd $> 1$ then it has a prime factor $p,$ which is a common factor of $N$ and $a^{\large (N-1)/2}-1.\,$ Therefore, working $\bmod p\,$ we have $$\ a^{\large (N-1)/2}\equiv \color{#c00}{1}$$

The following congruence also holds $\!\bmod p\,$ since by hypothesis it's true $\!\bmod N,\,$ and $\,p\mid N$

$$\,a^{\large (N-1)/2}\equiv \color{#0a0}{-1}$$

Combining the two yields $\, \color{#c00}1\equiv\color{#0a0}{-1}\,$ so $\,2 \equiv 0,\,$ so $\,p\mid 2,\,$ contra $\,p\,$ odd, by $\,p\mid N\,$ odd.

Alternatively $\ p\mid (a^{\large (N-1)/2}+\color{#0a0}{1})-(a^{\large (N-1)/2}-\color{#c00}{1})) = 2.\,$ But one should strive to use congruence methods such as those above (they will prove simpler in more complicated contexts).

$\endgroup$
  • $\begingroup$ Would you just fix the (mod) part, I think that you didn't write it very well $\endgroup$ – عبد الرحمن رمزي محمود Aug 7 at 22:30
  • $\begingroup$ @عبدالرحمنرمزيمحمود I have no idea what you mean. $\endgroup$ – Bill Dubuque Aug 7 at 22:31
  • $\begingroup$ could you explain your answer, because I don't understand it very well, would you make it more simply $\endgroup$ – عبد الرحمن رمزي محمود Aug 7 at 22:34
  • $\begingroup$ @عبدالرحمنرمزيمحمود You'll need to be more specific about what you don't understand. $\endgroup$ – Bill Dubuque Aug 7 at 22:34
  • $\begingroup$ well, thank you $\endgroup$ – عبد الرحمن رمزي محمود Aug 7 at 22:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.