Problem with finding the GCD in the Field of Polynomials mod p I am really having trouble working a problem in my course. I will post it and then add what I have thought etc.
Let p be an odd prime, then using the Euclidian Algorithm, calculated the GCD of of $x^{p-1}-1$ and $x^2+1$ in $\mathbb{Z} / p\mathbb{Z}[x]$
Also, how does $p=1 (mod4)$ tell us that  $-1$ is a square in $\mathbb{Z} / p\mathbb{Z}$, infact that $-1$ is a square here if and only if $p=1(mod4)$.
My thoughts: 
I know that $$x^{p}-x=(x)(x-1)(x-2)…(x-(p-1))$$ and so that in this sense our roots will be the congruence classes of $1,2,…p-1$
and also that $$x^{p-1}-1=(x-1)(x-2)…(x-(p-1))$$
But I get lost when trying to apply the EA to these polynomials,
like how can I do it when p is arbitrary?
Preferably id like to be able to understand/see how to do the first part first i.e. using division with residue and then move on to the second part.
Any insight/hint or solution to this would be great,
Thank you all
Update:
When I try to do division with residue, I just get
$$x^{p-1}-1=(x^2+1)(x^{p-3}-x^{p-5}+x^{p-7}-x^{p-9}...)$$
for example,
$p=7$
$$(x^{6}-1)=(x^2+1)(x^4-x^2+1)$$
for $p=11$
$$(x^{10}-1)=(x^2+1)(x^{8}-x^{6}+x^{4}-x^{2}+1)$$
which for specific cases tells me that 1 is the gcd, but I dont know how to generalize that for the case with arbitrary prime p.
 A: a) Let $p$ be of the form $4k+3$. Then $\frac{p-1}{2}$ is twice an odd number. It follows that $x^2+1$ divides $x^{p-1}+1$, by the familiar fact that the polynomial $t+1$ divides $t^n+1$ when $n$ is odd. 
So $x^{p-1}+1=A(x)(x^2+1)$ for some polynomial $A(x)$. It follows that $x^{p-1}-1=A(x)(x^2+1)-2$. We conclude that $\gcd(x^{p-1}-1,x^2+1)=1$. 
b) Now let $p=4k+1$.  Observe that the polynomial $t^{2k}-1$ has root $t=-1$. So $t+1$ divides $t^{2k}-1$ and therefore, putting $t=x^2$, we conclude that $x^2+1$ divides $x^{4k}-1$.
Remark:  Now to your question about $x^2+1\equiv 0\pmod{p}$ when $p\equiv 1\pmod{4}$.  Note that $x^{p-1}-1=(x-1)(x-2)\cdots(x-(p-1))$. Since $x^2+1$ divides this, by unique factorization of polynomials it follows that $x-a$ must divide $x^2+1$ for some $a$, meaning that $x^2+1\equiv 0\pmod{p}$ has a solution.
If instead we take as given that the congruence has a solution, we can show divisibility by $x^2+1$ in another way. For let $a$ and $b$ be the solutions of the congruence. Then $x^2+1$ splits as $(x-a)(x-b)$, which obviously divides $(x-1)(x-2)\cdots(x-(p-1))$, and so the gcd is $x^2+1$.
Proofs that for primes of the form $4k+1$ the congruence $x^2+1\equiv 0\pmod{p}$ has a solution can be found in many places. The problem has been solved repeatedly on MSE. The usual argument uses the fact that $p-1\equiv -1$, $p-2\equiv -2$, and so on, so by Wilson's Theorem $(2k!)^2\equiv -1\pmod{p}$. There are also group theoretic arguments. And our polynomial manipulation in b) gives still another proof.
By the way, it is easy to see from a) that if $p=4k+3$ then the congruence $x^2+1\equiv 0\pmod{p}$ has no solution.
