# Thread: diophantine equation 3 variables

1. ## 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...

2. ## 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$.

3. ## 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 ?

4. ## 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.

5. ## Re: diophantine equation 3 variables

$\displaystyle 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 $\displaystyle 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).

6. ## Re: diophantine equation 3 variables

Originally Posted by HallsofIvy
$\displaystyle 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 $\displaystyle 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}$