Quick! Prove that $3^{15}+37$ is a square. CONTEXT: I have been studying the odd powers of $3$ and trying to determine when they are "close to" square numbers; more specifically, I have conjectured that there exist finitely many solutions $m,n$ to the diophantine equation
$$|3^{2m+1}-n^2|<m^2$$
and some examples of solutions include $3^7+22=47^2$, $3^{11}+94=421^2$, and $3^{15}+37=3788^2$. Then it occurred to me that coming up with any of these solutions would take a huge amount of time if I had no calculator.
QUESTION: How could one show by hand in a short amount of time (say, $5$ minutes of calculation at most) that $3^{15}+37$ is a perfect square? Ideally, one would find its square root, but perhaps there is some way to demonstrate its square-ness without doing this? I imagine that any quick way of doing this would rely on some sort of factoring trick, but I haven't been able to come up with one.
 A: Here is some more detail on the technique being used in Batominovski's answer. Suppose $3^{15} + 37 = a^2$ for some integer $a$. Writing $b = 3^7$, this gives
$$a^2 - 3b^2 = 37$$
which is a Pell-type equation, and it's possible to explicitly describe all solutions to it and then just check whether any of them happen to satisfy $b = 3^7$. They grow exponentially quickly so this is a fairly short finite search. 
The equation can equivalently be written as a norm equation
$$N(a + \sqrt{3} b) = 37$$
and its smallest solution is $a = 7, b = 2$. We can find other solutions by multiplying $x = 7 + 2 \sqrt{3}$ by a unit of $\mathbb{Z}[\sqrt{3}]$ of norm $1$. The group of such units is cyclic with generator $y = 2 + \sqrt{3}$, the fundamental unit (see e.g. these notes), and hence we can find solutions to $N(a + b \sqrt{3}) = 37$ by repeatedly multiplying by $y$ and $y^{-1} = 2 - \sqrt{3}$ as follows:
$$x = 7 + 2 \sqrt{3}$$
$$xy = 20 + 11 \sqrt{3}$$
$$xy^{-1} = 8 - 3 \sqrt{3}$$
$$xy^2 = 73 + 42 \sqrt{3}$$
$$xy^{-2} = 25 - 14 \sqrt{3}$$
$$xy^3 = 272 + 157 \sqrt{3}$$
$$xy^{-3} = 92 - 53 \sqrt{3}$$
$$xy^4 = 1015 + 586 \sqrt{3}$$
$$xy^{-4} = 343 - 198 \sqrt{3}$$
$$xy^5 = 3788 + 2187 \sqrt{3}$$
and at this point we're done, because $2187 = 3^7$. If we had kept going until the values of $b$ got larger than $2187$, then we would have stopped and concluded that $3^{15} + 37$ is not a square. 
There's a remaining question of whether this process was guaranteed to generate all solutions. We have $37 = (7 + 2 \sqrt{3})(7 - 2 \sqrt{3})$, and $7 \pm 2 \sqrt{3}$ both have prime norms, and hence are prime. $\mathbb{Z}[\sqrt{3}]$ is a UFD, so these are the only elements of norm $37$, up to units; equivalently, every element of norm $37$ is $7 \pm 2 \sqrt{3}$ times a unit, so the procedure above generates all solutions up to sign. 
Unfortunately this technique is of no help in finding the identity. It does correctly suggest that such identities should be rare. 

Here's an approach for finding the identity, although maybe still not by pen and paper. If $3^{2n+1}$ is close to a square then $3^n \sqrt{3}$ is close to an integer, so you've not only found a good rational approximation to $\sqrt{3}$ but one whose denominator is itself a power of $3$. You can search for these by computing $\sqrt{3}$ in base $3$ and looking for long stretches of $0$s or $2$s. This expansion begins
$$\sqrt{3} = 1.2012021222212 \dots_3$$
and that stretch of four $2$s implies that $3^7 \sqrt{3}$ is unusually close to an integer. That integer is $12012022_3 = 3788$ as expected. I did both of these calculations with WolframAlpha, though. 
A: This is more like a comment, but it is too long.  My answer is not actually a good way to show that $3^{15}+37$ is a perfect square.  You have to a priori know that it is a perfect square in order to proceed with this Pell-equation guess.  Moreover, the computation cannot be done in $5$ minutes or less (unless you are a savant).   
Note that $37=7^2-3\cdot 2^2$ and $1=2^2-3\cdot 1^2$.  Now, note that
$$(7+2\sqrt{3})\cdot(2+\sqrt{3})^5=3788+2187\sqrt{3}=3788+3^{\frac{15}{2}}\,.$$
Therefore,
$$(7-2\sqrt{3})\cdot(2-\sqrt{3})^5=3788-2187\sqrt{3}=3788-3^{\frac{15}{2}}\,.$$
Multiplying the two equations above yields
$$37=3788^2-3^{15}\,.$$
Therefore, $3^{15}+37=3788^2$ is the square of an integer. 
Due to Qiaochu Yuan's kind (deleted) remark, $\mathbb{Z}[\sqrt{3}]$ is a unique-factorization domain (which I faultily remembered that it was not).  If you started with a different minimal solution $(x,y)\in\mathbb{Z}_{>0}\times\mathbb{Z}_{>0}$ to the Pell equation $x^2-3y^2=37$, namely, $(x,y)=(8,3)$, then you could achieve the same proof:
$$(8+3\sqrt{3})\cdot(2+\sqrt{3})^{-6}=3788-2187\sqrt{3}=3788-3^{\frac{15}{2}}$$
and
$$(8-3\sqrt{3})\cdot(2-\sqrt{3})^{-6}=3788-2187\sqrt{3}=3788+3^{\frac{15}{2}}\,.$$
A: \begin{align}3^{15}+1&=(3^5+1)(3^{10}-3^5+1)=244(243\cdot242+1)=2^2\cdot7\cdot31\cdot61\cdot271\\&=(61\cdot62)(14\cdot271)=3782\cdot3794=3788^2-6^2\end{align} 
A: Checking that $3^{15}+37$ is (or is not) a square in $5$ minutes by hand is quite possible.   It helps to know that $3^6=729$, so you can write $3^{15}=27\cdot 729 \cdot 729=3\cdot 2187\cdot 2187$  Doing the multiply should not take a minute, then if you know how to take a square root by hand four minutes should suffice easily.  You can use this approach to find it as well-just compute $3^{15},$ take its square root, and when you get to the units place see how much you need to add to come out even.  I think the digit-by-digit method for square roots takes about twice as long as division for the same number of figures in the dividend, but for eight digits it won't take too long.
