# Fall 2016, problem 25

Let $n,p$ be integers such that $n>1$ and $p$ is a prime. If $n\mid p-1$ and $p\mid n^3-1$, show that $4p-3$ is a perfect square.

5 years ago

Dear board administrators: There seems to be a bug in the upvoting system: I just upvoted this solution myself in the same login session, in which I composed it.

Strangely, it doesn't seem necessary to assume that $p$ is prime:

Since $(n^3 -1) = (n - 1)(1 + n + n^2)$ and $p | n - 1$ can easily be seen to contradict the assumptions, we have $$p | 1 + n + n^2$$ So let $k, l \in \mathbb{N}$, such that: $$p - 1 = k n \textrm{ and } 1 + n + n^2 = l p$$ We observe:

1. $p$ and $n$ are coprime by $p - kn = 1$.
2. $l - 1\lt n$ This follows from the equation $1 + n + n^2 = l k n + l$: If l >= n + 1, then the right hand side would be larger than the left.

The definition of $k$ and $l$ gives: $$p - kn = lp - n - n^2 \implies (l - 1) p = n (n + 1 - k)$$ We use the two facts established above on this equation: $p$ and $n$ are coprime, so $n | l - 1$. But $n > l - 1$, so

$$l = 1$$

This gives the required result immediately: $$4 p - 3= 4 lp - 3 = 4(1 + n + n^2) - 3= (2 n + 1)^2$$ Done.

You used the fact that p is prime when you decided that there are two cases in  the begining of your proof .

rubs 5 years ago

@rubs: Correct. Thanks.

Nelix 5 years ago
cookdaniel
2 months ago

Note that n|p−1⟹p−1=kn⟹p=kn+1 for some k∈N

Similarly p|n2+n+1⟹mp=n2+n+1 for some m∈N

It follows that n2+n+1=m(kn+1)=mkn+m⟹n2+(1−mk)n+(1−m)=0

Now, the roots of this quadratic must be integers, so the discriminant must be a perfect square. It follows that there is some N∈N such that (1−mk)2+4(1−m)=N2

Case I: m=1 In that case p=n2+n+1⟹4p−3=(2n+1)2

Case II: m>1 . In that case we easily see that 4(m−1)≥2(mk−1)+1 But this quickly shows that k=1 which implies that p=n+1 which would imply that n+1|n2+n+1 which is impossible.