# Prove $4p-3$ is a square knowing that $n\mid p-1$ and $p\mid n^3-1$, $p$ prime

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!

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

## 3 Answers

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.