Show that if integers a and b both are not divisible by 5, then the product ab is also not divisible by 5....where a=5k+r such as (1 <= r <= 4)

Printable View

- May 20th 2008, 06:20 PMVedicmathsDivisibility...
Show that if integers a and b both are not divisible by 5, then the product ab is also not divisible by 5....where a=5k+r such as (1 <= r <= 4)

- May 20th 2008, 06:58 PMIsomorphism
$\displaystyle a = 5k_1 + r_1$ and $\displaystyle b = 5k_2 + r_2$. Since 5 does not divide, $\displaystyle r_1 r_2 \neq 0$.

$\displaystyle ab= (5k_1 + r_1)(5k_2 + r_2) = 25k_1 k_2 + 5k_1 r_2 + 5k_2 r_1 + r_1 r_2$

Now we want to prove that 5 does not divide ab. Lets do what Jhevon has taught you before.... the contradiction method....

So let us assume 5 does divide ab, that means 5 divides $\displaystyle 25k_1 k_2 + 5k_1 r_2 + 5k_2 r_1 + r_1 r_2 = 5(5k_1 k_2 + k_1 r_2 + k_2 r_1) + r_1 r_2 $. But this means 5 divides $\displaystyle r_1 r_2$. But since $\displaystyle r_1$ and $\displaystyle r_2$ are both less than 5 and and nonzero, 5 cannot divide $\displaystyle r_1 r_2$. This**contradicts**our assumption that 5 divides ab. So 5 does not divide ab :) - May 20th 2008, 07:15 PMTheEmptySet
Another way to do it.

Lets write this as an if then statement

if $\displaystyle 5 \not | a$ and $\displaystyle 5 \not | b$

then $\displaystyle 5 \not | (ab)$

in this form we can find p and q

$\displaystyle p \implies q$ is logically equivelent to (the contraposition)

$\displaystyle \neg q \implies \neg p$

or in words

if $\displaystyle 5 | (ab)$ then $\displaystyle 5|a$ or $\displaystyle 5|b$

this is easier to prove

since 5|ab $\displaystyle 5=(ab)q,q \in \mathbb{Z}$

suppose that 5|a then we are done...

now suppose that $\displaystyle 5 \not | a$ we need to show that 5|b

but 5=(ab)q 5=(aq)b so 5|b

QED

I hope this helps.