1
$\begingroup$

Let $p$ be an odd prime, $n$ be any integer, if $$n^{(p-1)/2}\equiv -1\pmod p,$$ is it always true that $k=p-1$ is the smallest positive integer satisfy $$n^k\equiv 1\pmod p?$$ This is the little lemma I need in my solution to a bigger problem. I first hold a skeptical mind that this is false, so I want to find is it possible $$n^{(p-1)/2}\equiv -1\pmod p\quad \text{and} \quad n^{(p-1)/3}\equiv1\pmod p?$$

I think this is not obvious, because $(p-1)/2$ does not have any relation with $(p-1)/3$, I have found an example, $7^6\equiv 1\pmod {19}$, but then I checked that $7^9\equiv 1\pmod {19}$ is also true.

Is there any counterexample? Or any proof?

$\endgroup$
2
$\begingroup$

No. Take $n=5$, $p=13$. Then $\frac{p-1}{2}=6$, $5^2=-1$ mod $p$, hence $5^6=-1$ mod $p$. However, $5^4=1$.

$\endgroup$
  • $\begingroup$ I should find another way to solve my question, thanks for your counter-example! $\endgroup$ – kelvin hong 方 Mar 7 at 12:21
1
$\begingroup$

This is the little lemma I need in my solution to a bigger problem. I first hold a skeptical mind that this is false, so I want to find is it possible $$n^{(p-1)/2}\equiv -1\pmod p\quad \text{and} \quad n^{(p-1)/3}\equiv1\pmod p?$$

Yes, it is possible, e.g. $\bmod p\!=\!7\!:\,\ n\equiv -1\,\iff n^{\large 3}\equiv -1\,$ and $\ n^{\large 2}\equiv 1$

Generally: $\ \, a\equiv n^{\large (p-1)/6}\equiv -1\iff \,a^{\large 3}\!\equiv n^{\large (p-1)/2}\!\equiv -1\,$ and $\ a^{\large 2}\!\equiv n^{\large (p-1)/3}\!\equiv 1$

$\endgroup$

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.