I really need some help at this problem:

Let $p$ be a prime number and $n$ a natural number, $n\ge2$ such that $n \mid p-1$ and $p \mid n^3-1$. Prove that $4p-3$ is a square.

So $p \mid (n-1)(n^2+n+1)$

What if $p \mid n-1$? Treating the cases wasn't too efficient. I was thinking about Fermat's theorem but it didn't helped really much.

A hint would be really apreciated. Thanks!

  • 1
    $\begingroup$ Hint: if $m$ and $n$ are natural numbers and $m|n$, then $m\le n$. $\endgroup$
    – Fan Zheng
    Oct 10, 2016 at 20:27
  • $\begingroup$ How far can you made it with the hint? $\endgroup$
    – arkeet
    Oct 10, 2016 at 21:37

3 Answers 3


Note $p \mid n-1$ is impossible because $n \le p-1$, so we have $p \mid n^2+n+1$.

Since $n \mid p-1$, we can write $p = an+1$ for some integer $a \ge 1$. Since $p \mid n^2+n+1$, we can write $$n^2 + n + 1 = bp = b(an+1)$$ for some integer $b \ge 1$.

Reducing modulo $n$ gives $1 \equiv b \pmod{n}$, so write $b = rn+1$ for some integer $r \ge 0$. Putting this in the above equation gives $$n^2 + n + 1 = (rn+1)(an+1).$$

If $r \ge 1$, then $(rn+1)(an+1) \ge (n+1)^2 > n^2+n+1$, which is a contradiction. So $r = 0$, $b = 1$, and $n^2 + n + 1 = p$, so we get $4p-3 = (2n+1)^2$.


Hint: If $p\mid n-1$ and $n\mid p-1$, then we also have $p\leq n-1$ and $n\leq p-1$.


Given that $p\mid(n^3-1)$, thus we have $p\mid(n-1)$ or $p\mid(n^2+n+1)$. We also have $n\mid(p-1)$. Let us make cases.

Case 1: $p\mid(n-1)$ and $n\mid(p-1)$. Since $p-1\ge 1$ and $n>1$. Thus we can conclude that $p\mid(n-1)\implies p\le n-1$ and $n\mid(p-1)\implies n\le p-1$. Thus we have $n\le p-1\le n-2\implies n\le n-2\implies 0\le-2$, which is a clear contradiction. Hence $p\not\mid(n-1)$.

Case 2: $p\mid(n^2+n+1)$ and $n\mid(p-1)$. Thus, $\exists k\in\mathbb{Z},$ such that $pk=n^2+n+1$ and $\exists q'\in\mathbb{Z}$, such that $p=nq'+1$. Now $n^2+n+1\equiv 1\pmod n$ and $p\equiv 1\pmod n\implies pk\equiv k\pmod n\implies k\equiv pk=n^2+n+1\equiv 1\pmod n\implies k\equiv 1\pmod n.$

Thus $\exists q\in\mathbb{Z}$, such that $k=nq+1$. Hence we have $$p=nq'+1 \text{ and } k=nq+1\\ \implies pk=n^2qq'+n(q+q')+1=n^2+n+1\\\implies n(1-qq')=q+q'-1.$$

Now $p=nq'+1\implies nq'=p-1$ and $p-1\ge 1$. Thus $nq'\ge 1$. Now since $n>1$, hence $q'\ge 1$. This again implies that $nq'>1\implies p>2\implies p\ge 3.$

Now $pk=n^2+n+1>3\implies pk>3.$ Now $p\ge 3\implies k\ge 1.$ Now again we have $k=nq+1$. Since, $k\ge 1\implies nq+1\ge 1\implies nq\ge 0\implies q\ge 0$ $(\because n>1).$

Thus $q\ge 0,q'\ge 1\implies qq'\ge 0.$ Also $q+q'\ge 1\implies q+q'-1\ge 0.$ This implies that $n(1-qq')=q+q'-1\ge 0\implies n(1-qq')\ge 0\implies 1-qq'\ge 0 \implies qq'\le 1.$

Therefore, we simultaneously have $qq'\ge 0$ and $qq'\le 1$, which implies that $qq'=0$ or $qq'=1$.

Let us make cases.

Case 1: $qq'=1\implies q=1$ and $q'=1$. Thus $q+q'-1=1$ and $n(1-qq')=0\implies n(1-qq')\neq q+q'-1$, which is a contradiction to the fact that $n(1-qq')=q+q'-1$. Hence $qq'\neq 1$.

Case 2: $qq'=0\implies q=0$. Thus $n=q'-1\implies q'=n+1$, which in turn implies that $p=n(n+1)+1.$ Thus $4p-3=4n(n+1)+1=4n^2+4n+1=(2n+1)^2$.

Hence after analyzing all the cases we can conclude that $4p-3$ is a perfect square and is equal to $(2n+1)^2$, and we are done.


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.