A Pocklington theorem failed proof of mine that baffles me

78 Views Asked by At

With the following conditions for some $a,p$, we can assure that $\mathcal N$ is a prime, where $\mathcal P$ denotes a set of all primes, as the Pocklington's theorem stated $$ \begin{align} a^{\mathcal N-1}\equiv 1 \pmod {\mathcal N}, \\ p\in\mathcal P:\sqrt {\mathcal N}-1<p\Big|(\mathcal N-1), \\ \gcd\left(a^{\frac{\mathcal N-1}{p}}-1, \mathcal N\right)=1 \end{align} $$

Let $\mathcal N=pk+1$ and $a^k=b$. We have the condition above become $\gcd(b-1,\mathcal N)=1$ and that \begin{align*} (b-1)(b^{p-1}+b^{p-2}+\cdots +1):&=(a^{k}-1)\Big((a^k)^{p-1}+(a^k)^{p-2}+\cdots+1\Big)\\ &=a^{pk}-1\equiv 0\pmod {\mathcal N}, \end{align*} so that $b^{p-1}+b^{p-2}+\cdots +1\equiv 0\pmod{\mathcal N}$.

The strange comes in when I assume that $\mathcal N$ is prime so we have that, we obtain first that $\gcd(b,\mathcal N)=1$ otherwise the above will imply $1\equiv 0\pmod{\mathcal N}$, \begin{align*} 0&\equiv1+b+b^2+\cdots b^{p-1}\pmod{\mathcal N}\\ 0&\equiv 1+b+b^2+\cdots b^{\mathcal N-1} \pmod{\mathcal N} \end{align*} Now we have $p,\mathcal N$ numbers of terms for each congruence. We subtract each one with the larger one, which is $\mathcal N>\mathcal N-1\ge p$, so that we obtain $0\equiv b^{p}+b^{p+1}+\cdots +b^{\mathcal N-1}\pmod {\mathcal N}$ and as $\gcd(\mathcal N,b)=1$, $0\equiv 1+b+b^2+\cdots +b^{\mathcal N-p-1}\pmod{\mathcal N}$. Now we focus on the following,

\begin{align*} 0&\equiv1+b+b^2+\cdots b^{p-1}\pmod{\mathcal N}\\ 0&\equiv 1+b+b^2+\cdots b^{\mathcal N-p-1} \pmod{\mathcal N}, \end{align*} with the number of $p,\mathcal N-p$ terms for each equation. This, as of my first thought, it is cool, is similar to the evaluation of $\gcd$ where we can reduce it further with the similar process. So that, I keep $x,y$ to be positive along the way, we obtain eventually some positive integer $\alpha$ $$1=\gcd(p,\mathcal N)=\gcd(p, \mathcal N-p)=\cdots =\gcd(x,y)=\cdots =\gcd(\alpha, \alpha+1)$$ This gives me the contradiction as we will have $b^{\alpha+1}\equiv 0\pmod{\mathcal N}$. At first I try another prime $q|\mathcal N$ and I got the contradiction, but I didn't use the condition $p>\sqrt{n}-1$ (and the assumed compositeness of $\mathcal N$) for this. Eventually, I tried with $\mathcal N$ itself to be a prime and I got this contradiction again. What are my failures here.

1

There are 1 best solutions below

0
On

Okay, I am sorry. I've found my failures already. The line $0\equiv 1+b+b^2+\cdots +b^{\mathcal N-1}\pmod{\mathcal N}$ should read $0\equiv 1+b+b^2+\cdots +b^{\mathcal N-2}\pmod{\mathcal N}$.

The full proof is then be as follows. Let $q|\mathcal N$ with $q\le \sqrt{\mathcal N}$ as $\mathcal N$ is assumed to be composite. We obtain that $q\le \mathcal N<p+1\Longrightarrow \gcd(p, q-1)=1.$ We then use the same process starting with \begin{align*} 0&\equiv 1+b+b^2+\cdots +b^{p-1}\pmod{q}\\ 0&\equiv 1+b+b^2+\cdots +b^{q-2}\pmod{q}, \end{align*} with $\gcd(p,q-1)=1$ we obtain the contradiction and the theorem.