# Confusing thing at the proof of proth theorem

$$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)

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).

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