0
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ A counterexample is a formal proof. $\endgroup$ – lulu Feb 15 '18 at 14:09
  • 1
    $\begingroup$ " (¬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. $\endgroup$ – fleablood Feb 15 '18 at 17:36
  • 1
    $\begingroup$ Shouldn't those $\cup$s be $\cap$s? $\endgroup$ – fleablood Feb 15 '18 at 17:39
  • $\begingroup$ @fleablood If an implication (if ..., then...) is considered, then only union of two terms, i.e. negated hypothesis and conclusion be there. $\endgroup$ – jitender Feb 15 '18 at 18:07
1
$\begingroup$
  • 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.
$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – jitender Feb 16 '18 at 19:26
  • 1
    $\begingroup$ hmmm... it's ok to have $R=Q$. $\neg P \lor Q$ is equivalent to $P \implies Q$. $\endgroup$ – Siong Thye Goh Feb 16 '18 at 20:19
  • $\begingroup$ 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. $\endgroup$ – jitender Feb 17 '18 at 2:17
  • 1
    $\begingroup$ i mean $(\neg P \lor Q)$ is equivalent to $(P \implies Q)$. It is not equivalent to $P \lor \neg Q$ $\endgroup$ – Siong Thye Goh Feb 17 '18 at 3:35
  • 1
    $\begingroup$ 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$. $\endgroup$ – Siong Thye Goh Feb 17 '18 at 17:41
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.