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

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.

• A counterexample is a formal proof. – lulu Feb 15 '18 at 14:09
• " (¬H∪C) cannot be true, in general case. " The only way to "prove" something can't be true in the general case is to give a counter example. And no matter how general and vague or constructive it may be, it is still a counter example. – fleablood Feb 15 '18 at 17:36
• Shouldn't those $\cup$s be $\cap$s? – fleablood Feb 15 '18 at 17:39
• @fleablood If an implication (if ..., then...) is considered, then only union of two terms, i.e. negated hypothesis and conclusion be there. – jitender Feb 15 '18 at 18:07

• 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.
• Thanks a lot for your kind help. Your answer introduced me to the contradiction approach that leads to "$\bot$" form. I read about contradiction approach, at link: math.stackexchange.com/a/705291/424260. It states:--- In a "genuine" proof by contradiction, you assume both $P$ and $\lnot Q,$ and deduce some other contradiction $R\wedge \lnot R.$ --- Have two issues: 1. My proof is not "genuine" proof, as per the link, as $R=Q$, & not "some other contradiction $R\wedge \lnot R"$. 2. I not use $P, \lnot Q$, as per definition at link; due to conditional leading to $\lnot P \lor Q$. – jitender Feb 16 '18 at 19:26
• hmmm... it's ok to have $R=Q$. $\neg P \lor Q$ is equivalent to $P \implies Q$. – Siong Thye Goh Feb 16 '18 at 20:19
• I want to elaborate my doubt regarding the second issue: Do you mean that both (i) $\lnot P , Q$ and (ii) $P, \lnot Q$ are equivalent. I have used the former, or (i), while the link stresses the need to use the latter, or (ii), to get a "genuine proof" for contradiction approach, with $P$ being the hypothesis and $Q$ the conclusion in a conditional. – jitender Feb 17 '18 at 2:17
• i mean $(\neg P \lor Q)$ is equivalent to $(P \implies Q)$. It is not equivalent to $P \lor \neg Q$ – Siong Thye Goh Feb 17 '18 at 3:35
• can you quantify every variable is involve including $a$ and $b$ in a statement that you want to prove. Contradiction is about given a true statement, you suppose it is false and you get a contradiction. if you want to show that $\forall x, \exists y P(x,y)$ is true. you assume that $\exists x , \forall y \neg P(x,y)$ is false and try to find a contradiction. Note that the article that you link to is about proving $P \rightarrow Q$ while you are trying to prove $P \nrightarrow Q$. – Siong Thye Goh Feb 17 '18 at 17:41

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.