Lesson Solving Diophantine equations
Algebra
->
Divisibility and Prime Numbers
->
Lessons
-> Lesson Solving Diophantine equations
Log On
Algebra: Divisibility and Prime Numbers
Section
Solvers
Solvers
Lessons
Lessons
Answers archive
Answers
Source code of 'Solving Diophantine equations'
This Lesson (Solving Diophantine equations)
was created by by
ikleyn(52908)
:
View Source
,
Show
About ikleyn
:
<H2>Solving Diophantine equations</H2> <H3>Problem 1</H3>Find the ordered pair (m,n), where m,n are positive integers satisfying the following equation 14mn = 55 - 7m - 2n. <B>Solution</B> <pre> 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. <B>ANSWER</B>. The pair (m,n) is (1,3). </pre> <H3>Problem 2</H3>If x = 100 and y = 1, then 19x + 83y = 1983. There is exactly one other pair of positive integers x and y, for which this equation is true. What is this pair of integers? <B>Solution</B> <pre> The simplest/quickest way to find this "other" pair is to write x = {{{(1983-83y)/19}}} 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). <U>ANSWER</U> <U>CHECK</U>. 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. </pre> <H3>Problem 3</H3>In a block of flats there are 24 units of 3 types: the luxury unit, the superior unit and deluxe unit. The luxury can accommodate 8 people, the superior unit can accommodate 7 people and deluxe can accommodate 5 people. Given that the total number of people living in this block is 160, how many of each type are there? <B>Solution</B> <pre> 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 = {{{(40-2y)/3}}}. 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. <U>ANSWER</U> </pre> <H3>Problem 4</H3>Alan has 13 pieces of $2, $5 and $10 notes in his wallet. If the amount of money he has is $67, how many pieces of each note does he have ? <B>Solution</B> Here I'd like to present a regular solution to this problem. Not the most witty and not the most slow, but something REGULAR, which is in between of these extremes. <pre> 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 = {{{(41-8z)/3}}} ---------------------------------------------------------------------------- 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. <U>ANSWER</U>. 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. </pre> ------------------- In this problem, making " trial and errors " is dowable procedure. In other similar problems, if the number of " trials and errors " is great, you may use the tools like Excel to facilitate such a job and to make a calculation Table quickly. In any case, what is presented here, is traditionally considered as a standard procedure to solve similar problems. Again, as a reminder, originally you have only two equations for three unknowns. But an additional restriction of having non-negative integer solutions reduces the possible number of solutions from infinity to a finite number. <H3>Problem 5</H3>Solve equation {{{7x^3 - x^2y^2 + 14399}}} = 0 in positive integer numbers x and y. <B>Solution</B> <pre> Starting equation is {{{7x^3 - x^2*y^2 + 14399}}} = 0. Factor 14399 = {{{7*11^2*17}}}. Re-write equation in this equivalent form {{{x^2*y^2 - 7x^3}}} = {{{7*11^2*17}}}. Right side is divisible by 7, and one term in the left side is multiple of 7; hence, the term {{{x^2*y^2}}} 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 {{{x^2*(7z)^2 - 7x^3}}} = {{{7*11^2*17}}}, or {{{x^2*7^2*z^2 - 7x^3}}} = {{{7*11^2*17}}}. Cancel factor 7 in both sides and get {{{7x^2*z^2 - x^3}}} = {{{11^2*17}}}, {{{x^2*(7z^2-x)}}} = {{{11^2*17}}}. 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= {{{sqrt(4)}}} = 2. Thus x= 11; z= 2. Hence, y = 7z = 7*2 = 14. <U>ANSWER</U>. x= 11, y= 14. </pre> <H3>Problem 6</H3>If 4x + 4xy + 4y = 260, where x and y are integer numbers, find all possible values of x+y. <B>Solution</B> <pre> 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. </pre> <H3>Problem 7</H3>If {{{2^13}}} + {{{2^10}}} + {{{2^x}}} = {{{y^2}}}, find the solutions x and y in integer numbers. <B>Solution</B> <pre> {{{2^13}}} + {{{2^10}}} = 9216 = 96^2. (1) Therefore, {{{2^x}}} = {{{y^2}}} - {{{96^2}}}. (2) Hence, {{{2^x}}} = (y+96)*(y-96). (3) Thus, {{{2^x}}} 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 = {{{2^n}}} y - 96 = {{{2^m}}} with integer non-negative n and m, and we understand that m < n. Subtracting the lower equation from the upper one, we get {{{2^n}}} - {{{2^m}}} = 192, {{{2^m*(2^(n-m)-1)}}} = 192 = 64*3 = {{{2^6*3}}}. (4) From it, we conclude that m = 6, n-m = 2; hence n-6 = 2, n = 8. Thus y+96 = {{{2^n}}} = {{{2^8}}} = 256; hence y = 256-96 = 160. <U>CHECK</U>: y-96 = {{{2^m}}} = {{{2^6}}} = 64; hence y = 64+96 =160. <<<---=== Check says OK. Now from (3) {{{2^x}}} = (y+96)*(y-96) = (160+96)*(160-96) = 16384 = {{{2^14}}}, Hence, x = 14. <U>ANSWER</U>. 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 {{{-2^6}}} 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. </pre> <H3>Problem 8</H3>For this given system of equations in integer numbers a + b + c = 6, {{{a^2}}} + {{{b^2}}} + {{{c^2}}} = 14, find the value of {{{a^8}}} + {{{b^8}}} + {{{c^8}}}. <B>Solution</B> <pre> It is assumed that a, b, c are integer numbers. From {{{a^2}}} + {{{b^2}}} + {{{c^2}}} = 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 {{{a^8}}} + {{{b^8}}} + {{{c^8}}}. Also, it is clear from the equation for squares, that there are no other solutions in integer numbers. Now we make direct calculation {{{a^8}}} + {{{b^8}}} + {{{c^8}}} = {{{3^8}}} + {{{2^8}}} + {{{1^8}}} = 6818. <U>ANSWER</U>. Under given conditions, the sum {{{a^8}}} + {{{b^8}}} + {{{c^8}}} is 6818. </pre> My other lessons in this site on miscellaneous problems on divisibility of integer numbers are - <A HREF=https://www.algebra.com/algebra/homework/divisibility/lessons/Light-flashes-on-a-Christmas-tree-and--a-Least-Common-Multiple.lesson>Light flashes on a Christmas tree and a Least Common Multiple</A> - <A HREF=http://www.algebra.com/algebra/homework/divisibility/lessons/The-number-that-leaves-a-remainder-1-when-divided-by-2-by-3-by-4-by-5-and-so-on-until-9.lesson>The number that leaves a remainder 1 when divided by 2, by 3, by 4, by 5 and so on until 9</A> - <A HREF=https://www.algebra.com/algebra/homework/divisibility/The-number-rem4-mod7-rem5-mod8-and-rem6-mod9.lesson>The number which gives remainder 4 when divided by 7, remainder 5 when divided by 8 and remainder 6 when divided by 9</A> - <A HREF=https://www.algebra.com/algebra/homework/divisibility/Introductory-problems-on-divisibility-numbers.lesson>Introductory problems on divisibility of integer numbers</A> - <A HREF=https://www.algebra.com/algebra/homework/divisibility/lessons/Finding-Greatest-Common-Divisor-of-integer-numbers.lesson>Finding Greatest Common Divisor of integer numbers</A> - <A HREF=http://www.algebra.com/algebra/homework/divisibility/lessons/Relativity-prime-numbers-help-to-solve-the-problem.lesson>Relatively prime numbers help to solve problems</A> - <A HREF=https://www.algebra.com/algebra/homework/divisibility/lessons/Solving-equations-in-integer-numbers.lesson>Solving equations in integer numbers</A> - <A HREF=https://www.algebra.com/algebra/homework/divisibility/lessons/Quadratic-polynomial-with-odd-integer-coefs-can-not-have-a-rational-root.lesson>Quadratic polynomial with odd integer coefficients can not have a rational root</A> - <A HREF=https://www.algebra.com/algebra/homework/divisibility/Proving-the-equation-has-no-integer-solutions.lesson>Proving an equation has no integer solutions</A> - <A HREF=https://www.algebra.com/algebra/homework/divisibility/lessons/Composite-number-of-the-form-%284n%2B3%29-must--have-a-prime-divisor-of-the-form-%284n%2B3%29.lesson>Composite number of the form (4n+3) must have a prime divisor of the form (4n+3)</A> - <A HREF=https://www.algebra.com/algebra/homework/divisibility/lessons/Problems-on-divisors-of-a-given-number.lesson>Problems on divisors of a given number</A> - <A HREF=https://www.algebra.com/algebra/homework/divisibility/lessons/How-many-three-digit-numbers-are-multiples-of-both-5-and-7.lesson>How many three-digit numbers are multiples of both 5 and 7?</A> - <A HREF=https://www.algebra.com/algebra/homework/divisibility/lessons/How-many-3-digit-numbers-are-not-dvsbl-by-2-not-dvsbl-by-3-notdvsbl-by-either-2-or-3.lesson>How many 3-digit numbers are not divisible by 2; not divisible by 3; not divisible by either 2 or 3</A> - <A HREF=https://www.algebra.com/algebra/homework/divisibility/lessons/How-many-integer-numbers-in-the-range-1-300-are-divisible-by.lesson>How many integer numbers in the range 1-300 are divisible by at least one of the integers 4, 6 and 15 ?</A> - <A HREF=https://www.algebra.com/algebra/homework/divisibility/lessons/Find-the-remainder-of-division.lesson>Find the remainder of division </A> - <A HREF=https://www.algebra.com/algebra/homework/divisibility/lessons/Why-3%5En%2B7%5En-2-is-divisible-by-8-for-all-positive-integer-n.lesson>Why 3^n + 7^n - 2 is divisible by 8 for all positive integer n ?</A> - <A HREF=https://www.algebra.com/algebra/homework/divisibility/What-is--the-last-digit-of-the-number-a%5En.lesson>What is the last digit of the number a^n ?</A> - <A HREF=https://www.algebra.com/algebra/homework/divisibility/lessons/Find-the-last-three-digits-of-these-numbers.lesson>Find the last three digits of these numbers</A> - <A HREF=https://www.algebra.com/algebra/homework/divisibility/lessons/Find-the-two-last-digits-of-the-number-3%5E123%2B7%5E123%2B9%5E123.lesson>Find the last two digits of the number 3^123 + 7^123 + 9^123</A> - <A HREF=https://www.algebra.com/algebra/homework/divisibility/Find-the-last-two-digits-of-%281%21-%2B-2%21-%2B-3%21-%2B-%2B-2024%21%29%5E2024.lesson>Find the last two digits of (1! + 2! + 3! + ... + 2024!)^2024</A> - <A HREF=https://www.algebra.com/algebra/homework/divisibility/lessons/Find-n-th-term-of-a-sequence.lesson>Find n-th term of a sequence</A> - <A HREF=https://www.algebra.com/algebra/homework/divisibility/lessons/Determine-the-number-of-integer-solutions-to-equation-n%5E2%2B18n%2B3=m%5E2.lesson>How many integers of the form n^2 + 18n + 13 are perfect squares</A> - <A HREF=https://www.algebra.com/algebra/homework/divisibility/lessons/Miscellaneous-problems-on-divisibility-numbers.lesson>Miscellaneous problems on divisibility numbers</A> - <A HREF=https://www.algebra.com/algebra/homework/divisibility/lessons/Find-the-sum-of-digits-of-integer-numbers.lesson>Find the sum of digits of integer numbers</A> - <A HREF=https://www.algebra.com/algebra/homework/divisibility/lessons/Two-digit-numbers-with-digit-9.lesson>Two-digit numbers with digit "9"</A> - <A HREF=https://www.algebra.com/algebra/homework/divisibility/lessons/Find-a-triangle-with-integer-side-lengths-and-integer-area.lesson>Find a triangle with integer side lengths and integer area</A> - <A HREF=https://www.algebra.com/algebra/homework/divisibility/lessons/Math-circle-level-problem-on-the-hundred-handed-monster-Briareus.lesson>Math circle level problem on the hundred-handed monster Briareus</A> - <A HREF=https://www.algebra.com/algebra/homework/divisibility/lessons/Math-Citcle-level-problem-on-lockers-and-divisors.lesson>Math Circle level problem on lockers and divisors of integer numbers</A> - <A HREF=https://www.algebra.com/algebra/homework/divisibility/lessons/Nice-entertaiment-problem-What-numbers-John-is-thinking-about.lesson>Nice entertainment problems related to divisibility property</A> - <A HREF=https://www.algebra.com/algebra/homework/divisibility/lessons/Solving-problems-on-modular-arithmetic.lesson>Solving problems on modular arithmetic</A> - <A HREF=https://www.algebra.com/algebra/homework/divisibility/lessons/Using-the-little-Fermat-theorem-to-solve-a-problem-on-modular-arithmetic.lesson#google_vignette>Using the little Fermat's theorem to solve a problem on modular arithmetic</A> - <A HREF=https://www.algebra.com/algebra/homework/divisibility/lessons/OVERVIEW-of-miscellanious-solved-problems-on-divisibility-of-numbers.lesson>OVERVIEW of miscellaneous solved problems on divisibility of integer numbers</A>
