Results 1 to 2 of 2

Math Help - Modulo

  1. #1
    Sea
    Sea is offline
    Junior Member Sea's Avatar
    Joined
    Dec 2008
    From
    Turkey
    Posts
    50

    Modulo

    <br /> <br />
a,n\in\mathbb{Z},


    Show that:

    n+1=a^2 \Rightarrow n+1|2(n-1)!
    Last edited by Sea; December 23rd 2008 at 03:07 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member PaulRS's Avatar
    Joined
    Oct 2007
    Posts
    571
    For the hypothesis it'd be enough to say that n is a positive integer such that n+1 is not a prime number.

    Let p^s be the maximum power of a prime p dividing n+1.


    • If n+1 is divisible by at least 2 primes, then p^s\leq{\tfrac{n}{2}}\leq{n-1} and so p^s appears as a factor of (n-1)!=1\cdot{2}...\cdot{p^s}\cdot{...\cdot{(n-1)}}, thus p^s|(n-1)!
    • Otherwise n+1=p^s. If p=2 then 2^{s-1} appears as a factor of (n-1)! - this can be seen as in the previous part- so 2^{s-1}|(n-1)! and so 2^{s}|[2\cdot{(n-1)!}]. Now if p>2 we have that p^{s-1} is a factor of (n-1)!, but, since n is not prime, it must be that s>1 and so 2p appears also as a factor in the product, because 2p<p^2-1\leq{p^s-1}=n-1 (*). Clearly 2p\neq p^{s-1} so we have that p^s|(n-1)!

    (*) 2p<p^2-1 iff 2<p^2-2p+1=(p-1)^2 and this holds since we were considering p>2

    From this analysis it follows that p^s|[2\cdot{(n-1)!}]. (this holds for all the maximum powers of primes dividing n+1)

    And therefore (n+1)|[2\cdot{(n-1)!}]

    Remark: This doesn't hold when n+1 is a prime greater than 2. ( it holds for n+1=2)
    Last edited by PaulRS; December 23rd 2008 at 08:49 AM. Reason: the case n+1=2 was missing in the remark
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Modulo
    Posted in the Algebra Forum
    Replies: 2
    Last Post: May 7th 2010, 05:14 PM
  2. Modulo help
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: April 18th 2010, 09:13 AM
  3. Modulo of squares = modulo of roots
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: December 1st 2009, 09:04 AM
  4. Modulo 42
    Posted in the Algebra Forum
    Replies: 3
    Last Post: June 2nd 2009, 05:00 PM
  5. Modulo
    Posted in the Algebra Forum
    Replies: 11
    Last Post: May 5th 2009, 02:24 PM

Search Tags


/mathhelpforum @mathhelpforum