Results 1 to 5 of 5

Math Help - Linear Diophantine Equations

  1. #1
    Newbie
    Joined
    Apr 2006
    From
    Sydney Australia
    Posts
    14

    Linear Diophantine Equations

    Hi
    I'm looking for help on solving Linear Diophantine Equation
    15y + 27x = 39

    partial solution

    y = (39-27x)/15

    y = (39 - 12x - 15x)/15

    y = (39 - 12x)/15 - x

    Next step? I'm unsure


    Thanks in advance
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by delpin
    Hi
    I'm looking for help on solving Linear Diophantine Equation
    15y + 27x = 39
    I'm not sure this is how you are expected to solve this, or even if this
    is the simplest method; but:

    First divide through by 3 and rearrange to get:

    <br />
5y+9x-13=0<br />

    Now this gives:

    <br />
4 x -3 \equiv 0 \mod\ 5 <br />

    So there exists an integer \lambda such that:

    <br />
4 x=5\lambda+3<br />

    Now the LHS (left hand side) is even, so \lambda must be odd.
    So let \lambda=2\mu+1, then:

    <br />
4x=10\mu+8<br />

    But the LHS is divisible by 4 so the RHS must also be divisible by
    4 so \mu must be even., so we may write it as \mu=2\kappa, and then:

    <br />
x=5\kappa+2<br />

    Now substituting this back into 5y+9x-13=0 gives:

    <br />
y=-9 \kappa-1<br />

    So we see that for any \kappa \in \mathbb{Z}:

    <br />
x=5\kappa+2
    y=-9 \kappa-1<br />

    is a solution.

    RonL
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Use the following theorem,
    Given a diophatine equation with \gcd(a,b) |c
    ax+by=c
    and x_0,y_0 is a particular solution
    Then all solutions and every solution is,
    x=x_0+\frac{b}{d}t
    y=y_0-\frac{a}{d}t
    for an integer t
    ------
    You have,
    15y+27x=39
    You can leave it the way it is but I suggest to divide by 3,
    5y+9x=13
    You need to find a specific solution. Which can be done with trail and error. (Otherwise you can use the Euclidean Algorithm or Coutinued fractions to get a particular solution).
    We can easily see that y=-1 and x=2 work.
    Also \gcd(5,9)=1 which divides 13.
    Thus, all solutions are,
    y=-1+9t
    x=2-5t

    Note it might look different from CaptainBlack's but they are both equivalent.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Apr 2006
    From
    Sydney Australia
    Posts
    14

    Thank you

    For your help... most appreciated
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,682
    Thanks
    614
    Hello, delpin!

    This is basically Captain Black's and Hacker's solutions ... in baby-talk.

    I'm looking for help on solving Linear Diophantine Equation: 15y + 27x \:= \:39
    First, reduce the equation: . 5y + 9x\:=\:13

    We have: . 9x - 13\;= \;-5y

    . . Then: . 9x \;\equiv \;13 \pmod{5}\quad\Rightarrow\quad 4x\;\equiv\;3 \pmod{5}

    Multiply both sides by 4:
    . . 16x\;\equiv \;12 \pmod{5}\quad\Rightarrow\quad x\;\equiv\;2 \pmod{5}

    Hence: . x\:=\:2 + 5n for some integer n.


    Substitute into the original equation: . 5y + 9(2 + 5n)\:=\:13

    . . and we get: . y\:=\:-(1 + 9n)


    The solutions are: . \begin{Bmatrix}x\:=\:2 + 5n \\ y\:=\:-(1 + 9n)\end{Bmatrix} for any integer n.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Linear Diophantine Equations
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: June 25th 2010, 06:49 PM
  2. Linear Diophantine Equations
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: August 23rd 2009, 07:59 PM
  3. linear diophantine equ.
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: January 27th 2009, 06:49 PM
  4. Linear Diophantine Equations
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: December 9th 2008, 11:31 AM
  5. Linear Diophantine Equations
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: February 26th 2007, 11:24 AM

Search Tags


/mathhelpforum @mathhelpforum