Modular Arithmetic Question+

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

Answers and Replies

  • #2
matt grime
Science Advisor
Homework Helper
9,395
3
what do you know about legendre's symbol?
 
  • #3
uart
Science Advisor
2,776
9
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
 
Last edited:
  • #4
uart
Science Advisor
2,776
9
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:
  • #5
Legendre symbol? Heard of, but not know much about it. It could possibly explain this modular question???
 
  • #6
thanks to uark for a detailed and well-given solution!!!
 

Related Threads on Modular Arithmetic Question+

  • Last Post
Replies
5
Views
2K
  • Last Post
Replies
5
Views
572
  • Last Post
Replies
7
Views
3K
Replies
12
Views
5K
  • Last Post
Replies
4
Views
2K
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
17
Views
3K
  • Last Post
Replies
1
Views
560
  • Last Post
Replies
3
Views
2K
Replies
3
Views
2K
Top