Sounds like you're using the Niven textbook. I did this exercise last fall, and it gave be some trouble too. It is indeed proved by Gauss's lemma.
Just do a case-by-case proof that $\displaystyle x^2\equiv 2\pmod{p}$ has a solution given that $\displaystyle p\equiv 1$, then $\displaystyle p\equiv 3$, then $\displaystyle p\equiv 5$, and finally $\displaystyle p\equiv 7\pmod{8}$. Since those are the only possibilities (even numbers won't work), the conclusion will follow.
Consider
Gauss's lemma, and let $\displaystyle a=2$, and observe that each $\displaystyle i\in\{2,4,6,\cdots,p-1\}$ is its own least positive residue modulo $\displaystyle p$. Let $\displaystyle n$ denote the number of integers in the set
$\displaystyle \left\{\frac{p+1}{2},\frac{p+3}{2},\cdots,p-1\right\}$.
Then by Gauss's lemma, $\displaystyle \left(\frac{2}{p}\right)=(-1)^n$.