Prove for prime $p, \forall l \in \mathbb Z^+, a\equiv b\pmod {p}\nrightarrow a\equiv b\pmod {p^l}.$

Question

Although, it is easy to see with an example with $a=2,b=12, p=5, l=2$, I wanted a formal proof.
Let the hypothesis be denoted by $H$, and conclusion by $C$.
$C: a\equiv b \pmod {p^l}, H: a≡b \pmod p$.
So, have to prove failure of : $\lnot (a\equiv b\pmod p)\cup C $
$\implies \lnot (\exists k \in \mathbb{Z}, (a−b)=kp) \cup C$
$\implies (\forall k \in \mathbb{Z}, (a−b)\ne kp) \cup C$
So, $\forall k \in \mathbb{Z}, (a−b)\ne kp$ is a tautology, as true for all values possible of $k$. Also, it being a tautology means that its union with any proposition is also true.

Need prove by contradiction by finding that the above expression ($\lnot H \cup C$) cannot be true, in general case.
=>$ (\forall k \in \mathbb{Z}, (a−b)\ne kp) \cup (a\equiv b \pmod {p^l})$
=>$(\forall k \in \mathbb{Z}, (a−b)\ne kp) \cup (\exists m \in \mathbb{Z}, {p^l} = m (a-b))$ is not true in general.

So, can we prove by transitivity of division, that:
if $(p \nmid (a-b) \wedge (\forall l \in \mathbb{Z+}, p \mid p^l))$, then it implies that $p^l \nmid (a-b)$

Have confusion regarding the validity of the last statement, as is crucial to proof by contradiction.

---

Edit The validity of the last statement is arrived at by using the contra-positive approach with the proof for : $r\mid s, r\nmid t\implies s\nmid t$, as at my posts here, and here. The initial input was provided by the answer by Siong Thye Goh.

Answer 1

• A counterexample is a formal proof.

• Just verify that $12-2=10$ is multiple of $5$ but not a multiple of $5^2$.

• logical or is usually denoted by $\lor$.

• transitivity of division means $r|s$ and $s | t$ then we have $r|t$. What are your $r,s,t$?

• we do not have $r|s$ and $r \not \mid t$, then $t \not \mid s$. $2$ divides $6$ , $2$ doesn't divide $3$ but $3$ divides $6$.

• Fortunately, we do have $p \not \mid r$ then $\forall l \in \mathbb{Z}^+, p^l \not \mid r$.

• You wanted to show the failure of $\forall a,b \in \mathbb{Z}, \forall l \in \mathbb{Z}^+, \neg ( a \equiv b \pmod{p}) \lor a \equiv b \pmod{p^l}$ and hence you assume it is true and hope that you encounter a contradiction. hence $\forall a,b \in \mathbb{Z}, \forall l \in \mathbb{Z}^+, ( p \not \mid (a-b)) \lor a \equiv b \pmod{p^l}$ and then we arrived at $\forall a,b \in \mathbb{Z}, \forall l \in \mathbb{Z}^+, ( a \not\equiv b \pmod{p^l}) \lor a \equiv b \pmod{p^l}$ which is not a contradiction.

• If you let $a=2,b=12, p=5, k=2$, then $p \not \mid a-b$ is false and $a \equiv b \pmod{p^l}$ is also a false statement.
• Aiming to reach a statement that claims it is false for all $a,b, l$ is a tough target and in fact not expected for the question. You just have to show that sometimes it is false, it is alright to be true sometimes.
• I think what you wanted to show is $\exists a,b \in \mathbb{Z}, \exists l \in \mathbb{Z}^+, a \equiv b \pmod{p} \nrightarrow a \equiv b\pmod{p^l}$ is a true statement, since $a=2, b=12,p=5, l=2$ is an example.
• $\exists a,b \in \mathbb{Z}, \forall l \in \mathbb{Z}^+, a \equiv b \pmod{p} \nrightarrow a \equiv b\pmod{p^l}$ is a true statement, since $a=0$ and $b=0$ is an example.

Answer 2

A counter example is a formal proof.

However if you want a more general statement:

$a\equiv b\mod p$ implies that $a = b + k*p$ for some $k \in \mathbb Z$.

We know nothing of $k$ and it could be anything. $k\equiv \overline{k} \mod p^{l-1}$ for some equivalence class. And.... you know what... let's just use the the division algorithm.

$k = q*p^{l-1} + r$ for a unique set of integers $q$ and $r: 0\le r < p^{l-1}$.

So $a = b + k*p = b + (q*p^{l-1} + r)p = b + r*p + q*p^l$.

So $a \equiv b + r*p \mod p^l$ and $a - b \equiv r*p \mod p^l$.

If $r = 0$ then $a \equiv b\mod p^l$. Fine. But if $r \ne 0$ and $0 < r < p^{l-1}$ then $0< rp < p^l$ so $a-b \equiv rp \not \equiv 0\mod p^l$ and $a \not \equiv b \mod p^l$. Not fine.