Solve for $x$ in $x^2 +2x +1\equiv 2 \pmod{13}$
I started with $2^{12}\equiv 1 \pmod{13}$ by Fermat's Little Theorem. I found no square root of $2$ from $(x+1)^2\equiv 2 \pmod{13}$ using a table. How do you use show that $(2^{12})(2)\equiv 2 \pmod{13}$ has no solution without making a table?
On
The following solution is specific to this problem and not usable in general when finding whether $2$ is a quadratic residue mod a prime.
For contradiction, assume it is possible for the congruence to hold. Then:
$(x+1)^2\equiv 2\stackrel{6}\implies (x+1)^{12}\equiv 2^6\equiv 64\equiv -1\pmod{\! 13}$
Clearly $x+1\not\equiv 0\pmod{\! 13}$, so Fermat's little theorem gives us a contradiction.
In case it is not clear, we raised both sides by $6$. In general:
For $n\in\Bbb Z_{\ge 1}$ we have $\,a\equiv b\implies a^n\equiv b^n\pmod{\! p}$,
because $a^n-b^n=(a-b)\left(a^{n-1}+a^{n-2}b+\cdots+ab^{n-2}+b^{n-1}\right)$.
$\left(\frac{a}{p}\right)$ denotes Legendre symbol (for odd primes $p$).
$$\left(\frac{a}{p}\right)=\begin{cases}1,&& x^2\equiv a\not\equiv 0\pmod{\! p}\, \text{ is solvable}\\ 0, && 0\equiv a\pmod{\! p}\\ -1,&& x^2\equiv a\pmod{\! p}\, \text{ is unsolvable}\end{cases}$$
A supplementary law of quadratic reciprocity (simple proof here) claims:
$(x+1)^2\equiv 2\pmod{\! 13}$ is unsolvable, because $\left(\frac{2}{13}\right)=-1$ (since $13\not\equiv \pm 1\pmod{\! 8}$).
You don't need to use Quadratic reciprocity here though: none of $0^2,1^2,2^2,\ldots,6^2$ is equivalent to $2$ mod $13$, so $2$ is not a quadratic residue mod $13$ and no solutions can exist (remember $(-y)^2\equiv y^2\pmod{\! p}$, so you don't need to check any of $7^2,8^2,\ldots, 12^2$).