Results 1 to 4 of 4
Like Tree1Thanks
  • 1 Post By emakarov

Math Help - Basic number theory problem

  1. #1
    Newbie
    Joined
    Jul 2012
    From
    Hanoi
    Posts
    3

    Basic number theory problem

    Let x and y be integers. Prove that 2x + 3y is divisible
    by 17 iff 9x + 5y is divisible by 17.
    Solution. 17 | (2x + 3y) ⇒ 17 | [13(2x + 3y)], or 17 | (26x + 39y) ⇒
    17 | (9x + 5y), and conversely, 17 | (9x + 5y) ⇒ 17 | [4(9x + 5y)], or
    17 | (36x + 20y) ⇒ 17 | (2x + 3y)

    Could someone please help me understand this solution. I do not understand it at all. What basis do they have for doing such operations? The solution just doesn't make sense

    Savvycom software
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,545
    Thanks
    780

    Re: Basic number theory problem

    Quote Originally Posted by susan12 View Post
    Solution. 17 | (2x + 3y) ⇒ 17 | [13(2x + 3y)], or 17 | (26x + 39y) ⇒ 17 | (9x + 5y)
    Perhaps the unclear step is 17 | (26x + 39y) ⇒ 17 | (9x + 5y). The reason is that 26x = 17x + 9x and 39y = 2 * 17y + 5y. So, if 26x + 39y = 17k for an integer k, then 9x + 5y + 17(x + 2y) = 17k and thus 9x + 5y = 17(k - x - 2y).
    Thanks from Deveno
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member
    Joined
    Jun 2012
    From
    AZ
    Posts
    616
    Thanks
    97

    Re: Basic number theory problem

    You can freely add/subtract multiples of 17. From 17 | (26x + 39y) \Rightarrow 17 | 9x + 5y, the writer subtracted 17x + 34y, which is valid (because it is congruent to 0 (mod 17)).
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,401
    Thanks
    762

    Re: Basic number theory problem

    for emphasis:

    suppose p (a positive integer) divides a+b and p divides a. then p must also divide b.

    p divides a+b means a+b = kp, for some integer k.

    p divides a means a = mp, for some integer m.

    so then b = (a+b) - a = kp - mp = (k - m)p, and surely k - m is an integer if k and m are, so p divides b.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Number Theory problem
    Posted in the Number Theory Forum
    Replies: 15
    Last Post: June 29th 2010, 08:04 AM
  2. Basic number problem
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: May 14th 2010, 10:43 PM
  3. Basic number theory
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: December 21st 2009, 03:37 PM
  4. Basic Number Theory
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: November 2nd 2009, 09:21 PM
  5. Replies: 2
    Last Post: December 18th 2008, 05:28 PM

Search Tags


/mathhelpforum @mathhelpforum