1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Modular Arithmetic Question+

  1. May 26, 2004 #1
    Show that (2n-1)! is always a square modulo 2n+1.
    :cry:
     
  2. jcsd
  3. May 26, 2004 #2

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    what do you know about legendre's symbol?
     
  4. May 27, 2004 #3

    uart

    User Avatar
    Science Advisor

    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: May 27, 2004
  5. May 27, 2004 #4

    uart

    User Avatar
    Science Advisor

    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
  6. May 28, 2004 #5
    Legendre symbol? Heard of, but not know much about it. It could possibly explain this modular question???
     
  7. May 28, 2004 #6
    thanks to uark for a detailed and well-given solution!!!
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Modular Arithmetic Question+
  1. Modular arithmetic (Replies: 5)

  2. Modular arithmetic (Replies: 7)

Loading...