# Thread: proof of a congruence modulo prime powers

1. ## 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

2. $\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}}$

3. 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?

4. Originally Posted by minivan15
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.$