Results 1 to 6 of 6

Math Help - 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: <br />
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)}}<br />
{{\left( {k - 1} \right) \cdot ...\left( {k - k + 1} \right) \cdot \left( {k - k - 1} \right)... \cdot \left( {k - p + 1} \right)}}} <br />

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

    Thus: <br />
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)}}<br />
{{\left( {k - 1} \right) \cdot ...\left( {k - k + 1} \right) \cdot \left( {k - k - 1} \right)... \cdot \left( {k - p + 1} \right)}}} <br />

    Simplifying we get: <br />
\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} } <br />

    Now by Fermat's Little Theorem and the Binomial Theorem: \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
    7
    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
    7
    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
    9
    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 f(x) = x(x-1)...(x-(p-1)) over \mathbb{Z}_p, p odd.
    Notice that f(0) = f(1) = ... = f(p-1) = 0.
    Consider g(x) = x^p - x.
    Notice that g(0) = g(1) = ... = g(p-1) = 0.
    The polynomial f(x) - g(x) has degree p-1 and it is 0 for p values.
    This must be that f(x) - g(x) is the zero polynomial and so f(x) = g(x).
    The x coefficient of f(x) is (-1)^{p-1}(1)(2)...(p-1) = (p-1)!.
    The x coefficient of g(x) is -1.
    Therefore, (p-1)! \equiv -1(\bmod p).

    ---

    Here is another proof, again p>2.
    Let 0 < x < p, if x is its own inverse mod p then x^2 \equiv 1(\bmod p).
    Thus, (x-1)(x+1) \equiv 0(\bmod p) \implies x = 1 \text{ or }p-1.
    If 1 < x < p-1 then there is  1 < y  < p-1 so that xy\equiv 1(\bmod p) and x\not = y.
    In the list 2,3,...,p-2 for every a\in \{2,...p-2\} pair it with b so that ab\equiv 1(\bmod p).
    Therefore, (p-1)!\equiv (p-1) \equiv -1(\bmod p) because we can rearrange the factors to produce 1 mod p.
    (We do not pair 1 or 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: June 20th 2010, 10:02 PM
  2. HW help....dealing with e
    Posted in the Calculus Forum
    Replies: 2
    Last Post: March 29th 2010, 11:35 AM
  3. Dealing with
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: November 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: January 2nd 2008, 03:47 PM

Search Tags


/mathhelpforum @mathhelpforum