- #1

- 92

- 0

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

- Thread starter killerinstinct
- Start date

- #1

- 92

- 0

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

- #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

Case 1:

In this case it is easy show that every prime factor of

Case 2: (2n+1) is prime.

Let prime

By Wilson's Thm (see link),

Hence the remainder is always 1 (a perfect square) for this case.

In summary the remainder is always

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.

In case 1 when I said, "it is

For the case where (2n+1) has repeated prime factors like

Assume (2n+1) has a prime factor of the form

BTW. Note that

Since

(2n-1) >= q^m - 2

But also it is easy to show that

Loosly what this means is that if

Last edited:

- #5

- 92

- 0

- #6

- 92

- 0

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

- 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