Results 1 to 10 of 10

Math Help - A number theory puzzle

  1. #1
    Banned
    Joined
    Oct 2009
    Posts
    769

    A number theory puzzle

    I give you 7x - 17y = 1. Now give me back how many solution pairs (in natural numbers) there are for the equation? For example (5,2) and (22,9) are solutions (if you can't figure this one out in a week, I'll drop a hint and if you still can't solve it after another week, then I'll solve it for you).
    Last edited by wonderboy1953; September 15th 2010 at 06:25 AM. Reason: correction
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by wonderboy1953 View Post
    I give you 7x - 7y = 1. Now give me back how many solution pairs (in natural numbers) there are for the equation? For example (5,2) and (22,9) are solutions (if you can't figure this one out in a week, I'll drop a hint and if you still can't solve it after another week, then I'll solve it for you).
    Typo? 7*5 - 7*2 most definitely does not equal 1.

    In fact it is easily shown that 7x - 7y = 1 has no integer solutions; the LHS is a multiple of 7 while the RHS is not.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Banned
    Joined
    Oct 2009
    Posts
    769
    Quote Originally Posted by undefined View Post
    Typo? 7*5 - 7*2 most definitely does not equal 1.

    In fact it is easily shown that 7x - 7y = 1 has no integer solutions; the LHS is a multiple of 7 while the RHS is not.
    Correction made.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by wonderboy1953 View Post
    I give you 7x - 17y = 1. Now give me back how many solution pairs (in natural numbers) there are for the equation? For example (5,2) and (22,9) are solutions (if you can't figure this one out in a week, I'll drop a hint and if you still can't solve it after another week, then I'll solve it for you).
    We have Bezout's identity with a sign change. There are infinite solutions, and a solution exists iff x > 4 and x\equiv 5\pmod{17}.

    For k \ge 0 we solve for y

    7*(17k + 5) - 17y = 1

    7*17k + 35 - 17y = 1

    17y = 7*17k + 34

    y = 7k + 2

    So the solution set is given by (x,y) = (5 + 17k, 2 + 7k) where k ranges over the non-negative integers.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Banned
    Joined
    Oct 2009
    Posts
    769
    That's the solution using parametric equations.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Dec 2007
    From
    Ottawa, Canada
    Posts
    3,110
    Thanks
    68
    Methinks Sir Diophantine just turned over in his grave.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by Wilmer View Post
    Methinks Sir Diophantine just turned over in his grave.
    I realize my solving for y could be shortened realizing that

    7(x + 17) - 17(y + 7) = 7x - 17y

    but what exactly are you referring to?
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Banned
    Joined
    Oct 2009
    Posts
    769
    Quote Originally Posted by Wilmer View Post
    Methinks Sir Diophantine just turned over in his grave.
    Certainly not English.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,826
    Thanks
    714
    Hello, wonderboy1953!

    I have a very elementary solution . . .


    \text{Given: }\;7x - 17y \:=\: 1

    \text{How many solutions in natural numbers are there for the equation?}

    Answer: there are a brizillian solutions.


    Solve for x\!:\;\;x \:=\:\dfrac{17y+1}{7} \;=\;2y + \dfrac{3y+1}{7}

    Since \,x is a natural number, (3y+1) must be divisible by 7.

    We find that: . y \;=\;2,\,9,\,16,\,\hdots,\,7t-5\;\text{ for }t \in N

    Then: . x \;=\;2(7t-5) + \dfrac{3(7t-5)+1}{7} \;=\;17t - 12


    Solutions: . \begin{Bmatrix}x &=& 17t - 12 \\ y &=& 7t-5 \end{Bmatrix}\;\;\text{ for }t \in N



    Of course, this is basicaly undefined's solution.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor
    Joined
    Dec 2007
    From
    Ottawa, Canada
    Posts
    3,110
    Thanks
    68
    Quote Originally Posted by undefined View Post
    I realize my solving for y could be shortened realizing that
    7(x + 17) - 17(y + 7) = 7x - 17y
    but what exactly are you referring to?
    Nothing in particular UnD; I had just skimmed over:
    Diophantine Equations
    and saw WB's equation...
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Graph Theory Puzzle
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 19th 2010, 01:31 PM
  2. Replies: 0
    Last Post: May 20th 2010, 07:58 AM
  3. Set theory Puzzle
    Posted in the Math Puzzles Forum
    Replies: 4
    Last Post: January 25th 2010, 08:11 AM
  4. puzzle, set theory or statistics or probability
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: December 21st 2009, 04:24 AM
  5. Game Theory - Heuristic for single-player puzzle
    Posted in the Math Challenge Problems Forum
    Replies: 0
    Last Post: March 16th 2008, 01:25 PM

Search Tags


/mathhelpforum @mathhelpforum