Results 1 to 3 of 3

Thread: Divisibility...

  1. #1
    Member
    Joined
    May 2008
    Posts
    102
    Awards
    1

    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)
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Lord of certain Rings
    Isomorphism's Avatar
    Joined
    Dec 2007
    From
    IISc, Bangalore
    Posts
    1,465
    Thanks
    6
    Quote Originally Posted by Vedicmaths View Post
    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)
    $\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
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Behold, the power of SARDINES!
    TheEmptySet's Avatar
    Joined
    Feb 2008
    From
    Yuma, AZ, USA
    Posts
    3,764
    Thanks
    78
    Quote Originally Posted by Vedicmaths View Post
    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 $\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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Divisibility 11
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: Dec 20th 2008, 02:41 AM
  2. Divisibility (gcd) 10
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Dec 19th 2008, 04:44 PM
  3. Divisibility (gcd) 9
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Dec 19th 2008, 01:12 PM
  4. Divisibility (gcd) 8
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: Dec 19th 2008, 03:53 AM
  5. Divisibility
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Dec 14th 2008, 09:24 AM

Search Tags


/mathhelpforum @mathhelpforum