my solution: $p^2-p+1=q^3 <->p(p-1)=(q-1)(q^2+q+1)$ hence $p(p-1)$ divisible to (q-1).But $(p,p-1)=1$ so $p$ divisible to $(q-1)$ or $(p-1)$ divisible to $(q-1)$ But $p >q$ so that $(p-1)$ divisible to $(q-1)$.hence $(p-1)=k*(q-1)$ $(k \in Z)$ Now we have $q^2+(1-k^2)q+(k^2-k+1)=0$ so that $k^4-6k^2+4k-3$ is a quare number .But $(k^2-3)^{2} \leq k^4-6k^2+4k-3<(k^2-1)^{2}$ so we are easy to see the solution $k=3$ then we have the root $(p,q)=(19,7)$

nhat wrote: hence $p(p-1)$ divisible to (q-1).But $(p,p-1)=1$ so $p$ divisible to $(q-1)$ or $(p-1)$ divisible to $(q-1)$ Why wouldn't the prime factors of $q-1$ divide into two groups, one dividing $p$ the other dividing $p-1$? Pierre.

In another hand, the reasoning can be adapted : Since $p$ is prime, then $p$ divides $q-1$ or $q^2+q+1$. If $p$ divides $q-1$, let $q = ap+1$ for some nonnegative integer $a$. Then $a(q^2+q+1) = p-1.$ But if $a > 0$ we have $q>p$ which leads to $q^2+q+1 p-1$, a contradiction. It is easy to see that $a=0$ is not possible. Thus $p$ divides $q^2+q+1$, which means that $q^2+q+1 = kp$ so that $p-1 = k(q-1)$ and we end as proposed by Nhat. Pierre.

I have another way to prove that $p$ divides $q^2+q+1$ since $p^2-p+1=q^3$ then $p^3+1=q^3(p+1)$ so $q^3 \leq p^3+1$ (1) also $p^2-p+1=q^3 \Rightarrow p(p-1)=(q-1)(q^2+q+1)$ since $p$ is prime this means that it divides $q-1$ or $q^2+q+1$ If $p$ divides $q-1$ then $p \leq q-1 <q \Rightarrow p^3<q^3$ and from (1) we deduce that $q^3=p^3+1$ Hence $p^2-p+1=q^3 \Rightarrow p^2-p+1=p^3+1$ So $p$ divides $1$ which is not possible. then $p$ divides $q^2+q+1^$ and we continue like nhat ...

It is a probelm from Saint-Petersburg selection test for All-Russian of 1995. Another way to finish the solution: after we get $q^2+(1-k^2)q+(k^2-k+1)=0$, we may consider it modulo $q-1$ and get that $k-3$ is divisible by $q-1$. If $k=3$, we get $q^2-8q+7=0$, so $q=7$; else $k\ge q+2$ and LHS is less then $q^2+q-k^2q+k^2\le q^2+q-(q-1)(q+2)^2<0$.

This question came from a National Preparation Problem Set for this year. To prove that p must divide not q-1, it's easy to prove that p>q from which p must divide the other factor. The question, nicely, dosen't use the fact that q is prime, it only comes out incidentally. Bomb

Yes,this is not so hard,I solved it almost the same way nhat did.

$k \geq 3$, because $p|x^2+x+1$, so $-3$ is quadratic residue moduo $p$. => $6|p-1$ and $6|x-1$.

Can we extend it? Find all primes $p$ such that $p^2-p+1$ is a natural power: $p^2-p+1=q^m$, $m>1$.

let w be a third root of unity not $1$. $p^2-p+1=(p+w)(p+w^2)$ so $p+w=(a+bw)^3(-w)^k$now, seing all possibilities for $k$ mod $6$, and comparing parts we get to the only possible case $a=3$, $b=1$, $p=19$.

What if $k=2$? I tried this case for a while, without success.

$k >= 3$

It was question for Pascual2005's approach, he has different $k$

Yes Fedor, It let us in a no way walk, so i am sorry

Can we determine all primes $p$ such that $p^2-p+1$ is an odd natural power: $p^2-p+1=q^m$, $m>1$, $m$-odd.

The easiest way to prove that q-1 divides p-1 is that knowing that p>q to see that q = 2*k+1 so q-1=2*k which means that p cannot be equal to k*(q-1)

Notice that $ p^2-p=q^3-1$ defines an elliptic curve. We can then find all integral points and finish the problem.

I don't undestant why $p>q$

shinichiman wrote: I don't undestant why $p>q$ $p^2-p+1<p^3\implies p>q$

This question is also AZERBAIJAN'S selection exam.Don't copy...Be happy.................... Bilduz eeeeeeeeeeeeeeee

Well, that means Azerbadjan did copy ... by re-using this problem from the Balkan MO

See here may help you: http://www.artofproblemsolving.com/Forum/viewtopic.php?f=56&t=576488 / http://www.artofproblemsolving.com/Forum/viewtopic.php?f=56&t=487608&p=2732752&hilit=italy+prime#p2732752

I have an other solution. From $p^2-p+1=a^3$ we have $p(p-1)=(a-1)(a^2+a+1)$ so $p \mid a^2+a+1$ and $a-1 \mid p-1$. In particular $p \ge a$. We have $\frac{a^2+a+1}{p} \equiv 3 mod(a-1)$. For $a=1, 2, 3$ we don't have any solutions so we assume that $a \ge 4$. [if $a<4$ we could have $3 \equiv 1 mod (a-1)$ so the following proof is incomplete] Case 1 : $\frac{a^2+a+1}{p}=3$. Then $p-1=3(a-1)$ so $a^2+a+1=3(3a-2)$ ie. $a=1$ or $a=7$. $a=7$ gives $p=19$. Case 2 : $\frac{a^2+a+1}{p}=a+2$ We have $a+2 \mid a^2+a+1$ so $a=1$ and no solution. Case 3 : $\frac{a^2+a+1}{p}=3+k(a-1)$ with $k \ge 2$. Then $p=\frac{a^2+a+1}{3+k(a-1)} \le \frac{a^2+a+1}{2a+1} <a$ if $a>1$ which is a contradiction, so no solution. Hence $p=19$ is the only solution.

n hat wrote (k² -3)²≤k⁴-6k²+4k-3<(k²-1)² I cant understand this pls explain this

@above we know that K^4-6K^2+4k-3 is a square number. However it is greater or equal to (k^2-3)^2 and less than (K^2-1)^2 which can be seen by simple expansion (k is greater or equal to 3 as K^4-6K^2+4k-3 must be positive). letting K^4-6K^2+4k-3 equal to (k^2-3)^2, (k^2-2)^2, the only solution to k=3

I guess this is what troll NT looked like in 2005 - probably have a similar solution to those above - posting for storage.

Given, $p^2-p+1=x^3\Rightarrow p^2-p=p(p-1)=x^3-1=(x-1)(x^2+x+1)$. $\forall\ x\in\mathbb{N}$, we have $p^2-p+1=x^3\equiv0,1,8(\textbf{mod }9)\Rightarrow p^2-p\equiv0,7,8(\textbf{mod }9)$. However we know that $p^2-p\equiv0,2,3,6(\textbf{mod }9)$. This means that $9\mid (p^2-p)=p(p-1)$. Since $9$ and $p$ are coprime, we get $9\mid p-1\Rightarrow p\equiv1(\textbf{mod }9)$. This gives $p^2-p+1(\equiv x^3)\equiv1(\textbf{mod }3)$ which gives $x\equiv1(\textbf{mod }3)$. This shows that both $x-1$ and $x^2+x+1$ have a common factor of $3$. $GCD(x-1, x^2+x+1)=GCD(x-1,x^2+x+1-x^2+2x-1)=GCD(x-1,3x)=GCD(x-1, 3x-3(x-1)=GCD(x-1,3)=3$. Hence, $p$ cannot divide $x-1$ and $x^2+x+1$ simultaneously, because $p\ne3$. CASE 1) $p\mid x-1$. Let $x-1=kp\Rightarrow p(p-1)=(x-1)(x^2+x+1)=kp(x^2+x+1)\Rightarrow k(x^2+x+1)=p-1$. Now, $k\geq1\Rightarrow x-1\geq p\Rightarrow x-2\geq p-1$ and $x^2+x+1\leq p-1\leq x-2\Rightarrow x^2+3\leq 0$ which is a contradiction. CASE 2) $p\mid x^2+x+1$. Let $x^2+x+1=kp\Rightarrow k(x-1)=p-1\Rightarrow p=kx-k+1\Rightarrow x^2+x+1=k^2x-k^2+k$. This gives the quadratic in $x$ as follows: $x^2+(1-k^2)x+k^2-k+1=0$. The discriminant of this quadratic should be a perfect square. So, we have $D=(1-k^2)^2-4(k^2-k+1)=k^4-2k^2+1-4k^2+4k-4=k^4-6k^2+4k-3$ should be a perfect square. It should be positive, so $k\geq3$. Now, $(k^2-3)^2=k^4-6k^2+9\leq k^4-6k^2+4k-3=D$ (equality holds if and only if $k=3$) and $(k^2-1)^2=D+4(k^2+1)>D$. $k=3$ satisfies. For $k>3$, we have $(k^2-3)^2<D<(K^2-1)^2\Rightarrow D=(k^2-2)^2=k^4-4k^2+4=k^4-6k^2+4k-3\Rightarrow 2k^2-4k+7=0$ which has no integral solutions. So, $k$ must be $3$. This means $x^2-8x+7=0\Rightarrow x=1,7$. $x=1$ corresponds to $p=0,1$ (not prime) and $x=7$ corresponds to $p=19,-18$ (we reject $-18$). Hence, $p=19$ is the only such prime.

[redacted] Haha, I found this in Alexandru Gica, Rational Points on Elliptic Curves

Answer:$(x,p)=(7,19)$ \[p(p-1)=(x-1)(x^2+x+1)\]Firstly, we can see that $x>3$. It's obvious that $p$ doesn't divide $x-1$ because if $p$ divides $x-1$, then $x^2+x+1|p-1$ but $x^2+x+1\leq p-1<p \leq x-1<x$ which gives us a contradiction. So $p|x^2+x+1$ and $x-1|p-1$. Let $k(x-1)=p-1\implies kx-k+1=p$ $kx-k+1=p|x^2+x+1$ $kx-k+1|k(x^2+x+1)-x(kx-k+1)=x^2k+xk+k-x^2k+xk-x=2xk+k-x$ So $kx-k+1|2xk+k-x$ Let $(kx-k+1)m=2xk+k-x$ We have $(2xk+k-x)-3(xk-k+1)=-xk+4k-x-3<-4k+4k-x-3=-x-3<0$ hence $m<3$. $(2xk+k-x)-(kx-k+1)=xk+2k-x-1=k(x+2)-(x+1)\geq (x+2)-(x+1)>0$ hence $m>1$. These two gives us that $m=2$. \[2(xk-k+1)=2xk+k-x\iff x+2=3k\iff k=\frac{x+2}{3}\]$(x-1)(\frac{x+2}{3})=p-1 \iff 3p-3=x^2+x-2\iff p=\frac{x^2+x+1}{3}$ Also $3x-3=3(x-1)=p-1=\frac{x^2+x+1}{3}-1\iff 9x-6=x^2+x+1$ $\iff x^2-8x+7=0\iff (x-1)(x-7)=0$ $x=1$ gives $p^2=p$ which has no solution in prime numbers. $x=7$ gives $p=19$ so $\boxed{(x,p)=(7,19)}$

At first, note that $p^2-p+1>0$ for all $p\in\mathbb Z^{+}$, by this we can conclude that doesn't exist a negative integer $q$ such that $p^2-p+1$. Now lets assume that exists $q>1$ such that $p^2-p+1=q^3$, by arranging this equation we get $p(p-1)=(q-1)(q^2+q+1)$, given that $p$ is prime, we have $p \mid q-1$ or $p \mid q^2+q+1$. If both cases occur, we get $p \mid q^2+q+1-(q-1)^2 = 3q$, we can't have $p \mid q$ because this will lead to a contadiction, so, we get $p \mid 3$, hence $p=3$, but $3^2-3+1=25$, which isn't a perfect cube, so, both cases can't occur. Now assume $p \mid q-1$, this in particular implies that $p<q-1$. If $p>3$, we get $p-1<(p+1)(p+2)+1<q^2+q+1$, hence we need $p=2$, but $2^2-2+1=3$, which in fact, isn't a perfect cube. The only case remaining is $p \mid q^2+q+1$, and this implies that exists $k\in\mathbb Z^{+}$ such that $pk=q^2+q+1$, substituting in $p(p-1)=(q-1)(q^2+q+1)$ we get $p-1=(q-1)k=qk-k \implies p=qk-k+1$, hence, $pk=q^2+q+1 \implies (qk-k+1)k=q^2+q+1 \implies q^2+(1-k)q+(k^2-k+1)=0$. So, $q$ is an integer root of $f(x)=x^2+(1-k^2)x+(k^2-k+1)$, given that $q$ is a positive integer, we need $(1-k^2)^2-4(k^2-k+1)=k^4+6k^2+4k-3$ be a perfect square. We can see that $(k^2-3)^2\leq k^4-6k^2+4k-3<(k^2-1)^2$, and clearly $k^4-6k^2+4k-3\neq (k^2-2)^2$, therefore $k=3$ and $f(x)=x^2-8x+7=(x-7)(x+1)$, knowing that $q>0$, we can easily conclude that $q=7$, thus $p=7(3)-3+1=19$, so we conclude that the unique prime $p$ such that $p^2-p+1$ is a perfect cube is 7.