Modular Arithmetic Question+

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.