I read in this paper (see page 1 paragraph 3) that Gaussian integers arithmetic $\pmod{p}$, where $p\in\mathbb{Z}^+$ is a prime, requires that $p \equiv 3 \pmod{4}$.
I have some doubts here that I hope one can clarify:
1- Why is this necessary?
2- What about primes $\equiv 1 \pmod{4}$? don't they support Gaussian integers arithmetic (I tired some examples and it works fine for +,-,*)?
3- Which operations are not supported specifically (division, remainder, or what)?
4- Is there any trick that can be used to support Gaussian integers arithmetic using these primes $\equiv 1 \pmod{4}$?
As I understand, $p$ is a prime number, and you are working in a field $F$ with $p^2$ elements. This field contains the field $\mathbb{F}_p = \mathbb{Z}/p\mathbb{Z}$ with $p$ elements as a subfield.
Assuming $p$ is congruent to $3$ modulo $4$, it is possible to write the elements of $F$ in a similar way to Gaussian integers: namely, there some is element of $F$, let's call it $i$, with the property that $i^2 = -1$. Such an element $i$ will not be in $\mathbb{F}_p$. Then
$$F = \{ a+ bi : a, b \in \mathbb{F}_p \}$$
You can't do this if $p \equiv 1 \pmod{4}$, because in this case, the square roots of $-1$ already lie in $\mathbb{F}_p$. For example, if $p = 5$, then $-1$ is equal to $2^2$. Therefore, the set
$$\{ a + bi : a, b \in \mathbb{F}_p\}$$
just gets you $\mathbb{F}_p$, not all of $F$.