Show that (2n-1)! is always a square modulo 2n+1.
what do you know about legendre's symbol?
I'd treat it as two seperate cases.
Case 1: (2n+1) is non-prime.
In this case it is easy show that every prime factor of (2n+1) must be contained in (2n-1)! and hence the remainder is zero (a perfect square).
Case 2: (2n+1) is prime.
Let prime p = (2n+1).
By Wilson's Thm (see link), (p-1)! = (p-1) : modulo p
(p-2)!(p-1) = (p-1) : mod p
(p-2)! = 1 : mod p
Hence the remainder is always 1 (a perfect square) for this case.
In summary the remainder is always zero when (2n+1) is non-prime and is always one when (2n+1) is prime.
Link for Wilsons Thm
Quick errata :
In case 1 when I said, "it is easy show that every prime factor...", I have to admit that I was thinking specifically about non-repeated prime factors at the time, in which case the result really is trivial enough to be done "by inspection".
For the case where (2n+1) has repeated prime factors like q^m then you can use an arguement along the lines of :
Assume (2n+1) has a prime factor of the form q^m, where q is prime >= 3 and m is integer >= 2.
BTW. Note that (2n+1) can't have 2 as a factor so we only need to look a 3 and greater. Also, since I'm looking specifically at the case of repeated factors I only need to consider m greater or equal to 2.
Since q^m is a factor then,
(2n+1) >= q^m
(2n-1) >= q^m - 2
But also it is easy to show that q^m - 2 > m*q for q>=3 and m>=2
Loosly what this means is that if (2n+1) has a repeated prime factor q^m then (2n-1)! has enough factors of the form q, 2q, 3q etc to "cover" it.
Legendre symbol? Heard of, but not know much about it. It could possibly explain this modular question???
thanks to uark for a detailed and well-given solution!!!
Separate names with a comma.