# Divisibility...

• May 20th 2008, 06:20 PM
Vedicmaths
Divisibility...
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 PM
Isomorphism
Quote:

Originally Posted by Vedicmaths
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)

$a = 5k_1 + r_1$ and $b = 5k_2 + r_2$. Since 5 does not divide, $r_1 r_2 \neq 0$.

$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 $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 $r_1 r_2$. But since $r_1$ and $r_2$ are both less than 5 and and nonzero, 5 cannot divide $r_1 r_2$. This contradicts our assumption that 5 divides ab. So 5 does not divide ab :)
• May 20th 2008, 07:15 PM
TheEmptySet
Quote:

Originally Posted by Vedicmaths
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)

Another way to do it.

Lets write this as an if then statement

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

then $5 \not | (ab)$

in this form we can find p and q

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

$\neg q \implies \neg p$

or in words

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

this is easier to prove

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

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

now suppose that $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.