Results 1 to 3 of 3

Math Help - 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)
    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
    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 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.
    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: December 20th 2008, 02:41 AM
  2. Divisibility (gcd) 10
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: December 19th 2008, 04:44 PM
  3. Divisibility (gcd) 9
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: December 19th 2008, 01:12 PM
  4. Divisibility (gcd) 8
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: December 19th 2008, 03:53 AM
  5. Divisibility
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: December 14th 2008, 09:24 AM

Search Tags


/mathhelpforum @mathhelpforum