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...