Results 1 to 6 of 6

Thread: two problems dealing with congruences

  1. #1
    Junior Member
    Joined
    Sep 2008
    Posts
    55

    two problems dealing with congruences

    1. let p be a prime number. Show that (p - 1)! is congruent to (-1)mod p


    2. prove criteria for divisibility by 2, 3, 4, 5, 9, 10, 11 using congruences modulo appropriate powers of 10

    for this one, I have proved 2 and 10 modulo 10, but am stuck on 3

    for divisibility by 3:

    say n = d0 + 10d1 + ... +(10^k)dk

    so I need to prove that if d0 + d1 + ... +dk is divisible by 3, then so is n

    I can see how it would work modulo 3 (start with d0 +d1 +... +dk is congruent to 0 mod 3 and manipulate it to get n is congruent to 0 mod 3), but the problem clearly states i need to use modulo appropriate powers of 10... a starting point on this would be great. Thanks!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member PaulRS's Avatar
    Joined
    Oct 2007
    Posts
    571
    1. Note that: $\displaystyle
    p\left( x \right) = x^{p - 1} - \left( {x - 1} \right) \cdot ... \cdot \left( {x - p + 1} \right) = \sum\limits_{k = 1}^{p - 1} {k^{p - 1} \cdot \tfrac{{\left( {x - 1} \right) \cdot ...\left( {x - k + 1} \right) \cdot \left( {x - k - 1} \right)... \cdot \left( {x - p + 1} \right)}}
    {{\left( {k - 1} \right) \cdot ...\left( {k - k + 1} \right) \cdot \left( {k - k - 1} \right)... \cdot \left( {k - p + 1} \right)}}}
    $

    Since $\displaystyle p(x)$ is of degree $\displaystyle x^{p-2}$ and the RHS is a polynomial of the same degree that gives the same values for $\displaystyle x=1,2,...,p-1$

    Thus: $\displaystyle
    p\left( 0 \right) = - \left( {p - 1} \right)! = \sum\limits_{k = 1}^{p - 1} {k^{p - 1} \cdot \tfrac{{\left( {0 - 1} \right) \cdot ...\left( {0 - k + 1} \right) \cdot \left( {0 - k - 1} \right)... \cdot \left( {0 - p + 1} \right)}}
    {{\left( {k - 1} \right) \cdot ...\left( {k - k + 1} \right) \cdot \left( {k - k - 1} \right)... \cdot \left( {k - p + 1} \right)}}}
    $

    Simplifying we get: $\displaystyle
    \left( {p - 1} \right)! = \sum\limits_{k = 1}^{p - 1} {\binom{p-1}{k} \cdot k^{p - 1} \cdot \left( { - 1} \right)^{p - 1 - k} }
    $

    Now by Fermat's Little Theorem and the Binomial Theorem: $\displaystyle \sum\limits_{k = 1}^{p - 1} {\binom{p-1}{k} \cdot k^{p - 1} \cdot \left( { - 1} \right)^{p - 1 - k} } \equiv{\sum\limits_{k = 1}^{p - 1} {\binom{p-1}{k} \cdot \left( { - 1} \right)^{p - 1 - k} }}=(-1)^p (\bmod.p)$

    And the result follows.

    For more proofs see here
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    10
    Quote Originally Posted by minivan15 View Post
    for divisibility by 3:

    say n = d0 + 10d1 + ... +(10^k)dk

    so I need to prove that if d0 + d1 + ... +dk is divisible by 3, then so is n

    I can see how it would work modulo 3 (start with d0 +d1 +... +dk is congruent to 0 mod 3 and manipulate it to get n is congruent to 0 mod 3), but the problem clearly states i need to use modulo appropriate powers of 10... a starting point on this would be great. Thanks!
    Notice that 10 is congruent to 1 (mod 3), and therefore so is any power of 10. Thus d0 + 10d1 + ... +(10^k)dk is congruent to ...
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member
    Joined
    Sep 2008
    Posts
    55
    okay i see how that would go..thank you

    I think I may have misunderstood the problem...does the phrase "modulo appropriate powers of 10" refer to doing 10 mod something (i.e. 10 congruent to 1 mod 10)? Because I thought it meant doing something mod 10 (i.e. d0 congruent to n mod 10)

    if someone could clear that up that would be great. Thank you for your answers!
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    10
    Quote Originally Posted by minivan15 View Post
    okay i see how that would go..thank you

    I think I may have misunderstood the problem...does the phrase "modulo appropriate powers of 10" refer to doing 10 mod something (i.e. 10 congruent to 1 mod 10)? Because I thought it meant doing something mod 10 (i.e. d0 congruent to n mod 10)

    if someone could clear that up that would be great. Thank you for your answers!
    I see what you mean. I hadn't noticed the strange way that the question is phrased. I think that it must surely have meant to say "using powers of 10 reduced by an appropriate modulus." I don't see that you can get anywhere by using a power of 10 as the modulus.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by minivan15 View Post
    1. let p be a prime number. Show that (p - 1)! is congruent to (-1)mod p
    Kinda similar to what PaulRS said.

    Consider $\displaystyle f(x) = x(x-1)...(x-(p-1))$ over $\displaystyle \mathbb{Z}_p$, $\displaystyle p$ odd.
    Notice that $\displaystyle f(0) = f(1) = ... = f(p-1) = 0$.
    Consider $\displaystyle g(x) = x^p - x$.
    Notice that $\displaystyle g(0) = g(1) = ... = g(p-1) = 0$.
    The polynomial $\displaystyle f(x) - g(x)$ has degree $\displaystyle p-1$ and it is $\displaystyle 0$ for $\displaystyle p$ values.
    This must be that $\displaystyle f(x) - g(x)$ is the zero polynomial and so $\displaystyle f(x) = g(x)$.
    The $\displaystyle x$ coefficient of $\displaystyle f(x)$ is $\displaystyle (-1)^{p-1}(1)(2)...(p-1) = (p-1)!$.
    The $\displaystyle x$ coefficient of $\displaystyle g(x)$ is $\displaystyle -1$.
    Therefore, $\displaystyle (p-1)! \equiv -1(\bmod p)$.

    ---

    Here is another proof, again $\displaystyle p>2$.
    Let $\displaystyle 0 < x < p$, if $\displaystyle x$ is its own inverse mod $\displaystyle p$ then $\displaystyle x^2 \equiv 1(\bmod p)$.
    Thus, $\displaystyle (x-1)(x+1) \equiv 0(\bmod p) \implies x = 1 \text{ or }p-1$.
    If $\displaystyle 1 < x < p-1$ then there is $\displaystyle 1 < y < p-1$ so that $\displaystyle xy\equiv 1(\bmod p)$ and $\displaystyle x\not = y$.
    In the list $\displaystyle 2,3,...,p-2$ for every $\displaystyle a\in \{2,...p-2\}$ pair it with $\displaystyle b$ so that $\displaystyle ab\equiv 1(\bmod p)$.
    Therefore, $\displaystyle (p-1)!\equiv (p-1) \equiv -1(\bmod p)$ because we can rearrange the factors to produce $\displaystyle 1$ mod $\displaystyle p$.
    (We do not pair $\displaystyle 1$ or $\displaystyle p-1$ because they only pair with themselves).
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 2
    Last Post: Jun 20th 2010, 10:02 PM
  2. HW help....dealing with e
    Posted in the Calculus Forum
    Replies: 2
    Last Post: Mar 29th 2010, 11:35 AM
  3. Dealing with
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: Nov 3rd 2009, 04:35 AM
  4. dealing with -i
    Posted in the Algebra Forum
    Replies: 4
    Last Post: May 15th 2008, 01:06 PM
  5. Replies: 3
    Last Post: Jan 2nd 2008, 03:47 PM

Search Tags


/mathhelpforum @mathhelpforum