Is (2n-1)! Always a Square Modulo 2n+1?

  • Thread starter killerinstinct
  • Start date
  • Tags
    Arithmetic
In summary, the speaker discusses the Legendre symbol and its application to proving that (2n-1)! is always a square modulo 2n+1. They break the proof into two cases, one where (2n+1) is prime and another where it is not, and explain how the Wilson's Theorem and the existence of repeated prime factors contribute to the proof.
  • #1
killerinstinct
92
0
Show that (2n-1)! is always a square modulo 2n+1.
:cry:
 
Mathematics news on Phys.org
  • #2
what do you know about legendre's symbol?
 
  • #3
I'd treat it as two separate 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
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 argument 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!
 

What is modular arithmetic?

Modular arithmetic is a mathematical system that deals with integers and their remainders when divided by a specified number. It is often used to solve problems involving cyclic patterns or repeated operations.

How is modular arithmetic used in cryptography?

Modular arithmetic is used in cryptography to encrypt and decrypt messages. It provides a way to scramble and unscramble data using a secret key and a modular arithmetic function, making it difficult for unauthorized parties to access the information.

What is the difference between modular addition and modular multiplication?

Modular addition involves adding two numbers and then finding the remainder when divided by a specified number, while modular multiplication involves multiplying two numbers and finding the remainder. Both operations are used in modular arithmetic, but serve different purposes.

Can modular arithmetic be applied to non-integer numbers?

No, modular arithmetic is only applicable to integers. When dealing with non-integer numbers, modular arithmetic cannot be used, as remainders can only be calculated when dividing integers.

How is modular arithmetic used in computer science?

Modular arithmetic is used in computer science for various purposes, including data encryption, error correction codes, and generating random numbers. It is also used in computer graphics to create repeating patterns and in programming to optimize algorithms.

Similar threads

Replies
11
Views
316
Replies
1
Views
758
Replies
2
Views
972
Replies
1
Views
610
Replies
2
Views
835
  • General Math
Replies
1
Views
1K
  • General Math
Replies
1
Views
930
Replies
5
Views
1K
Replies
2
Views
1K
Back
Top