Results 1 to 6 of 6
Like Tree1Thanks
  • 1 Post By SlipEternal

Thread: diophantine equation 3 variables

  1. #1
    Newbie
    Joined
    Aug 2017
    From
    Linkooping
    Posts
    4

    diophantine equation 3 variables

    Hello everyone!

    I am currently studying for a test that is in two weeks but I am having a difficult time with diophantine equations.

    31|(5a+7b+11c) where a,b,c being positive integers


    This is the first three variable diophantine equation I have encountered. Usually the two variable ones are not a problem but this I just can't solve...
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Nov 2010
    Posts
    2,602
    Thanks
    990

    Re: diophantine equation 3 variables

    $5a+7b+11c \equiv 0 \pmod{31}$

    $5a \equiv -7b-11c \pmod{31}$

    $a \equiv (5^{-1})(-7b-11c) \pmod{31}$

    $a \equiv 11b+4c \pmod{31}$

    So, for any integer values of $b,c$, you have $a \equiv 11b+4c \pmod{31}$.

    Let's try it for $b=c=1$. Then $a\equiv 15 \pmod{31}$

    Let's try it out:

    $5\cdot 15+7+11 = 93 = 3\cdot 31$.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Aug 2017
    From
    Linkooping
    Posts
    4

    Re: diophantine equation 3 variables

    Thank you for a quick response! Almost all of it makes perfect sense. I am however still a bit confused over the the fourth row. How does this step work?

    I guess that 5^-1 isn't the same as (-7b-11c)/5 ?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Nov 2010
    Posts
    2,602
    Thanks
    990

    Re: diophantine equation 3 variables

    You need to find which number times $5$ is congruent to $1$ mod 31. If you do not know how to calculate it by hand, a quick way is to try it in wolfram alpha. If you do not have access to that, you can find it with Excel. In cell A1, enter the formula:
    =MOD(5*ROW(),31)

    Copy that to cells A1:A30. Find the entry that says 1. That row number is the multiplicative inverse of 5 (mod 31). It turns out that $5\cdot 25 \equiv 1 \pmod{31}$. Next, you find $25\cdot (-7) \pmod{31}$ and $25\cdot (-11) \pmod{31}$. Those residues are 11 and 4 respectively.
    Thanks from soakn
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    Apr 2005
    Posts
    19,181
    Thanks
    2816

    Re: diophantine equation 3 variables

    5^{-1} mod 31 is the number, x, such that 5x= 1 (mod 31). There is no integer x such that 5x= 1. There is no integer x such that 5x= 31+ 1= 32. There is no integer x such that 5x= 2(31)+ 1= 63. There is no integer x such that 5x= 3(31)+ 1= 94. But there is integer x such that 5x= 4(31)+ 1= 125. That x is 25. So a= (5)^{-1}(-7b- 11c)= -(25(7b+ 11c)= -(174b+ 2950c)= -(5(31)+ 19)b+ (95(31)+ 5)c= -(19b+ 5c)= -19b- 5c
    -19= 31- 19= 12 (mod 31) and -5= 31- 5= 26 (mod 31). So a= 12b+ 26c (mod 31).
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Nov 2010
    Posts
    2,602
    Thanks
    990

    Re: diophantine equation 3 variables

    Quote Originally Posted by HallsofIvy View Post
    5^{-1} mod 31 is the number, x, such that 5x= 1 (mod 31). There is no integer x such that 5x= 1. There is no integer x such that 5x= 31+ 1= 32. There is no integer x such that 5x= 2(31)+ 1= 63. There is no integer x such that 5x= 3(31)+ 1= 94. But there is integer x such that 5x= 4(31)+ 1= 125. That x is 25. So a= (5)^{-1}(-7b- 11c)= -(25(7b+ 11c)= -(174b+ 2950c)= -(5(31)+ 19)b+ (95(31)+ 5)c= -(19b+ 5c)= -19b- 5c
    -19= 31- 19= 12 (mod 31) and -5= 31- 5= 26 (mod 31). So a= 12b+ 26c (mod 31).
    Let's try with b=c=1.
    That gives $a \equiv 12+26 \pmod{31}$, so $a \equiv 7 \pmod{31}$.

    31 does not divide $5\cdot 7 + 7 + 11 = 53$. There is an error somewhere.

    I think it is $-(25(7b+11c)) = -(175b+275c) = -((5(31)+20)b+(8(31)+27)c) \equiv -(20b+27c) \pmod{31}$

    31-20 = 11 and 31-27 = 4, so:

    $a \equiv 11b+4c \pmod{31}$
    Last edited by SlipEternal; Aug 2nd 2017 at 01:48 PM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Linear diophantine equation - 7 variables
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: Jun 26th 2017, 01:39 PM
  2. yet another Diophantine equation
    Posted in the Number Theory Forum
    Replies: 12
    Last Post: Sep 7th 2011, 06:48 AM
  3. Diophantine equation .
    Posted in the Number Theory Forum
    Replies: 16
    Last Post: Jan 9th 2011, 05:06 AM
  4. Diophantine equation
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: Jul 7th 2010, 06:18 AM
  5. diophantine equation
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Jun 3rd 2009, 05:08 AM

Search Tags


/mathhelpforum @mathhelpforum