7
$\begingroup$

Can you prove or disprove the following claim:

Let $N=2^a3^b+1$ , $a>0 , b>0$ . If there exists an integer $c$ such that $$c^{(N-1)/3}-c^{(N-1)/6} \equiv -1 \pmod{N}$$ then $N$ is a prime.

You can run this test here. I have verified this claim for all composite $N$ up to $2^{100} \cdot 3^{100}+1$ with $2 \le c \le 100$ , and for all prime $N$ from this list.

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ The "only if" part is clear - by the same trick as in the answer by @Fedor it follows from $(c^{(N-1)/3}-c^{(N-1)/6}+1)(c^{(N-1)/6}+1)=c^{(N-1)/2}+1$, since for prime $N$ there are $(N-1)/2$ residues modulo $N$ with $c^{(N−1)/2}+1\equiv0\mod N$ but only $(N-1)/6$ residues with $c^{(N−1)/6}+1\equiv0\mod N$. $\endgroup$
    – მამუკა ჯიბლაძე
    Commented Aug 2, 2020 at 10:14

1 Answer 1

Reset to default
15
$\begingroup$

Yes. Obviously this $c$ and $N$ are coprime. We get $c^{(N-1)/2}+1=(c^{(N-1)/6}+1)(c^{(N-1)/3}-c^{(N-1)/6}+1)$ is divisible by $N$. Therefore $c^{N-1}-1$ is divisible by $N$, and $N-1$ is divisible by $k:={\rm {ord}}(c)$, where ${\rm ord}(x)$ denotes the multiplicative order of $x$ modulo $N$. But $(N-1)/2$ is not divisible by $k$, since $c^{(N-1)/2}\equiv -1\pmod N$. Assume that $(N-1)/3$ is divisible by $k$; then $c^{(N-1)/3}\equiv 1 \pmod N$, $c^{(N-1)/6}\equiv c^{(N-1)/3}+1\equiv 2 \pmod N$ and $$1\equiv c^{(N-1)/3}= (c^{(N-1)/6})^2\equiv 4\pmod N,$$ a contradiction. So neither $(N-1)/2$ nor $(N-1)/3$ is divisible by $k$; thus, $k=N-1$. But $k$ must divide $\varphi(N)$, so $N-1\leqslant \varphi(N)$ and $N$ is prime.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Yes, thank you, fixed $\endgroup$
    – Fedor Petrov
    Commented Aug 2, 2020 at 6:44
  • $\begingroup$ @მამუკაჯიბლაძე true, so many misprints for 8 lines, sorry. Fixed. $\endgroup$
    – Fedor Petrov
    Commented Aug 2, 2020 at 9:44

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .