\[p^a+a^4=k^2\iff p^a=(k-a^2)(k+a^2)\]$i)p\geq 5,$ $k-a^2=p^x$ and $k+a^2=p^{a-x}$ \[2a^2=p^{a-x}-p^x=p^x(p^{a-2x}-1)\]$x=v_p(RHS)=2v_p(a). \ $Let $a=p^{\frac{x}{2}}b$ where $(p,b)=1$. \[2b^2+1=p^{a-2x}=p^{p^{\frac{x}{2}}b-2x}\]But \[2b^2+1=p^{p^{\frac{x}{2}}b-2x}\geq p^{5^{\frac{x}{2}}b-2x}\geq p^b\geq 5^b>2b^2+1\]Since $p\geq 5, \ 2b^2+1<5^b$ and $(5^{\frac{x}{2}}-1)b\geq 5^{\frac{x}{2}}-1\geq 2x$ which can be proved by induction.$\square$ $ii)p=3$ \[3^a=(k-a^2)(k+a^2)\]$k-a^2=3^x$ and $k+a^2=3^{a-x}$ \[2a^2=3^x(3^{a-2x}-1)\]Denote $a=3^{\frac{x}{2}}b$ We have \[2b^2+1=3^{3^{\frac{x}{2}}b-2x}\]If $b=1,$ then $3^{\frac{x}{2}}-2x=1$ which gives $x=0,4$ so we get $\boxed{(a,p)=(9,3),(1,3)}$. If $b=2,$ then $2.3^{\frac{x}{2}}-2x=2\iff 3^{\frac{x}{2}}-x=1\implies x=0,2$ Thus we get $\boxed{(a,p)=(6,3),(2,3)}$ Suppose that $b\geq 3$. \[3^b> b^2+1=3^{3^{\frac{x}{2}}b-2x}\implies 2x>b(3^{\frac{x}{2}}-1)\geq 3(3^{\frac{x}{2}}-1)\geq 6x\]Which is impossible.$\square$ $iii)p=2$ $k-a^2\neq 1$ Let $k-a^2=2^x, \ k+a^2=2^{a-x}$ \[2a^2=2^x(2^{a-2x}-1\iff a^2=2^{x-1}(2^{a-2x}-1)\]Let $x=2m+1$ and $a=2^mb$ \[b^2+1=2^{2^mb-4m-2}\]For $m=1$ we have $b^2+1=2^{2b-6}\underbrace{>}{\text{for} \ b\geq 6}b^2+1$ which gives no solution and for $m=2$ we have $b^2+1=2^{4b-10}\underbrace{>}{\text{for} \ b\geq 4}b^2+1$ which gives no solution again. If $m\geq 3,$ then $2^m>4m+2$ hence \[2^{b+1}\geq b^2+1=2^{2^mb-4m-2}>2^{(4m+2)(b-1)}\geq 2^{12(b-1)}\implies b+1\geq 12(b-1)\implies b=1\]Which gives a contradiction.$\blacksquare$

Answer: $p=3,a=1,2,6,9.$ Set $p^a+a^4=b^2,$ then $p^a=(b-a^2)(b+a^2).$ Then set $b-a^2=p^x,b+a^2=p^y$ where $x,y$ are nonnegative integers with $y>x$ and $x+y=a.$ We also get $2a^2=p^y-p^x$ so we are trying to solve $p^y-p^x=2(x+y)^2.$ First suppose $p=2.$ We get \[2^{y-x}-1=\frac{(x+y)^2}{2^{x-1}}.\]Then $\nu_2$ gives $x-1$ is even, so $\frac{(x+y)^2}{2^{x-1}}$ is a square and an integer. Thus we have $y-x=1$ by Mihailescu, so plugging this in we have $2^{x-1}=(2x+1)^2.$ Now the right side is odd, so $x=1$ which doesn't work. Thus there are no solutions in this case. Now if $p\ne 2,$ we have $p^x\cdot\frac{p^{y-x}-1}2=(x+y)^2.$ By $\nu_p$ we have $x$ even, so $p^x$ and $\frac{p^{y-x}-1}2$ are both squares. However, $\frac{p^{y-x}-1}2\equiv-\frac12\pmod p.$ Now it is well known that $-1$ is a QR $\pmod p$ iff $p\equiv 1\pmod 4,$ and $2$ is a QR $\pmod p$ iff $p\equiv 1,7\pmod 8.$ Thus $-\frac12$ is a QR iff $p\equiv 1,3\pmod 8.$ Thus $p\ne 5,7.$ Now if $p\ge 11,$ we have \[8y^2=2(y+y)^2>2(x+y)^2=p^y-p^x\ge p^y-p^{y-1}\ge10p^{y-1}>8p^{y-1},\]so $y^2>p^{y-1}.$ But for $y=1$ we have $y^2=p^{y-1},$ and $p^{y-1}$ grows faster than $y^2$ since $\frac{p^y}{p^{y-1}}\ge 11$ but $\frac{(y+1)^2}{y^2}\le\frac{(y+y)^2}{y^2}=4$ for $y\ge 1.$ Thus there are no solutions in this case. Now we consider $p=3.$ We have \[8y^2>2(x+y)^2=3^y-3^x\ge 3^y-3^{y-1}=2\cdot 3^{y-1},\]so $4y^2>3^{y-1}.$ This is true for $y=1,2,3,4,5$ but false for $y=6,$ and thus false for $y\ge 6$ since $\frac{(y+1)^2}{y^2}=\frac{y^2+2y+1}{y^2}<\frac{y^2+y^2+y^2}{y^2}=3$ for $y\ge 6,$ so the right side grows faster than the left. Thus we just have to check $y=1,2,3,4,5$ and $x<y.$ Checking, we get only $(y,x)=(1,0),(2,0),(4,2),(5,4)$ work. Using $a=x+y$ we get $a=1,2,6,9.$ These work, so we are done.

Time consuming, but great to exercise optimization strategies. Answer. $(p,a)$: $(3,1), (3,2)$, $(3,6)$, $(3,9)$. The equation $p^a + a^4 = m^2$ is equivalent to $p^a = (m - a^2)(m + a^2)$, hence (as $p$ is prime) $m-a^2 = p^x$ and $m + a^2 = p^{a-x}$ for some $0 \leq x < \frac{a}{2}$. Thus $2a^2 = p^{a-x} - p^x$. In the right-hand side the first time decreases as $x$ increases, while the second term increases, hence \[ 2a^2 \geq p^{a - \left \lfloor \frac{a-1}{2} \right\rfloor} - p^{\left \lfloor \frac{a-1}{2} \right\rfloor} = p^{\left \lfloor \frac{a-1}{2} \right\rfloor}(p^{a - 2\left \lfloor \frac{a-1}{2} \right\rfloor} - 1). \] If $a=1$, then in $2a^2 = p^{a-x} - p^x$ we can have only $x=0$, so $p=3$. If $a=2$, then again $x=0$ and $8 = p^2 - 1$ yield $p=3$. Suppose $a\geq 3$ and $p\geq 5$. In the above inequality the right-hand side is at least $p^{\left \lfloor \frac{a-1}{2} \right\rfloor}(p-1) \geq 5^{\left \lfloor \frac{a-1}{2} \right\rfloor} \cdot 4$, so necessarily $a^2 \geq 2 \cdot 5^{\frac{a-1}{2}}$. This is false for $a=3$ (direct check) and for $a\geq 5$ by induction: the base case is checked directly, and if $5^{\frac{a-1}{2}} > \frac{a^2}{2}$, then multiplying with $5 > \frac{(a+1)^2}{a^2}$ (the right-hand side is indeed not more than $\left(1 + \frac{1}{a}\right)^2 \leq \left(\frac{6}{5}\right)^2 < 2$) we obtain what we want. If $a=4$ in $2a^2 = p^{a-x} - p^x$ we have $2^5 = p^{4-x} - p^x$ and $0\leq x < 2$, but none of $x=0$ and $x=1$ yields a solution (in the first case $p^4 = 33$, in the second one $p$ divides the right-hand side, so $p=2$ which does not work). Now let $p=3$ and $a\geq 3$. In $2a^2 = p^{a-x} - p^x$ if $x=0$, then $2a^2 = 3^a - 1$, impossible since the right-hand side is larger by induction. If $x\geq 1$, then $3$ divides $2a^2$ and so $a$ is divisible by $3$. For $a=3$ the main expression is $3^3 + 3^4 = 108$, for $a=6$ is $3^6 + 6^4 = 45^2$, for $a=9$ it is $3^9 + 9^4 = 3^9 + 3^8 = 3^8 \cdot 4 = 162^2$. For $a\geq 12$ in the main inequality the right-hand side is at least $p^{\left \lfloor \frac{a-1}{2} \right\rfloor}(p-1) \geq 2 \cdot 3^{\frac{a-1}{2}}$, but actually $3^{\frac{a-1}{2}} > a^2$ by induction for $a\geq 11$ (for $a=11$ we have $243 > 121$ and the step follows by $3 > \left(1+\frac{1}{a}\right)^2$). It remains to consider $p=2$ and $a\geq 3$. In the main inequality the right-hand side is at least $2^{\frac{a-1}{2}}$, so $a^2 \geq 2^{\frac{a-3}{2}}$, false for $a\geq 21$ (by induction, since $512 > 441$ and $2 > \left(1 + \frac{1}{a}\right)^2$). For $a=1,2,\ldots,20$ the expression $2^a + a^4$ equals $3 \in (1^2, 2^2)$, $20 \in (4^2, 5^2)$, $89 \in (9^2, 10^2)$, $272 \in (16^2, 17^2)$, $657 \in (25^2, 26^2)$, $1360 \in (36^2, 37^2)$, $2529 \in (50^2, 51^2)$, $2^8 + 2^{12} = 2^8 \cdot 17$, $7073 \in (84^2, 85^2)$, $11024 \in (104^2, 105^2)$, $16689 \in (129^2, 130^2)$, $2^{12} + 12^4 = 2^{8}(16 + 81) = 2^8 \cdot 97$, $2^{13} + 13^4$ ends at $3$, impossible for a square; $2^{14} + 14^4 = 2^4(1024 + 2401) = 2^4 \cdot 5^2 \cdot 137$ and $137 \in (11^2, 12^2)$ is not a square; $2^{15} + 15^4$ ends at $3$, impossible for a square; $2^{16} + 16^4 = 2^{17}$ and is not a square; $2^{17} + 17^4$ ends at $3$, impossible for a square; $2^{18} + 18^4 = 2^4 \cdot 22945$, the second multiplier is divisible by $5$, but not by $25$; $2^{19} + 19^4 = 654609$ is divisible by $3$, but not by $9$; $2^{20} + 20^4 = 2^8(2^{12} + 5^4) = 2^8 \cdot 4721$, where $4721 \in (68^2, 69^2)$ is not a square. Therefore there is no solution for $a=2$.

Rewrite $p^a+a^4=x^2$ by factoring out $p^a = (x-a^2)(x+a^2)$. The second bracket is strictly positive, so the first one must be as well. We now consider several cases for $x - a^2$: $x - a^2 = 1$. Then $x = a^2+1\Longrightarrow p^a = 2a^2 + 1$. The right-hand side is odd, so $p \geq 3$. Now $p^a \geq 3^a > 2a^2 + 1$ for $a>2$ (by induction, or taking the derivative of $f(a) = 3^a - 2a^2 - 1$, etc.), and $a=1, 2$ lead to the solutions $(a,p) = (1,3), (2,3)$. $x - a^2 > 1$ and $p > 2$. Then $p\mid x-a^2$ and $p\mid x+a^2$, so $p\mid 2x$ and $p\mid 2a^2$. As $p>2$, these imply $p\mid x$ and $p\mid a$. Now if $\nu_p(x) = X$ and $\nu_p(a) = A$, and $x = x_1p^{X}$, $a = a_1p^{A}$, then we can write the initial equation as: \[p^{a_1p^{A}} + a_1^4 p^{4A} = x_1^2 p^{2X}.\]As $\nu_p(x^2) = 2X$ is even, so must be $\nu_p(p^{a_1p^A}+a_1^4p^{4A}$. However, if we assume that we don't just have $a_1p^{A} > 4A$, then $a_1 = 1$, $p = 3$, and $A = 1$, at which point $\nu_p(p^a+a^4 = 3$, which is odd, contradiction. Therefore, $a_1p^A > 4A$ and so \[4A = \nu_p(p^a+a^4) = \nu_p(x^2) = 2X \Longrightarrow X = 2A.\]Dividing both sides by $p^{4A}$ leaves $p^{a_1p^{A} - 4A} = (x_1 - a_1^2)(x_1 + a_1^2)$. Now if $p\mid x_1-a_1^2$, then $p\mid x_1+a_1^2$ as well, so $p\mid a_1$ and $p\mid x_1$, contradiction with the assumption that $\nu_p(x) = X$ and $\nu_p(a) = A$ from before. Hence $x_1 - a_1^2 = 1$ and so \[p^{a_1p^{A} - 4A} = 2a_1^2+1.\]If $a_1>2$, then $p^{a_1p^{A} - 4A} \geq p^{3a_1-4} \geq 3^{3a_1-4} \geq 2a_1^2+1$. Checking $a_1 = 1, 2$ leads to the solutions $(a,p) = (9,3)$ and $(a,p) = (6,3)$, respectively. $x-a^2 > 1$ and $p = 2$. Here $x-a^2 = 2^y$ and $x+a^2 = 2^z$ for some positive integers $y<z$, and so $2^z - 2^y = 2a^2\Longrightarrow 2^{z-1} - 2^{y-1} = a^2$. Diving by $4$ until we can, we must get to $2^{z-y} - 1 = \alpha^2$ for some $\alpha \in\mathbb{N}$. However, $2^{z-y} - 1 \equiv 3\not\equiv \alpha^2 \pmod 4$ for $z>y+1$, so we must have $z = y+1$. This leads to $x+a^2 = 2(x-a^2)$, or $x = 3a^2$. Plugging this into the original equation gives $2^{a} + a^4 = 9a^4$, so $2^a = 8a^4$. At this point, $a$ is some power of two, say $a = 2^b$, but $2^a = 8a^4 \Longrightarrow 2^b = 4b+3$, which is impossible due to modulo $4$ issues again. Thus, there are no solutions in this case, and we're done. In conclusion, all solutions are $(a,p) = (1,3), (2,3), (6,3), (9,3)$.

Let $(a, p)$ be a pair of integers satisfying the equation $ p^a + a^4 = k^2 $ for some integer $ k $. Then we have: \[ p^a = (k - a^2)(k + a^2) = p^m \cdot p^{a-m} \]where $ k - a^2 = p^m $, $ k + a^2 = p^{a-m} $, and $ m $ is a non-negative integer. Subtracting these two equations gives: \[ p^{a-m} - p^m = 2a^2 \] This simplifies further to: \[ p^m(p^{a-2m} - 1) = 2a^2 \] It is clear that $ p \neq 2 $ and $ p \nmid \frac{p^{a-2m} - 1}{2} = \frac{a^2}{p^m} $, leading to $ v_p(a^2) - v_p(p^m) = 0 $, implying $ 2v_p(a) = m $. Therefore, $ m = 2b $ and $ a = c \cdot p^b $ for some positive integer $ c $ and non-negative integer $ b $. Hence, \[ \frac{p^{a-2m} - 1}{2} = c^2 = \frac{p^{c \cdot p^b - 4b} - 1}{2} \] Since $ p \neq 2 $, we have $ p \geqslant 3 $. Considering $ b $ as an integer, the inequality $ 3^b - 1 \geqslant 4b - 2 $ is always true. Furthermore, since $ p \geqslant 3 $, we have $ p^b - 1 \geqslant 3^b - 1 \geqslant 4b - 2 $, which results in: \[ c \geqslant 1 \geqslant \frac{4b - 1}{p^b - 1} \implies cp^b - c \geqslant 4b - 1 \implies cp^b - 4b \geqslant c - 1 \] Next, using the increasing nature of the function $ f(x) = p^x $, we obtain: \[ \frac{1}{2}(p^{cp^b - 4b} - 1) \geqslant \frac{1}{2}(p^{c - 1} - 1) \implies c^2 \geqslant \frac{1}{2}(p^{c - 1} - 1) \geqslant \frac{1}{2}(3^{c - 1} - 1) \] Upon further observation, if $ c \geqslant 5 $, the inequality $ c^2 < \frac{1}{2}(3^{c - 1} - 1) $ holds true. In conclusion, the possible values for $ c $ are in the range $ 1 \leqslant c \leqslant 4 $. Let's consider each case: $\bullet$ If $ c = 1 $, then $ 2 = p^{p^b - 4b} - 1 $, which implies $ p = 3 $ and $ p^b - 4b = 1 $. Thus, $ b = 2 $ or $ b = 0 $. If $ b = 2 $, then $ a = 9 $, satisfying $ p^a + a^4 = 3^9 + 9^4 = 162^2 $, a perfect square. If $ b = 0 $, then $ a = 1 $, satisfying $ p^a + a^4 = 3^1 + 1^4 = 2^2 $, also a perfect square. $\bullet$ If $ c = 2 $, then $ 8 = p^{2p^b - 4b} - 1 $, implying $ p = 3 $ and $ 2p^b - 4b = 2 $. Thus, $ b = 0 $ or $ b = 1 $. If $ b = 0 $, then $ a = 2 $, satisfying $ p^a + a^4 = 3^2 + 2^4 = 5^2 $, a perfect square. If $ b = 1 $, then $ a = 6 $, satisfying $ p^a + a^4 = 3^6 + 6^4 = 45^2 $, also a perfect square. $\bullet$ If $ c = 3 $, then $ 18 = p^{3p^b - 4b} - 1 $ leads to no integer solutions. $\bullet$ If $ c = 4 $, then $ 32 = p^{4p^b - 4b} - 1 $ results in $ 33 = p^{4p^b - 4b} $, but $ 33 $ is not a power of any prime number, hence no solutions exist in this case. Therefore, the valid pairs $ (a, p) $ that satisfy all conditions are $ \boxed{(1, 3), (2, 3), (6, 3), (9, 3)} $. Each pair has been verified to meet all criteria.

the only correctly placed problem on the n shortlist is hard for the wrong reasons

This problem was proposed by Tahjib Hossain Khan, Bangladesh.

We claim the only solutions are $(1,3), (2,3), (6,3), (9,3)$. Let $p^a + a^4 = x^2$ so we have that \[p^a = (x-a^2)(x+a^2) \implies x-a^2 = p^k, x+a^2 = p^{a-k} \implies a^2 = \frac{p^{a-k} - p^k}2.\] If $a = 1$, we get the only solution is $(1,3)$. We will proceed with casework. Case 1: $p \ge 5$. In this case, we get that $\nu_p(x) = 2\nu_p(a) = 2r$ where $2r \ge k-1$. If $r = 0$, we have $a^2 \ge \frac{p^{a-1} - p}{2} \ge 2p^{a-2}$ unless $a = 1$ or $a=2$ which we verify to not work. We have that $$\frac{p^{a-k}-p^k}{2} \ge 2p^{a-k-1} \ge \frac{2p^{a-2}}{a^2} > a^2$$where the last inequality holds unless $a = 5$ and $p = 5$, but the remaining case can be checked to fail. So there are no solutions here. Case 2: $p = 3$. Here, we have that $\nu_p(x) = 2\nu_p(a) = 2r, 2r\ge k - 1$ unless $r=1$ and $a = 3$ but this does not result in a solution. So we get that $$a^2 = \frac{p^{a-k}-p^k}{2} \ge p^{a-k-1} \ge \frac{p^{a-2}}{a^2}.$$This reduces to a case check for $a < 10$ which results in solutions $(2,3), (6,3), (9,3)$. Case 3: $p = 2$. Here, we have that if $k = 0$, then $2^a = 2a^2 + 1$ which clearly has no solutions. So we can get that $a^2 = 2^{k-1}(2^{a-2k}-1)$ so $k$ is odd. Let $k = 2l + 1$ and $a = 2^lq$, we get that $q^2 \equiv 3\pmod 4$ unless $a = 2k$ or $a = 2k+1$. But these cases give no solution as the first implies $a = 0$ and the second means $k = 1$ and this does not give a solution. Having exhausted all cases, we can conclude that the solutions we initially listed are the only ones.

The pairs are $\boxed{(1,3),(2,3),(6,3),(9,3)}$. Let $k$ be a positive integer such that $$p^a+a^4=(a^2+k)^2\iff p^a=k(2a^2+k)$$ We quickly resolve the case $p=2$. We can set $k=2^{k'}$ giving $2^{a-k'}=2a^2+2^{k'}$. We thus must have $2a^2=2^{k'}$ or $a=2^{\frac{k'-1}{2}}$. Thus we must have $2^{\frac{k'-1}{2}}=2k'+1$. Checking $k'\leq 10$ gives no solutions and one can finish with induction showing the LHS is larger. Now set $k=p^{2k'}$ and we must have $a=a'p^{k'}$ for an non-negative $k'$. The case $a'=k'=1$ clearly gives no solutions. Then we must have $$p^{a'p^{k'}-4k'}=2{a'}^2+1$$Notice that for $(a',k')\neq (1,1)$ we have $a'p^{k'}-4k'\geq a'3^{k'}-4k'\geq a'$. Thus we must have $3^{a'}\leq p^{a'}\leq 2{a'}^2+1$. Thus we must have either $a'=1$ or $a'=2$ and $p=3$. If $a'=1$ the equality simplifies to $3^{3^{k'}-4k'}=3$ so we must have $3^{k'}=4k'+1$ which has solutions at $k'=0$ and $k'=2$ giving $(a,p)$ as $(1,3)$ and $(9,3)$. If $a'=2$ the equality simplifies to $3^{2\cdot 3^{k'}-4k'}=9$ so we must have $3^{k'}=2k'+1$ which has solutions at $k'=0$ and $k'=1$ giving $(a,p)$ as $(2,3)$ and $(6,3)$.

Let $p^a + a^4 = k^2$. We have $(k - a^2)(k + a^2) = p^a$> If $k - a^2 = 1$, then $2a^2 + 1 = p^a$. We have that $p^a \geq 2^a > 2a^2 + 1$, for $a = 7$. Say $2^a > 2a^2 + 1$ for $a = \{7, \dots, k\}$. Then, $2^k > 2k^2 + 1$, and $2^{k + 1} = 2 \cdot 2^k > 4k^2 + 2 > 2(k + 1)^2 + 1$, so $2^a > 2a^2 + 1$ for $a \geq 7$, now we simply have to check $a = 1, 2, \dots 6$, which yield $(1, 3), (2, 3)$ as solutions. Now, assume \( k - a^2 \neq 1 \). Then \( p \mid k - a^2, p \mid k + a^2 \implies p \mid a, k \). Let \( k = p^{\alpha}x \) and \( a^2 = p^{2\beta}y \), where \( p \nmid x, y \). Let: \[ k - a^2 = p^{\gamma}, \quad k + a^2 = p^{a - \gamma} \]First, note that $a > 2\gamma$. We have $p^{\alpha}x + p^{2\beta}y = p^{a - \gamma}$, and WLOG $\alpha \geq 2\beta$ which gives $p^{2\beta}(p^{\alpha - 2\beta}x + y) = p^{a - \gamma}$. If $\alpha \neq 2\beta$, then $p \nmid p^{\alpha - 2\beta}x + y$ since $p \nmid y$, a contradiction (as it's not equal to 1). Therefore $v_p(k) = v_p(a^2)$, and $\alpha = 2\beta$. So, we have $p^{2\beta}(x - y) = p^{\gamma}, p^{2\beta}(x + y) = p^{a - \gamma}$. Note that $x + y \neq 1$, so $p \mid x + y$. If $x - y \neq 1$, then $p \mid x - y$ as well which yields $p \mid x, y$ a contradiction therefore $x - y = 1$, resulting in $p^{2\beta} = p^{\gamma}$, and $2y + 1 = p^{a - 2\gamma}$, and since $2y + 1 = \frac{2a^2}{p^{\gamma}} + 1$, we have $2a^2 = p^{a - \gamma} - p^{\gamma}$. Since $a > 2\gamma$, $\gamma \leq \frac{a - 1}{2}$, and therefore $p^{a - \gamma} - p^{\gamma} \geq p^{\frac{a + 1}{2}} - p^{\frac{a - 1}{2}} = p^{\frac{a - 1}{2}}(p - 1)$. Claim: $p^{\frac{a - 1}{2}}(p - 1) > 2a^2$ for odd primes and $a \geq 11$. If we prove $3^{\frac{a - 1}{2}}\cdot 2 > 2a^2$, we would be done. Note that for $a = 11$, $3^5 \cdot 2 = 486 > 242$, so say we are done for $a = \{11, \dots, k\}$. Then, $2 \cdot 3^{\frac{k}{2}} = \sqrt{3} \cdot 3^{\frac{a - 1}{2}} \cdot 2 > 2\sqrt{3}k^2 > 2(k + 1)^2$, since $2\sqrt{3} > 3$, and $k^2 > 5k > 4k + 1$. Therefore, we are simply reduced to a case check from $a = 1, 2, \dots 11$. Keep in mind that $p \mid a$ and we are only considering $p$ odd at the moment, so for $a = 10, p = 5, 10^{4} + 5^{10} \equiv 2\mod{3}$, not possible. For $a = 9, p = 3$, which gives $9^4 + 3^9 = 162^2$, which works. For $a = 8$, no odd primes divide it. For $a = 7$, $p = 7$ and this fails. For $a = 6, p = 3$ and $6^4 + 3^6 = 45^2$, so this works. For $a = 5, p = 5$, and this fails. For $a = 4$, no odd primes divide it. For $a = 3$, we fail. So, we have the solutions $(9, 3), (6, 3)$ as well. Now, consider $p = 2$. We have $2a^2 = 2^{a - \gamma} - 2^{\gamma} \implies a^2 = 2^{\gamma - 1}(2^{a - 2\gamma} - 1)$. Since $2 \nmid 2^{a - 2\gamma} - 1$, we have $v_2(a^2) = \gamma - 1$, which means $2^{\gamma - 1}$ is a perfect square therefore $2^{a - 2\gamma} - 1$ is a perfect square as well. However, this is not possible if $a \geq 2\gamma + 2$, as then $2^{a - 2\gamma} - 1 \equiv 3\mod{4}$, so $a = 2\gamma + 1$, which gives $(2\gamma + 1)^2 = 2^{\gamma - 1}$, impossible by parity (clearly $\gamma \neq 1$). So, we are done and our solutions are $\boxed{(1, 3), (2, 3), (6, 3), (9, 3)}$.

Wow okay I hate this problem. We want to solve $p^a + a^4 = n^2$, or $p^a = (n - a^2)(n + a^2)$. Let $p^\alpha = n - a^2$ and $p^\beta = n + a^2$, since $a > 0$, $\alpha < \beta$. We first eliminate the case $p = 2$. Then, $2^{\alpha - 1}(2^{\beta - \alpha} - 1) = a^2$, $2^{\beta - \alpha} - 1$ is a perfect square, so $\beta - \alpha = 1$, by taking modulo $4$. Therefore, $2(n - a^2) = n + a^2$, which gives $n = 3a^2$, or $2^a = 8a^2$, which clearly has no solutions. Now suppose $p > 2$. Then \[p^\beta - p^\alpha = 2a^2 \ge (p - 1)p^{\frac{a - 1}{2}}.\]Now we proceed with a massive cases bash: $p = 3$: then $a \le 9$. If $a = 1$, $3^1 + 1^4 = 3^2$ works. If $a = 2$, $3^2 + 2^4 = 5^2$ works. If $a = 3$, $3^3 + 3^4 = 108$ fails. If $a = 4$, $3^4 + 4^4 \equiv 2 \pmod 5$ fails. If $a = 5$, $3^5 + 5^4 = 2^2 \cdot 7 \cdot 31$ fails. If $a = 6$, $3^6 + 6^4 = 45^2$ works. If $a = 7$, $3^7 + 7^4 \equiv 12 \pmod{16}$ fails. If $a = 8$, $3^8 + 8^4 \equiv 3 \pmod 7$ fails. If $a = 9$, $3^9 + 9^4 = (2 \cdot 3^4)^2$ works. $p = 5$: then $a \le 4$. If $a = 1$, $5^1 + 1^4 = 6$ fails. If $a = 2$, $5^2 + 2^4 = 41$ fails. If $a = 3$, $5^3 + 3^4 = 206$ fails. If $a = 4$, $5^4 + 4^4 = 881$ fails. $p \ge 7$: All $a$ fail.

Write the equation as $p^a+a^4 = k^2$, or $p^a = (k-a^2)(k+a^2)$. So both factors are powers of $p$, i.e. \[2a^2 = p^r - p^{a-r} \geq \begin{cases} p^{a/2 + 1} - p^{a/2 - 1} = p^{a/2 - 1} (p^2-1) & \text{$a$ even} \\ p^{(a+1)/2} - p^{(a-1)/2} = p^{(a-1)/2} (p-1) & \text{$a$ odd} \end{cases}\]Okay, now time for the bash. Even Case: If $p = 2$, the inequality holds only for $a \leq 20$, and no cases yield valid solutions. If $p = 3$, check $a \leq 6$, which yields $a = 2$ and $a = 6$. If $p \geq 5$, no values of $a$ work. Odd Case: For $p = 2$, check $a \leq 23$; for $p = 3$, check $a \leq 12$, yielding $a = 1$ and $a = 9$; for $p = 5$, check $a \leq 6$; for $p \geq 7$ we have $a \leq 4$ which clearly will not yield any solutions. Thus we have $(1, 3)$, $(2, 3)$, $(6, 3)$, $(9, 3)$ in total.

Junior vibes but time consuming