all solutions of (p,n)

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

all solutions of (p,n)

G H J

Reveal topic tags

number theory proposed

L

G H BBookmark kLocked kLocked NReply

Source: ItaMO 2011, P5

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

2130 posts

Sayan

#1 h Feb 14, 2012, 3:56 PM • 2 Y

Y by Adventure10, Mango247

Determine all solutions $(p,n)$ of the equation
$n^3=p^2-p-1$
where $p$ is a prime number and $n$ is an integer

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

2903 posts

#2 h Feb 14, 2012, 11:43 PM • 2 Y

Y by Adventure10, Mango247

The solution of $(p,n) = (37,11)$ and the cubic factor really throws off a lot of things when attempting elementary methods. Does anybody have an elementary solution? I found one which uses unique factorization over $\mathbb{Z}[\phi]$ , but it is very computational...

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1354 posts

#3 h Feb 15, 2012, 12:53 AM • 2 Y

Y by Adventure10, Mango247

It can be solved elementary :
Set the trivial cases aside, $(n+1)(n^2-n+1)=p(p-1)$ $\implies$ $k(n+1)=p-1$ . Plug into the equation to obtain :
$n^2 - n(1+k^2)-(k^2+k-1)=0$
now put its $\Delta$ between two perfect squares to get $k=3$ .

(It's my ${1234}^{th}$ post

)

This post has been edited 2 times. Last edited by mahanmath, Feb 15, 2012, 7:41 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

2903 posts

#4 h Feb 15, 2012, 1:00 AM • 2 Y

Y by Adventure10, Mango247

Oh dear that works, how did I forget about that

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

866 posts

#5 h Feb 15, 2012, 4:01 AM • 1 Y

Y by Adventure10

mahanmath wrote:

It can be solved elementary :
$(n+1)(n^2-n+1)=p(p-1)$ so $k(n+1)=p-1$ . Plug into the equation to obtain :
$n^2 - n(1+k^2)-(k^2+k-1)=0$
now put its $\Delta$ between to perfect squares to get $k=3$ .

I am an amateur. So, please tell me why can't $n^2-n+1\mid p-1$ or a factor of $p-1\mid n+1.$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

2130 posts

Sayan

#6 h Feb 15, 2012, 4:14 AM • 2 Y

Y by Adventure10, Mango247

iarnab_kundu wrote:

mahanmath wrote:

It can be solved elementary :
$(n+1)(n^2-n+1)=p(p-1)$ so $k(n+1)=p-1$ . Plug into the equation to obtain :
$n^2 - n(1+k^2)-(k^2+k-1)=0$
now put its $\Delta$ between to perfect squares to get $k=3$ .

I am an amateur. So, please tell me why can't $n^2-n+1\mid p-1$ or a factor of $p-1\mid n+1.$

case 1
when, $p \mid (n+1)$
$n+1=mp$
$p-1=m(n^2-n+1)$
thus, $n^2-n+1\le p-1 < p \le n+1$
giving solution $n=1$ and $p=2$

case 2
when $p \mid (n^2-n+1)$ is given above by mahanmath

This post has been edited 1 time. Last edited by Sayan, Feb 16, 2012, 3:20 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1347 posts

WakeUp

#7 h Feb 15, 2012, 2:35 PM • 2 Y

Y by Adventure10, Mango247

Solved $n^3=p^2-p+1$ by accident..
Click to reveal hidden text

But no matter.. the same principle can be used for $n^3=p^2-p-1$ . here's what i did:

Note that $p\ge 2$ so $LHS>0$ , implying $n>0$ . Of course, $(n+1)(n^2-n+1)=p(p-1)$ . If $p|n+1$ then $n+1\ge p\implies n(n+1)\ge p(p-1)=(n+1)(n^2-n+1)$ which implies $2n\ge n^2+1$ (we can divide by $n+1>0$ ) so $n=1$ or $n=2$ . For $n=1$ , we obtain $p=2$ , otherwise $p\nmid n+1$ .

Therefore $p|n^2-n+1$ , let $pk=n^2-n+1$ . Then $k(n+1)=p-1\implies p=kn+k+1$ . Hence $kn+k+1|n^2-n+1$ .

Therefore, $kn+k+1|k(n^2-n+1)-(n-2)(kn+k+1)=3k+2-n$ .

This means one of the following is true: $kn+k+1\le 3k+2-n$ , $kn+k+1\le n-3k-2$ or $3k+2-n=0$ .

In the first case, we get $n(k+1)\le 2k+1<2(k+1)$ so $n=1$ , which we have dealt with before.

In the second case, we get $k(n+4)+3\le n\implies k<0$ , contradiction.

Otherwise we have $n=3k+2$ . But $k|n^2-n+1=(3k+2)^2-(3k+2)+1=9k^2+3k+3$ so $k|3$ , i.e. $k=1$ or $k=3$ . If $k=1$ then $n=3k+2=5$ , meaning $p=kn+k+1=7$ but these values don't satisfy the equation. If $k=3$ then $n=11$ and $p=37$ , which works out. So only solutions are $(1,2)$ and $(11,37)$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

15142 posts

#8 h Feb 15, 2012, 2:57 PM • 3 Y

Y by WakeUp, Adventure10, Mango247

Well, the problem was a spoof on the Problem 2 at 2005 Balkan Mathematical Olympiad, see http://www.artofproblemsolving.com/Forum/viewtopic.php?p=224998&sid=fafc44cee92612cb53fe7ec91f3e4536#p224998,
which precisely asked to solve $p^2-p+1 = n^3$

No big wonder the same method works for both.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1347 posts

WakeUp

#9 h Feb 15, 2012, 4:12 PM • 2 Y

Y by Adventure10, Mango247

I had never even spotted the connection! Strange..

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

2180 posts

#10 h Feb 16, 2014, 1:39 PM • 4 Y

Y by tritanngo99, Adventure10, and 2 other users

Solution. Write it as $p(p-1)=(n+1)(n^2-n+1)$ . So $p\mid n+1$ or $p\mid n^2-n+1$ .

If $p\mid n+1$ , we have $p\le n+1$ . Equality occurs only if $n=p-1$ , so that $(p-2)^2=0$ , i.e. $\boxed{(p,n)=(2,1)}$ - indeed a solution. Else, $p\mid n+1\implies p\le n$ . In this case, let $n=ap-1$ . Plugging in yields $p-1=a(n^2-n+1)$ . But if $a>0$ it follows $a(n^2-n+1)>p^2-p+1>p-1\Leftrightarrow (p-1)^2>-1$ . Now $a=0$ leads to $n=-1$ , or $p(p-1)=0$ , absurd. Thus, $p\nmid n+1$ and we have $p\mid n^2-n+1$ . So $n^2-n+1=bp$ or $p-1=(n+1)b$ . Hence (1) $p=(n+1)b+1$ and we are lead to (2) $n^2-(1+b^2)n+1-b-b^2=0\implies \Delta=b^4+6b^2+4b-3=t^2$ . But $(b^2+2)^2<b^4+6b^2+4b-2<(b^2+4)^2$ for all $b\le -4$ and $b\ge 2$ . So either $b\in \{-3,-2,-1,0,1\}$ or $b^4+6b^2+4b-3=(b^2+3)^2=b^3+6b^2+9$ . The latter case yields $4b-3=9$ or $b=3$ . The former gives $b=-1$ . Feeding back into (2) we obtain $n^2-2n+1=0$ and $n^2-10n-11=0$ , respectively. Factoring gives resp. $(n-1)^2=0$ and $(n-11)(n+1)=0$ . Checking both cases on (1) we get a unique pair, $\boxed{(p,n)=(37,11)}$ ; indeed a solution. $\blacksquare$

Arkan

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

284 posts

#12 h Apr 19, 2020, 9:40 AM • 1 Y

Y by Mango247

Any solution using mod 9

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a