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

Have something to add?



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

  2. Modular arithmetic (Replies: 7)

Loading...