4
$\begingroup$

Ok so my teacher said we can use this sentence: If $a$ is not a multiple of $5$, then $a^2$ is not a multiple of $5$ neither.

to prove this sentence: If $a^2$ is a multiple of $5$, then $a$ itself is a multiple of $5$

I don't understand the logic behind it, I mean what's the link between them, how can we conclude the 2nd sentence to be true if the 1st one is true?

Thanks a lot guys!

4 Answers 4

4

This is an example of an implication and its contrapositive. The contrapositive of an implication $\varphi\to\psi$ is the implication $\lnot\psi\to\lnot\varphi$; in words, the contrapositive of $\text{if }\varphi\text{ is true},\text{ then }\psi\text{ is true}\tag{1}$ is $\text{if }\psi\text{ is not true},\text{ then }\varphi\text{ is not true}\;.\tag{2}$

(Here $\varphi$ and $\psi$ are any statements.)

Suppose that you know that $(1)$ is true: whenever $\varphi$ is true, so is $\psi$. Now you discover that $\psi$ is false. Could $\varphi$ be true? No, because if it were, then you know that $\psi$ would be true as well. Thus, if $\psi$ is false you can conclude that $\varphi$ must be false as well $-$ which is $(2)$ in slightly different words.

In your case $\varphi$ is $a\text{ is not a multiple of }5$ and $\psi$ is $a^2\text{ is not a multiple of }5\;.$

You know that if $a$ is not a multiple of $5$, then neither is $a^2$. Suppose, now, that someone hands you an $a^2$ that is a multiple of $5$. Could $a$ fail to be a multiple of $5$? No: if $a$ were not a multiple of $5$, then $a^2$ would not be a multiple of $5$, and we know that this particular $a^2$ is a multiple of $5$. Since $a$ either is or is not a multiple of $5$, and we’ve ruled out the second possibility, we conclude that $a$ is also a multiple of $5$.

2

Given statements $p,q$, the following are equivalent:

$p\Rightarrow q$

$\neg q\Rightarrow\neg p$

To check that, you can use a truth table. These two are called contrapositives of each other.

In particular, let $p$ be the statement "$a^2$ is a multiple of $5$", and $q$ be the statement "$a$ is a multiple of $5$." Your teacher is saying that you can use $\neg q\Rightarrow\neg p$ to prove $p\Rightarrow q$.

2

For $p$ prime, $p|ab$ implies $p|a$ or $p|b$.

Since 5 is prime we have $5|a^2$ implies $5|a$ or $5|a$.

1

There are two possibilities:

$a$ is a multiple of 5 - in which case we prove that $a^2$ is a multiple of 5

$a$ is not a multiple of 5 - in which case we prove that $a^2$ is not a multiple of 5

So we have proved those facts.

Now suppose we are given a square number, and it is a multiple of 5. Can it come from the second line - no; so it must come from the first line.

In fact we don't need to prove the first line to show that a square number which is a multiple of 5 cannot come from the second line. And your teacher has dispensed with it.