Lesson Solving Diophantine equations

Solving Diophantine equations

Problem 1

14mn = 55 - 7m - 2n.


Rewrite it in the form

    14mn +7m + 2n = 55


Rewrite it one more time in this for

    14mn + 7m + 2n + 1 = 56


Rewrite it again in THIS form

    (7m + 1)*(2n + 1) = 56.


56 has the following pairs of divisors

    (1,56)  (2,28),  (4,14), (7,8), (8,7), (14,4), (28,2), (56,1).    (*)


The formal way to follow is, for each of these pair, write the system of equations (for example, for the pair (4,14)

    7m + 1 =  4
    2n + 1 = 14

and solve it; then leave only those solutions that are integer numbers.


Another way is to notice that the factor (2n+1) is an odd number, and try to find an odd divisors from the list.


In this way, there are pairs (1,56), (7,8), (8,7), and (56,1) with odd members.

The pairs (1,56) and (56,1) give  2n+1 = 1 and 7m+1 = 56; hence,  n= 0, but m = (56-1)/7 is not integer.

The pairs (7,8) and (8,71) give  2n+1 = 7 and 7m+1 = 8; hence,  n= 3 and m = 1, and this solution PERFECTLY WORKS.


ANSWER.  The pair (m,n) is (1,3).

Problem 2

The simplest/quickest way to find this "other" pair is to write  x = 

place this formula to Excel spreadsheet and run y = 1, 2, 3, . . . until you get integer positive value of x.



Doing this way, you will find the "other" pair  (x,y) = (17,20).    ANSWER


CHECK.  19*17 + 83*20 = 1983.



Another way to solve the problem is to notice that if (x',y') is another solution to 19x'+ 83y' = 1983,

then  19(x-x') + 83(y-y') = 0.



Then, since 19 and 83 are mutually prime integer numbers, it implies that

    x-x' = 83k,  y-y' = -19k,   with integer k = 0, +/-1, +/-2. . . . 

or

    x' = x - 83k,  y' = y + 19k,   with integer k = 0, +/-1, +/-2. . . . 



So, if we want to get "other" solution with positive (x',y'), we take k = 1, and then we get

    x' = 100-83 = 17,  y' = 1 + 19 = 20.



Thus, using this reasoning and doing this way, we obtain the same solution (17,20), 
which we got above using Excel procedure.

Problem 3

Let x be the number of the luxury units;

    y be the number of the superior units.


Then the number of the deluxe units is 24 - x - y.


Assuming maximum accommodation (fulfillment) of the units, we write this equation


    8x + 7y + 5*(24-x-y) = 160.


We simplify it


    8x + 7y + 120 - 5x - 5y = 160

    3x + 2y = 160 - 120

    3x + 2y = 40

     x      = .


We want have x and y as integer numbers.  It gives for  x  and  y  these values  (see the TABLE)


    T    A    B    L    E

     x        y        z
  luxury   superior   deluxe
---------------------------

     12       2       10

     10       5        9

      8       8        8

      6      11        7

      4      14        6

      2      17        5

      0      20        4


In parallel, we fill the column for z = 24 - x - y.


We do it until we have non-negative values for x, y, and z.


This list in the table is the FULL SET of all possible solutions to the given problem.     ANSWER

Problem 4

Let the numbers of pieces of $2, $5, and $10 notes be, respectively, x, y, and z. 
Then you have this system of two equations in three unknowns

     x  + y +  z  = 13,     (1)
    2x + 5y + 10z = 67.     (2)


You should find a solution / (solutions) in integer non-negative numbers.


Multiply first equation by 2

    2x + 2y +  2z = 26,     (1')
    2x + 5y + 10z = 67.     (2)


Subtract equation (1') from equation (2).  You will get

         3y +  8z = 41.     (3)


This equation is in two unknowns, but you need to solve it in integer non-negative numbers.


Under this restriction, this equation is so called linear Diophantine equation.
A standard way to solve it is "trial and error".
In other words, you should try several integer positive values of z, 
and find relevant values of y. Those values of z that provide non-negative integer y will be the solutions.

From equation (3), the candidates for z to try are z = 1, 2, 3, 4, and 5 - - - only five values,
so it is not a catastrophic job to try all five.


To facilitate this job, people usually make a Table such as I provide below


    z        41-8z              is y = 41-8z           Integer solution
                                a multiple of 3 ?      y = 
    ----------------------------------------------------------------------------

    1   41-8*1 = 41- 8 = 33           Yes                  11

    2   41-8*2 = 41-16 = 25           No

    3   41-8*3 = 41-24 = 17           No

    4   41-8*4 = 41-32 =  9           Yes                   3

    5   41-8*5 = 41-40 =  1           No


From the Table, you see that there are exactly two solutions to equation (3) for y and z.

One solution is        (y,z) = (11,1).  The corresponding value of x, from (1), is x= 13 - y - z = 13 - 11 - 1 = 1.

The other solution is  (y,z) =  (3,4).  The corresponding value of x, from (1), is x= 13 - y - z = 13 - 3 - 4 = 6.


At this point, the problem is just solved, in full.


ANSWER.  There are two solutions.
         One solution is       (one $2 note,  eleven $5 notes and one  $10 note).
         The other solution is (six $2 notes, three  $5 notes and four $10 notes).


You can easily CHECK it on your own that these numbers satisfy to all problem's requirements.

Problem 5

Starting equation is 

     = 0.


Factor 14399 = .  Re-write equation in this equivalent form

     = .


Right side is divisible by 7, and one term in the left side is multiple of 7;
hence, the term  is divisible by 7.


So, I write y = 7z, where z is some positive integer number.

    I can not write x = 7z, since then the degree of 7 will be too great on the left side.


Then the last equation takes the form

     = ,  or

     = .


Cancel factor 7 in both sides and get

     = ,

     = .


Recall about the uniqueness of decomposition of integer numbers into the product of primes.

It implies  that  x= 11.


Then  7z^2 - x = 17;  7z^2 - 11 = 17;  7z^2 = 17 + 11 = 28;  z^2 = 28/7 = 4;  z=  = 2.


Thus x= 11;  z= 2.  Hence, y = 7z = 7*2 = 14.


ANSWER.  x= 11,  y= 14.

Problem 6

Starting equation is 

    4x + 4xy + 4y = 260.


Divide both sides by 4

    x + y + xy = 65.


Make a trick:  add 1 to both sides

    1 + x + y + xy = 66.


and factor left side

    (1+x)*(1+y) = 66.



In integer non-negative numbers, it means that "EITHER OR"

    (a)  1+x = 1,  1+y = 66  --->  x = 0,  y = 65,  x+y = 65;

    (b)  1+x = 2,  1+y = 33  --->  x = 1,  y = 32,  x+y = 33;

    (c)  1+x = 3,  1+y = 22  --->  x = 2,  y = 21,  x+y = 23;

    (d)  1+x = 6,  1+y = 11  --->  x = 5,  y = 10,  x+y = 15

    plus 4 other symmetric cases that do not add new values of x+y.



In integer negative numbers, it means that "EITHER OR"

    (a)  1+x = -1,  1+y = -66  --->  x = -2,  y = -67,  x+y = -69;

    (b)  1+x = -2,  1+y = -33  --->  x = -3,  y = -35,  x+y = -38;

    (c)  1+x = -3,  1+y = -22  --->  x = -4,  y = -23,  x+y = -27;

    (d)  1+x = -6,  1+y = -11  --->  x = -7,  y = -12,  x+y = -19

    plus 4 other symmetric cases that do not add new values of x+y.


So, the answer to the problem question is that possible values of x+y are 15, 23, 33, 65, -69, -38, -27, -19.

Problem 7

 +  = 9216 = 96^2.       (1)


Therefore,   =  - .    (2)


Hence,   = (y+96)*(y-96).      (3)


Thus,   is the product of integers y+96 and y-96.


From it, we conclude that  y+96 and y-96 are degrees of 2.

So, we write

    y + 96 = 

    y - 96 = 


with integer non-negative n and m, and we understand that m < n.  
Subtracting the lower equation from the upper one, we get

     -  = 192,

      = 192 = 64*3 = .   (4)


From it, we conclude that  m = 6, n-m = 2;  hence n-6 = 2,  n = 8.


Thus    y+96 =  =  = 256;  hence  y = 256-96 = 160.

CHECK:  y-96 =  =  = 64;  hence  y = 64+96 =160.   <<<---===  Check says OK.


Now  from (3)  

     = (y+96)*(y-96) = (160+96)*(160-96) = 16384 = ,


Hence,  x = 14.


ANSWER.  This problem has two solutions  (x,y) = (14,160)  and  (x,y) = (14,-160).


From where the second, negative value of y came ?


Since right side of equation (1) is y^2, it is clear that with positive solution y= 160,
negative solution y= -160 works, too.


Where we missed it in our reasoning ? - Because in (4), we could take NEGATIVE factors    and  -3 
into consideration.  It would lead us to the negative value of y.

But since we just caught this second solution, we shouldn't worry anymore.

Problem 8

It is assumed that a, b, c are integer numbers.


From   +  +  = 14  we guess one solution

    a= 3,  b= 2,  c= 1.


Indeed,  then

    3 + 2 + 1 = 6

and

    3^2 + 2^2 + 1^2 = 9 + 4 + 1 = 14.


So, (a,b,c) = (3,2,1) is the basic solution.


There are 5 other solutions that are permutations of the basic triple.


But we should not worry about permutations, since they do not make influence on
the sum   +  + .


Also, it is clear from the equation for squares, that there are no other solutions in integer numbers.


Now we make direct calculation   +  +  =  +  +  = 6818.


ANSWER.  Under given conditions, the sum   +  +   is  6818.