# Pythagorean Primes and Gaussian Primes, divisibility question

1. Jan 20, 2010

### joeblow

Here is an interesting problem that I've been thinking about for a while:

Let p be a prime s.t. p = 4m+1 for some integer m. Show that p divides n^2 + 1, where n = (2m)!

It comes from a section on principal ideal domains and unique factorization domains.

It is well-known that p is the sum of squares of two integers and thus is a norm of a Gaussian prime, and n^2 + 1 = (n+i)*(n-i).

However, I am not sure that this helps anything. Does anyone have any ideas. Your help is greatly appreciated.

2. Jan 22, 2010

### joeblow

I figured it out. For those of you who want a hint, try to use Wilson's theorem. (I have no idea why this was in the section on PID's.) When I saw the factorial sign, I immediately tried Wilson's theorem, but I needed to be much more clever in order to get it to work.

3. Jan 22, 2010

### rasmhop

In case other people find this thread I will post a solution:
$$2m+i \equiv (4m+1)-(2m+i) = 2m + 1 - i \pmod {4m+1}$$
Thus,
$$\prod_{i=1}^{2m} (2m+i) \equiv \prod_{i=1}^{2m} (2m + 1 - i) = \prod_{i=1}^{2m}(2m+1-(2m+1-i)) = \prod_{i=1}^{2m} i = (2m)! \pmod {4m+1}$$
This gives,
$$(4m)! = (2m)!\prod_{i=1}^{2m} (2m+i) \equiv (2m)!^2 \pmod {4m+1}$$
Now since 4m+1 is prime we can apply Wilson's theorem.
$$-1 \equiv (4m+1-1)! \equiv (2m)!^2 \pmod {4m+1}$$
Thus $4m+1 | (2m)!^2 + 1$ which was to be shown.

Wilson's theorem is introduced in the exercises around PIDs in many abstract algebra books. Usually this means that exercises on applying Wilson's theorem is scattered in nearby sections.

4. Feb 1, 2010

### joeblow

Wilson's theorem is not presented anywhere near this problem. I would assume that this problem is supposed to help you determine which gaussian integers are irreducible.