Exercise about primes in the ring of Gaussian integers

For the first part, I understand that you are using the supplementary laws of quadratic reciprocity, and of course, the result is immediate. However, you can also solve the problem without that theorem. With the same notation as in your statement:

$\mathbb{F}_p^*$ is cyclic, so there exists $x \in \mathbb{Z}$ such that $\bar{x}$ has order $p-1=4n$ in $\mathbb{F}_p^*$. Hence, $$(\bar{x}^{2n})^2=\bar{x}^{4n}=\bar{1}.$$ Due to the order of $\bar{x}$, it follows that $\bar{x}^{2n}=-\bar{1}$. Thus, if we choose $y:=x^n$, we get that $$y^2 \equiv -1 \mod p;$$ ie, $$\left(\frac{-1}{p}\right)=1.$$

The second part is also correct, but when you reach to $p(m+ni)=x\pm i$, I would just say that $pn=\pm 1$, so $p \mid 1$; contradiction.

Yes, it's correct, though I'd like to unpack it a little, and work it out with a specific prime.

Since $p > 2$, we have $$\left(\frac{-1}{p}\right) = 1$$ if and only if $$(-1)^{\frac{p - 1}{2}} \equiv 1 \pmod p$$ if and only $(-1)^{2n} \equiv 1 \pmod p$, which is true.

So far so good. The wording is a bit clunky, but I should be able to just get past that.

Now suppose $p$ is prime in $\mathbb Z[i]$, which means that there exists $x \in \mathbb{Z}$ such that $-1 \equiv x^2 \pmod p$,

I'm sorry, I'm not liking your style of writing congruences at all. I left it alone when I edited your question, but now that I'm quoting you in my answer I really have to change it to something I like better.

I'm also having a bit of a problem with $-1 \equiv x^2 \pmod p$, I'd much rather write $x^2 \equiv -1 \pmod p$ even though it means the very same thing.

Maybe it's because it really obscures the meaning of $x^2 \equiv -1 \pmod p$. And that meaning is that the equation $x^2 = kp - 1$ has solutions in integers.

from which $p \mid (x^2 + 1) = (x - i)(x + i)$ and, since $p$ is prime, $p \mid (x - i)$ or $p \mid (x + i)$. In either case we have $m + ni \in \mathbb Z[i]$ such that $p(m + ni) = x \pm i$, which implies $pn = x$, that is $p \mid x$, and $x^2 + 1 \equiv 1 \pmod p$, which is not congruent to $0$, contradiction.

This is perfectly lucid and correct, but I can't shake the feeling that it's possible to be more elegant without getting too advanced (i.e., cyclic groups). Maybe Max will elaborate his comment into an answer.

Okay, now to work out an example with a specific prime. I choose 41. We have $$\left(\frac{-1}{41}\right) = (-1)^{20} = 1,$$ just as we expected.

This tells us that the congruence $x^2 \equiv 40 \pmod{41}$ has solutions, and likewise the equation $x^2 = 41k - 1$. This should immediately lead us to find $9^2 = 2 \times 41 - 1$. Then $(9 - i)(9 + i) = 82$.

At this point we're saying that 41 is prime in $\mathbb Z[i]$, which means that either 41 divides $9 - i$ or it divides $9 + i$. However, before carrying out either division, notice that $9 + i$ has even norm. It must be divisible by either $1 - i$ or $1 + i$, maybe both.

So then we compute $$\frac{9 + i}{1 - i} = \frac{(9 + i)(1 + i)}{2} = \frac{8 + 10i}{2} = 4 + 5i$$ and we verify that $N(4 + 5i) = 41$.

Since 41's norm is 1681 but $N(9 \pm i)$ is just 82, we should have realized earlier that $41 \nmid (9 \pm i)$. I admit I don't know what is the most elegant way to get from $9 \pm i$ to $4 \pm 5i$.