1.4a Direct Proof

Direct Proof

A direct proof is a logical argument that establishes the truth of a given hypothesis $P$ by assuming its truth and demonstrating that the conclusion $Q$ necessarily follows, such that
$P⟹Q.$

Examples

Prove that for any $a,b,c\in Z$, if $a\mid b$ and $a\mid c$, then $a\mid (b+c)$.

We can express the nc=q_2a$forsomequotients$q_1,q_2 \in \mathbb{Z}$.Then,$b+c=a(q_1 + q_2)$,whichhasafactorof$a$andthereforecanbedividedby$a$.

Alternatively, this theorem can be expressed in quantifier form as $(\forall a,b,c\in \mathbb{Z})(P(a,b)\wedge P(a,c))⟹P(a,b+c)$.

Prove that an integer $0<n<1000$ is divisible by 9 if and only if the sum of its digits is divisible by 9.

We can express $n$ as a number $abc$ such that $n=100a+10b+c$. Then, we can express the sum of its digits as a multiple of 9 as $a+b+c=9q$ for some quotient $q\in \mathbb{Z}$. Substituting for $c=9q-a-b$, it follows that $n=99a+9b+9q=9(11a+b+q)$. Since $9$ factors out, $n$ is divisible by $9$.

Since we are solving for $P⟺Q$, we must also prove for the converse, $Q⟹P$. Suppose that $n=9q$ for some $q\in \mathbb{Z}$ is (clearly) divisible by $9$. Then, it follows that $100a+10b+c=9q$ is also divisible by $9$. We can massage the equation such that $99a+9b+(a+b+c)=9q$. This leads to
$a+b+c=9(q-11a-b),$
which is clearly divisible by $9$.