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

• 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.

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.