Bulgarian National Mathematical Olympiad

If $p=3$, then $q^2|3^6-1=728=2^3\cdot 7\cdot 11$ and therefore $q=2$ which gives a solution. Let $p\ne 3$. Since $(q+1,q^2-q+1)=1$ or $3$, we have $p^2|q+1$ or $p^2|q^2-q+1$, which implies that $p<q$. If $p+1=q$ then $p=2$ and $q=3$ which is another solution. In the sequel we assume that $q\ge p+2$. Since $q^2|p^6-1=(p-1)(p+1)(p^2-p+1)(p^2+p+1)$ and $(q,p-1)=(q,p+1)=1$, we have $q^2|(p^2-p+1)(p^2+p+1)$. Moreover, we have $(p^2-p+1,p^2+p+1)=(p^2+p+1,2p)=1$ and therefore $q^2|p^2-p+1$ or $q^2|p^2+p+1$. However, $p^2-p+1<p^2<q^2$ and $(p+2{)}^2\le q^2\le p^2+p+1$, i.e. $3p+3<0$, a contradiction.