1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Basic Divisibility

  1. Jul 8, 2004 #1
    I am reading Naoki Sato's notes on Number Theory:
    http://donut.math.toronto.edu/~naoki/nt.pdf

    I am on page 2, and doing Example 1.1...

    "Let x and y be integers. Prove that 2x+3y is divisible by 17 iff 9x+5y is divisible by 17."

    There's ALREADY A SOLUTION on the book, but I do not understand it. I've read the theorems and also the other examples and found that I can understand them. I guess this one is different.

    Can somebody please explain it to me clearer...??

    Thanks.
     
  2. jcsd
  3. Jul 8, 2004 #2
    Assuming you know some basic things about congruences... If 2x + 3y is divisible by 17, then 2x + 3y == 0 (mod 17). Multiply both sides by 13 to get

    13(2x + 3y) == 13(0) (mod 17)
    <=>
    26x + 39y == 0 (mod 17) ... (1)

    But 26 == 9 (mod 17) and 39 == 5 (mod 17), så equation (1) is equivalent to

    9x + 5y == 0 (mod 17).

    Thus 9x + 5y is divisible by 17.

    The other implication, that if 9x + 5y is divisible by 17 then 2x + 3y is divisible by 17, can be proved in a similar fashion.

    *edit* After inspection of the PDF, I see that it doesn't use congruences at all. Right, if 2x + 3y is divisible by 17, there is an integer k such that (2x + 3y)/17 = k <=> 2x + 3y = 17k. Multiply both sides by 13 and do some algebra magic (trying to be as clear as possible):

    13(2x + 3y) = 13 * 17k
    <=>
    26x + 39y = 13 * 17k
    <=>
    9x + 5y + (17x + 34y) = 13 * 17k
    <=> (moving over the thing in the parantheses to the right-hand side and factoring out 17
    9x + 5y = 13 * 17k - (17x + 34y) = 13 * 17k - 17(x + 2y) = 17(13k - (x + 2y))

    Thus 9x + 5y is divisible by 17.
     
    Last edited: Jul 8, 2004
  4. Jul 8, 2004 #3
    oh, great thanks..
    you cleared it up beautifully...

    i love this forum ;)
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Basic Divisibility
  1. Divisibility question (Replies: 12)

  2. Divisibility Question (Replies: 6)

  3. Division ring (Replies: 0)

Loading...