Results 1 to 2 of 2

Thread: Modulo

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

    Modulo

    $\displaystyle

    a,n\in\mathbb{Z},$


    Show that:

    $\displaystyle n+1=a^2 \Rightarrow n+1|2(n-1)!$
    Last edited by Sea; Dec 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 $\displaystyle n$ is a positive integer such that $\displaystyle n+1$ is not a prime number.

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


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

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

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

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

    Remark: This doesn't hold when $\displaystyle n+1$ is a prime greater than 2. ( it holds for $\displaystyle n+1=2$)
    Last edited by PaulRS; Dec 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: Apr 18th 2010, 09:13 AM
  3. Modulo of squares = modulo of roots
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: Dec 1st 2009, 09:04 AM
  4. Modulo 42
    Posted in the Algebra Forum
    Replies: 3
    Last Post: Jun 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