Results 1 to 4 of 4

Math Help - proof of a congruence modulo prime powers

  1. #1
    Junior Member
    Joined
    Sep 2008
    Posts
    55

    proof of a congruence modulo prime powers

    let the symbol = denote congruence (a=b mod n means a is congruent to b mod n)

    let p be a prime number, m,k be two positive integers, p does not divide a


    Prove that if p>2 or m>1 and a=1 mod p^m is true, a=1 mod p^(m+1) is false, then:

    a^(p^k)=1 mod p^(m+k) is true (I have already proved this)

    a^(p^k)=1 mod p^(m+k+1) is false (this is the one I need help on)

    thank you! and sorry about the sloppy notation, I don't know how to do the imaging stuff
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member JaneBennet's Avatar
    Joined
    Dec 2007
    Posts
    293
    a=1+rp^m\ \Rightarrow\ a^{p^k}=\left(1+rp^m\right)^{p^k}\equiv1+rp^{m+k}\  pmod{p^{m+k+1}}

    If a^{p^k}\equiv1\pmod{p^{m+k+1}} we would have

    ___ rp^{n+k}\equiv0\pmod {p^{m+k+1}}

    \Rightarrow\ p\mid r

    \Rightarrow\ a=1+rp^m\equiv1\pmod{p^{m+1}} (contradiction)

    \therefore\ a^{p^k}\not\equiv1\pmod{p^{m+k+1}}
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Sep 2008
    Posts
    55
    thank you for your reply! Could you please explain the first line in more detail?

    also, why does this fail when p=2 and m=1?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member TheAbstractionist's Avatar
    Joined
    Apr 2009
    Posts
    328
    Thanks
    1
    Quote Originally Posted by minivan15 View Post
    thank you for your reply! Could you please explain the first line in more detail?

    also, why does this fail when p=2 and m=1?
    Hi minivan15.

    In the binomial expansion of \left(1+rp^m\right)^{p^k} the first two terms are 1 and \left(p^k\right)\left(rp^m\right)=rp^{m+k} and the last term is r^{p^k}p^{mp^k}; all the other terms contain p to powers greater than m+k. If m>1 or p\ge3 then mp^k\ge m+k+1 as well. Hence \left(1+rp^m\right)^{p^k}\equiv1+rp^{m+k}\pmod{rp^  {m+k+1}} if m>1 or p\ge3.

    However, when p=2 and m=1 it is possible for mp^k<m+k+1; e.g. 2<1+1+1. Hence the congruence \left(1+rp^m\right)^{p^k}\equiv1+rp^{m+k}\pmod{rp^  {m+k+1}} breaks down if p=2 and m=1.
    Last edited by TheAbstractionist; April 24th 2009 at 01:36 PM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Computing square roots modulo prime powers
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: February 3rd 2011, 07:50 PM
  2. [SOLVED] Modulo and congruence
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: June 26th 2010, 05:10 PM
  3. Congruence & Modulo Proof
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: February 15th 2009, 06:00 PM
  4. Modulo/congruence proof help
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: February 1st 2009, 11:39 AM
  5. powers modulo m help needed
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: June 5th 2008, 08:49 AM

Search Tags


/mathhelpforum @mathhelpforum