Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

A problem of number theory

  1. Jun 10, 2004 #1
    Hi again,

    how about the below problem, please give me advice.

    Let x and y be possitive integers such that 3x+7y is divisible by 11. Which of the following must also be divisible by 11
    A. 4x+6y
    B. x+y=5
    C. 9x+4y
    D .4x-9y
    E. x+y-1
  2. jcsd
  3. Jun 10, 2004 #2

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    my advice is to learn about the highest common factor, or greatest common divisor, and the ideal (gcd(x,y))=(d)={ax+by | a,b in Z}, oh, and notice at least on of them is of a different kind of expression than the others and isnt' even an integer, heck, isn't even a number.
  4. Jun 10, 2004 #3

    Option B cannot be a valid one since its an equation (pls check).

    As 3x + 7y is divisible by 11,

    3x + 7y = 11k (for some k)

    Clearly, multiples of this "equation" will also be divisible by 11. I can't comment further until you check the validity of the options....

  5. Jun 10, 2004 #4
    Yeah Matts right; the GCD idea didn't strike me though :-)

    Last edited: Jun 10, 2004
  6. Jun 10, 2004 #5
    Hi there,

    I found that we could deduce as following.
    3x+7y =0 (mod 11)
    <=> 8x+4y=0 (mod 11)
    <=> 4x+2y=0 (mod 11)
    <=>4x-9y=0 (mod 11)

    So the answer is D

    Thank so much for all your help,
  7. Jun 10, 2004 #6


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    In general, 8x+4y==0 does not imply that 4x+2y==0. But this is true mod an odd number, which is why it works for 11. You probably knew this when you went through that step. If you didn't, this is just a reminder to be careful when you divide !

    Your answer is correct.
  8. Jul 1, 2004 #7
    i too am taking a number theory course and we have just started with modulos. i had a heck of a time learning it until i came here. i think i can do better when i am explaining the info to someone else thus making me remember the information.

    BTW!!! i plan on being a future teacher in mathematics. are there any posts that are devoted to teachers and all? :confused:
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook