If $p=3$ then $9|q^3+1$ and $q^2|728$. This follows $q=2$. iF $q=3$ then $p=2$. If $p,q \ge 5$ then since $p^2|(q+1)(q^2-q+1)$ we get $p^2|q+1$ or $p^2|q^2-q+1$. We also have $q^2|(p^3-1)(p^3+1)$ then $q^2|p^3-1$ or $q^2|p^3+1$. Case 1. If $p^2|q+1$ and $q^2|p^3+1$. This follows $q^2|p+1$ or $q^2|p^2-p+1$. If $q^2|p+1$ then $p^2q^2|(p+1)(q+1)$ or $pq|p+q+1$, a contradiction since $pq>p+q+1>0$. If $q^2|p^2-p+1$ then $p^2q^2|(q+1)(p^2-p+1)$ or $pq|p^2-p+1+q$. Therefore $p^2-p+1+q \ge pq$ or $(p-1)(q-p) \le 1$, a contra diction since $q>p \ge 5$. Case 2. If $p^2|q+1$ and $q^2|p^3-1$. This follows $q^2|p-1$ or $q^2|p^2+p+1$. Since $p^2|q+1$ so $q \ge p^2-1$. This follows $q^2>p-1$ and $q^2 \ge (p^2-1)^2>p^2+p+1$. That means $q^2 \nmid p^3-1$. Case 3. If $p^2|q^2-q+1$ and $q^2|p^3+1$. Therefore $q^2|p+1$ or $q^2|p^2-p+1$. If $q^2|p+1$ then $p \ge q^2-1$. Hence $p^2 \ge (q^2-1)^2>q^2-q+1$, a contradiction since $p^2|q^2-q+1$. If $q^2|p^2-p+1$ then $q^2<p^2-p+1<p^2$ or $p>q$. But since $p^2|q^2-q+1$ then $q>p$, a contradiction. Case 4. If $p^2|q^2-q+1$ and $q^2|p^3-1$. It follows that $q^2|p-1$ or $q^2|p^2+p+1$. Since from $p^2|q^2-q+1$ we get $p<q$ so $q^2 \nmid p-1$. Hence $q^2|p^2+p+1$. Thus, we have $p^2<q^2-q+1$ and $q^2<p^2+p+1$. We obtain $p>q-2$. We also have $p<q$ so $p=q-1$. This follows $p=2,q=3$, a contradiction. Thus, the solution is $(p,q)=(2,3),(3,2)$. $\blacksquare$

Do you have the other Bulgarian problems?, if the case, can you post them?.

Is this problem harder than: "Let $n$-natural number, $p$-prime. Find all pairs $(n,p)$ such that $n^p+p^5$ is a square of an integer." ?

Obviously $(p,q)=(3,2)$ and $(2,3)$ are solutions.From now on we shall assume that $p,q>3$. $p^2 \mid q^3+1 \implies p^2 \mid q+1$ or $p^2 \mid q^2-q+1$(but not both). Similarly $q^2 \mid p^6-1 \implies q^2|p^3-1$ or $q^2|p^3+1$(since $q$ is odd).Thus we have $q^2 \mid p-1$ or $q^2 \mid p^2+p+1$ or $q^2 \mid p+1$ or $q^2 \mid p^2-p+1$. Thus we have 2*4=8 cases which are not hard to solve using inequality boundings.(Note that the smaller part of the inequality always has degree 4 while the larger part has degree less than 4)

borislav_mirchev wrote: Is this problem harder than: "Let $n$-natural number, $p$-prime. Find all pairs $(n,p)$ such that $n^p+p^5$ is a square of an integer." ? are you sure that this can be solved? it looks quite hard...for example if $ p=5, n=5a $ one has to solve $ a^{5}+1=5b^{2} $ which becomes $ a+1=c^{2}, a^{4}-a^{3}+a^{2}-a+1=5d^{2} $ (there is one more case but that can be easily solved)...?!...

This problem is trivial using lifting the exponent lemma. Solution: We claim that $(p,q) = \{2,3\}$ are the only solutions. Proof. Firstly, suppose $\text{gcd} (p,3) = 1$ and $\text{gcd} (q,6) =1$ i.e. $p \neq 3 $ and $q \neq 2,3$. Then, by lifting the exponent lemma, we have $\text{v}_p ( q^3+1) = \text{v}_p (q+1) \ge 2$. On the other hand, we also have : $\text{v}_q (p^6-1) = \text{v}_q (p-1) \ge 2 \implies $ $$ p^2 \mid q+1 ; q^2 \mid p+1 $$which is absurd. Thus our supposition was incorrect. Thus, we consider two cases: 1. $\text{gcd} ( p,3) \neq 1 \iff p=3$ This implies $9 \mid q^3+1$ and $q^2 \mid 728$. Now, $728 = 2^3\cdot 7 \cdot 13 \implies q =2$ is the only possibility. Hence $$ \boxed{ S_1 : (p,q) = (3,2)}\ \bullet$$ 2.$\text{gcd} (q,6) \neq 1 \iff q \in \{2,3\}$ The case for $q =2 $ is the same as the above case. Hence we consider $q = 3$. This implies $ p^2 \mid 28$ and $9 \mid p^6-1$. Since, $28 = 2^2 \cdot 7 \implies p =2$ is the only possibility and since $9 \mid 2^3+1$, we have: $$ \boxed{S_2 : (p,q) = (2,3)} \ \bullet$$

@above, LTE states that if $p\nmid a\wedge p\nmid b\wedge p| a + b$, then \[v_p(a^{2n+1} + b^{2n+1}) = v_p(a+b) + v_p(2n + 1).\]

I used the fact that : LTE wrote: for an odd positive integer $n$, if $\gcd(p,n)=1$, then $\text{v}_p (x^n+y^n) = \text{v}_p (x+y)$

Electron_Madnesss wrote: I used the fact that : LTE wrote: for an odd positive integer $n$, if $\gcd(p,n)=1$, then $\text{v}_p (x^n+y^n) = \text{v}_p (x+y)$ You still need $p\nmid x, p\nmid y$ and $p|x+y$ for that..

At first glance, it felt like the problem can be solved from first principles without resorting to any advanced results. This is my solution. Suppose $p = 2$. Then $q^2 | 2^6 - 1 \implies q = 3$. Suppose $q = 2$. Then $p^2 | 2^3 + 1 \implies p = 3$. Suppose $p \geq 3, q \geq 3$. It is clear that $p \neq q$. Suppose $q > p \implies q \geq p + 2$. $q^2 | p^6 - 1 \implies q^2 | (p-1)(p+1)(p^2 + p + 1)(p^2 - p +1) \implies q^2 | (p^2 + p + 1)(p^2 - p +1) \;(\because q \geq p + 2)$ Since $q^2 \geq (p + 2)^2 = p^2 + 4p + 4 > p^2 + p + 1 \implies q^2 \not | (p^2 + p + 1) \text{ and } q^2 \not | (p^2 - p + 1)$. The only possibility is $q | (p^2 + p + 1)$ and $q | (p^2 - p +1)$. Then $q | (p^2 + p + 1) - (p^2 - p +1) \implies q | 2p \Rightarrow \Leftarrow \;(\because q \text{ is odd and } q > p)$. Suppose $p > q \implies p \geq q + 2$. $p^2 | q^3 + 1 \implies p^2 | (q+1)(q^2 - q + 1) \implies p^2 | (q^2 - q +1) \;(\because p \geq q + 2)$ Since $p^2 \geq (q + 2)^2 = q^2 + 4q + 4 > q^2 - q + 1 \implies p^2 \not | q^2 - q + 1$. Hence, the only solutions are $(p, q) \in \{(2, 3), (3, 2)\}$.

The answer is $(p,q) = (2,3),(3,2)$. First we resolve the case $\min(p,q) < 5$: $q=2$. Then $p^2 \mid 9$, forcing $p=3$. $q=3$. Then $p^2 \mid 28$, forcing $p=2$. $p=2$. Then $q^2 \mid 63$, forcing $q = 3$, $p=3$. Then $q^2 \mid 728 = 8 \cdot 91$, forcing $q=2$. Now assume $p,q \ge 5$. We will show there are no solutions. FTSOC there is a solution. Claim 1: $q^2$ divides exactly one of $p-1,p+1,p^2 - p+ 1,p ^2 + p + 1$. Proof: Note $p^6 -1 = (p^3 - 1)(p^3 + 1) = (p-1)(p^2 + p + 1) (p+1)(p^2 - p + 1)$. Note $\gcd(p^3-1,p^3+1) \mid 2$, $\gcd(p-1,p^2 + p + 1) \mid 3$, $\gcd(p+1,p^2 - p + 1) \mid 3$. In particular, any number dividing some two of $p-1,p+1,p^2 - p + 1, p^2 + p + 1$ must divide $2 \cdot 3 = 6$. As $p \ge 5$ so we are done. $\square$ Claim 2: $p^2$ divides exactly one of $q+1,q^2 - q + 1$. Proof: Note $q^3 = (q+1)(q^2-q + 1)$. Observe $\gcd(q+1,q^2 - q + 1) \mid 3$. In particular, any number dividing both $q+1,q^2 - q + 1$ must divide $3$. As $q \ge 5$ so we are done. $\square$ Claim 1 gives $q \le p^2 + p +1 \implies q < p+1$. Hence $q \le p$. Claim 2 gives $p \le q^2 - q + 1 \implies p < q$. Hence $p \le q-1$. Thus we have a contradiction. $\blacksquare$

borislav_mirchev wrote: Is this problem harder than: "Let $n$-natural number, $p$-prime. Find all pairs $(n,p)$ such that $n^p+p^5$ is a square of an integer." ? Smart one

Here is my solution: https://calimath.org/pdf/BulgariaNMO2014-4.pdf And I uploaded the solution with motivation to: https://youtu.be/HSsvNDflK10

Assume for now that $p,q\neq 2,3$. Let us analyize $\mathrm{ord}_p(q)$. Note that $\mathrm{ord}_p(q)\mid 6$ but $\mathrm{ord}_p(q)\nmid 3$, so $\mathrm{ord}_p(q)=2,6$. \begin{itemize} \item If $\mathrm{ord}_p(q)=2$, then $p\mid (q+1)(q-1)$, so $p\mid q+1$ only, as $p\neq q$. In fact, this implies $p^2\mid q+1$. Looking at $\mathrm{ord}_q(p)$, we must have $\mathrm{ord}_q(p)\mid 6$. If $q^2\mid p^k-1$ with $k\le 3$, then \[p^2\le q+1\le \sqrt{p^k-1}+1\le \sqrt{p^3-1}+1\implies p^4\le p^3+2\sqrt{p^3-1}+1\]which is untrue for $p\ge 2$. Hence $\mathrm{ord}_q(p)=6$. Thus $q^2\mid p^3+1$. Again, As $p^2\le q+1$, we see that \[p^4\le q^2+1\le p^3+2\]which is untrue for $p\ge 2$. Hence there are no solutions in this case. \item Otherwise $\mathrm{ord}_p(q)=6$. Hence \[p\mid (q^6-1)=(q^3+1)(p^3-1)\implies p\mid q^3+1=(q+1)(q^2+q+1).\]If $p\mid q+1$, then again $p^2\mid q+1$, and we get the same case as before. Otherwise $p^2\mid q^2+q+1$. Then \[q^2\mid (p^3-1)(p^3+1).\]Thus, by the order condition, $q^2\mid p^3+1$. If $q^2\mid p+1$, then $p^2\le q^2+q+1\le p+1+\sqrt{p+1}+1$, which is untrue for $p>2$. Otherwise $p^2\mid q^2+q+1$ and $q^2\mid p^2-p+1$. If $2p^2\le q^2+q+1$, then $2p^2\le q^2+q+1\le (q+1)^2$ and thus \[2p^2\le q^2+2q+1\le p^2-p+1+2\sqrt{p^2-p+1}+1\]which is untrue for $p>2$. Hence $p^2=q^2+q+1$. Plugging this in gives $q^2\mid 3q$, which is impossible for $q>3$. \end{itemize} Thus $p,q\in\{2,3\}$. Among those, only $(p,q)=(2,3),(3,2)$ gives a solution.

The answers are $(p, q) = (2, 3) = (3, 2)$. Assume for now that $p, q \geq 5$. Then, note that the first condition implies there exists a multiple of $p^2$ in $\{q^2 - q + 1, q + 1\}$ for $\nu_p$ reasons. Similarly, there exists a multiple of $q^2$ in $\{p-1, p+1, p^2 - p + 1, p^2 + p + 1\}$. In particular, as $p \neq q$, suppose foremost that $p > q$. Then $p^2 > q^2 - q+1$, which is an obvious contradiction. If $p < q$, then $p^2 + p + 1 = q^2$ necessarily. But the LHS clearly is not a perfect square, contradiction. Thus, we can just check the cases where $p, q < 5$ and get the desired answer.

Answer: $(p, q) = (2, 3)$ or $(3, 2)$. If $\min(p, q) \le 3$, then one can check that the only solutions are $(2, 3)$ and $(3, 2)$. Thus we can assume $p, q > 3$. Since $p \mid q^3 + 1$, so $\text{ord}_{p}(q)$ equals $2$ or $6$. If $\text{ord}_p(q) = 2$, then we have $p^2 \mid q + 1$ (By LTE) and $2 \mid q+1$, so $2p^2 \mid q+1$. Hence $p^2 < 2p^2 - 1 \le q$. Note that $\text{ord}_q(p) \mid 6$. If $\text{ord}_q(p) < 6$, then by LTE, we get $p^4 < q^2 \mid p^{\text{ord}_q(p)} - 1 \le p^3 - 1$, a contradiction. Hence $\text{ord}_q(p) = 6$, so $p^4 < q^2 \mid p^3 + 1$, a contradiction. Now assume $\text{ord}_p(q) = 6$. Then we have $p \nmid q + 1$, so $p^2 \mid q^2 - q + 1 < q^2$. If $\text{ord}_q(p) \le 2$, then by LTE, we have $p^2 < q^2 \mid p^{\text{ord}_q(p)} - 1 \le p^2 - 1$, a contradiction. Therefore $\text{ord}_q(p)$ equals $3$ or $6$. If $\text{ord}_q(p) = 3$, then we have $q \nmid p+1$, so $q^2 \mid p^2 + p + 1$. Note that $p^2 + p + 1 < 2p^2 < 2q^2$, hence $p^2 + p + 1 = q^2$, but $(p+1)^2 > p^2 + p + 1 = q^2 > p^2$, thus we get a contradiction. Hence the only possibility is $\text{ord}_q(p) = 6$, which means $q^2 \mid p^3 + 1$ and since $q \nmid p+1$, so $p^2 < q^2 \mid p^2 - p + 1$, a contradiction. Thus there are no solutions if $p, q > 3$. $\blacksquare$

We claim that the solution $(p,q)=(2,3), (3,2)$. Suppose $p=2$. Then, $q^2\mid 63\Longrightarrow q=2$. Suppose $p=3$. Then, $q^2\mid 728\Longrightarrow q=2$. Suppose $q=2$. Then, $p^2\mid 9\Longrightarrow p=3$. Suppose $q=3$. Then, $p^2\mid 28\Longrightarrow p=2$. Now take $p,q>3$. Note that $p^2\mid (q+1)(q^2-q+1)$. Now, $\gcd(q+1,q^2-q+1)=\gcd(q+1,3q)=1$ as $q>2$. Hence, either $p^2\mid q+1$ or $p^2\mid q^2-q+1$. In either case $p<q$. Note that since $q^2$ is odd, we have either $q^2\mid p^3-1$ or $q^2\mid p^3+1$ However if $q^2\mid p^3+1$ then $q<p$, which is a contradiction. So, $q^2\mid p^3-1=(p-1)(p^2+p+1)$. Since $q>p$, we have $q^2\mid p^2+p+1$. This gives $q^2\leq p^2+p+1\leq p^2+2p+1=(p+1)^2\Longrightarrow q\leq p+1$. Since $q>p$, we have $q=p+1$. However, this forces $p=2$, which is a contradiction. $\blacksquare$

Please contact westskigamer@gmail.com if there is an error with my solution for cash bounties by 3/18/2025.