Results 1 to 4 of 4

Thread: 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 $\displaystyle 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
    $\displaystyle 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 $\displaystyle a^{p^k}\equiv1\pmod{p^{m+k+1}}$ we would have

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

    $\displaystyle \Rightarrow\ p\mid r$

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

    $\displaystyle \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 $\displaystyle \left(1+rp^m\right)^{p^k}$ the first two terms are 1 and $\displaystyle \left(p^k\right)\left(rp^m\right)=rp^{m+k}$ and the last term is $\displaystyle r^{p^k}p^{mp^k};$ all the other terms contain $\displaystyle p$ to powers greater than $\displaystyle m+k.$ If $\displaystyle m>1$ or $\displaystyle p\ge3$ then $\displaystyle mp^k\ge m+k+1$ as well. Hence $\displaystyle \left(1+rp^m\right)^{p^k}\equiv1+rp^{m+k}\pmod{rp^ {m+k+1}}$ if $\displaystyle m>1$ or $\displaystyle p\ge3.$

    However, when $\displaystyle p=2$ and $\displaystyle m=1$ it is possible for $\displaystyle mp^k<m+k+1;$ e.g. $\displaystyle 2<1+1+1.$ Hence the congruence $\displaystyle \left(1+rp^m\right)^{p^k}\equiv1+rp^{m+k}\pmod{rp^ {m+k+1}}$ breaks down if $\displaystyle p=2$ and $\displaystyle m=1.$
    Last edited by TheAbstractionist; Apr 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: Feb 3rd 2011, 07:50 PM
  2. [SOLVED] Modulo and congruence
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: Jun 26th 2010, 05:10 PM
  3. Congruence & Modulo Proof
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Feb 15th 2009, 06:00 PM
  4. Modulo/congruence proof help
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: Feb 1st 2009, 11:39 AM
  5. powers modulo m help needed
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: Jun 5th 2008, 08:49 AM

Search Tags


/mathhelpforum @mathhelpforum