Modular Arithmetic Question+

1. May 26, 2004

killerinstinct

Show that (2n-1)! is always a square modulo 2n+1.

2. May 26, 2004

matt grime

what do you know about legendre's symbol?

3. May 27, 2004

uart

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.

Last edited: May 27, 2004
4. May 27, 2004

uart

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.

Last edited: May 27, 2004
5. May 28, 2004

killerinstinct

Legendre symbol? Heard of, but not know much about it. It could possibly explain this modular question???

6. May 28, 2004

killerinstinct

thanks to uark for a detailed and well-given solution!!!