# Non-constructive proof for a prime $p, \forall k \in \mathbb{Z+}, a\equiv b\pmod {p^k}\implies a\equiv b\pmod p.$ [closed]

As a simple case take $k=2, a\equiv b\pmod {p^2}\implies a\equiv b\pmod p.$
A constructive example for $a= 2, b=27, p =5$ will work, but needed is a general or non-constructive approach, so as to get the reasoning applicable generally in a formal manner.

I mean the reason for the no change in residue class, for a root of the modulus is not clear.

I can only work out the case when $a , b \lt p$, as it is the trivial case (with $a=b$) for the smaller modulus case.

## closed as unclear what you're asking by Lord Shark the Unknown, Namaste, JMP, Trevor Gunn, Mohammad Riazi-KermaniFeb 16 '18 at 13:35

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

• What could possibly be "non-constructive" about a proof of this (which just amounts to noting that $p\mid p^k$)? – Lord Shark the Unknown Feb 15 '18 at 7:07
• I wonder what you think "non-construction proof" means. – fleablood Feb 15 '18 at 7:09
• @LordSharktheUnknown For me your statement is a non-constructive proof, in a verbal manner. – jitender Feb 15 '18 at 7:09
• This is trivial. If $p^2|a-b$ and $p|p^2$ then $p|a-b$. p doesn't have to be prime and we don't have to square it. If $a\equiv b \mod nk$ then $a\equiv b\mod n$. I'm pretty sure you prove that last week. – fleablood Feb 15 '18 at 7:13
• I was talking more about a basic prove that if $a|b$ and $b|c$ then $a|c$. This question is absolutely the exact same. – fleablood Feb 15 '18 at 7:20

$$a \equiv b \pmod{p^k}$$

$$a-b \equiv 0 \pmod{p^k}$$

$$\exists m \in \mathbb{Z}, (a-b) =p^km$$

$$\exists m \in \mathbb{Z}, (a-b) =p(p^{k-1}m)$$

$$a-b \equiv 0 \pmod{p}$$

• Thanks a lot. I request that the failure for the converse case be proved by such (non-constructive) approach. I mean that given $a\equiv b \pmod {p} \nrightarrow a \equiv b \pmod {p^k}$. – jitender Feb 15 '18 at 7:18
• scratch head, to disprove it, I just need a counter example... I dont get what is non-constructive. – Siong Thye Goh Feb 15 '18 at 7:21
• I mean that there should be an algebraic proof, but as in converse the hypothesis and conclusion are exchanged; and given the implication in the original - so, assuming hypothesis is H, conclusion is C; we have originally: $\lnot H \cup C$, and for converse, it is: $\lnot C \cup H$. $H: a\equiv b \pmod {p^k}$, $C: a\equiv \pmod p$. So, have: $\lnot (a\equiv b \pmod p) \cup H$. And need to prove it false, as a general case. Also, $\exists k \in \mathbb{Z}, a \equiv b \pmod p \implies (a-b) = kp$ – jitender Feb 15 '18 at 7:34
• $p \equiv 0 \pmod{p}$ but $p \not \equiv 0 \pmod{p^k}, k>1$. – Siong Thye Goh Feb 15 '18 at 7:39
• I hope yours is till a constructive example, just not using an actual value to substitute for. May be I am wrong, as if a general case is taken then it is non-constructive. Confused. But, one thing is certain that it is still showing a counter-case. – jitender Feb 15 '18 at 7:42

If $a|b$ and $b|c$ then $a|c$. (Because if there exist $k$ so that $b=a*k$ and if there is a $m$ so that $c=b*m$, then $c=a (k*m)$

So if $a\equiv b\mod p^2$ that means $p^2|a-b$. And since $p|p^2$ we know $p|a-b$