Descent method for solving Diophantine equations. Solution of linear Diophantine equations with any number of unknowns. Problem about paws

Today I propose to reflect on some interesting mathematical problem.
Namely, let's warm up by solving the following linear equation:

"What's hard?" - you ask. Indeed, only one equation and as many as four unknowns. Therefore, three variables are free, and the last one depends on them. So let's express it quickly! For example, through the variable , then the solution set is as follows:

where is the set of any real numbers.

Well, the solution really turned out to be too trivial. Then we will complicate our task and make it more interesting.

Let's remember about linear equations with integer coefficients and integer roots, which, in fact, are a kind of Diophantine equations. Specifically, we will impose on our equation the appropriate restriction on the integer coefficients and roots. The coefficients for the unknowns are already integers (), but the unknowns themselves must be limited to the following:

where is the set of integers.

Now the solution obtained at the beginning of the article will not work, since we risk getting it as a rational (fractional) number. So how do you solve this equation? exclusively in whole numbers?

Interested in solving this problem, I ask under cat.

And we continue with you. Let's try to make some elementary transformations of the desired equation:

The problem still looks incomprehensible, in such cases mathematicians usually make some kind of substitution. Let's bang it with you:

Wow, we have achieved an interesting result! Coefficient with us now equal to one, which means that you and I can express this unknown in terms of the rest of the unknowns in this equation without any divisions (which we sinned at the very beginning of the article). Let's do it:

Let me note that this tells us that no matter what they are (within the framework of Diophantine equations), they will still remain an integer, and this is fine.

Remembering that it is fair to say that . And substituting the result obtained above, we get:

Here we also see that no matter what they are, they will still remain an integer, and this is still fine.

Then a brilliant idea comes to mind: so let's declare as free variables, and we will express through them! In fact, we have already done it. It remains only to write the answer into the solution system:

Now you can see that in the decision system no division anywhere, which means that the solutions will always be integer. Let's try to find a particular solution to the original equation, assuming, for example, that:

Substitute in the original equation:

Same, cool! Let's try again with another example, shall we?

Here we see a negative coefficient, it can give us a fair amount of problems, so let's get rid of sin by replacing it, then the equation will be as follows:

As we remember, our task is to make such transformations so that in our equation there is an unknown with a unit coefficient at it (in order to then express it through the rest without any division). To do this, we must again take something "out of the bracket", the fastest is to take the coefficients from the equation that are closest to unity. However, you need to understand that only the number that is necessarily some coefficient of the equation (no more, no less) can be taken out of the bracket, otherwise we will stumble upon a tautology / contradiction or fractions (in other words, it is impossible for free variables to appear somewhere except for the last change). So:

We introduce a replacement, then we get:

Again, we take it out of the bracket and finally we get the unknown in the equation with a unit coefficient:

We introduce a replacement, then:

Let's express our lonely unknown from here:

It follows from this that no matter what we take, it will still remain an integer. Then we find from the ratio:

Similarly, we find from the relation:

On this, our system of solutions has matured - we have expressed absolutely all the unknowns without resorting to division, thereby showing that the solution will definitely be integer. Also, do not forget that , and we need to introduce a reverse substitution. Then the final system of solutions is as follows:

Thus, it remains to answer the question - can any similar equation be solved in this way? Answer: no, if the equation is in principle unsolvable. This occurs in cases where the free term is not divisible by the GCD of all coefficients for unknowns. In other words, given the equation:

To solve it in integers, it is sufficient to fulfill the following condition:

(where is the greatest common divisor).

Proof

The proof is not considered within the framework of this article, since this is a reason for a separate article. You can see it, for example, in the wonderful book by V. Sierpinsky "On solving equations in integers" in §2.

Summarizing the above, we write an algorithm of actions for solving linear Diophantine equations with any number of unknowns:

In conclusion, it is worth saying that it is also possible to add restrictions on each term of the equation in the form of an inequality on it (then a system of inequalities is added to the solution system, according to which the answer will need to be adjusted), and also add something else interesting. You should also not forget that the solution algorithm is strict and can be written in the form of a computer program.

Peter was with you
thank you for your attention.

Problem 1. Let's say octopuses and starfish live in an aquarium. Octopuses have 8 legs, and starfish have 5. There are 39 legs in total. How many animals are there in the aquarium?

Solution. Let x be the number of starfish and y be the number of octopuses. Then all octopuses have 8 legs, and all stars have 5 legs. Let's make an equation: 5x + 8y = 39.

Note that the number of animals cannot be expressed as non-integer or negative numbers. Therefore, if x is a non-negative integer, then y \u003d (39 - 5x) / 8 must also be integer and non-negative, which means that the expression 39 - 5x must be divisible by 8 without a remainder. A simple enumeration of options shows that this possible only if x = 3, then y = 3. Answer: (3; 3).

Equations of the form ax + bu = c are called Diophantine, after the ancient Greek mathematician Diophantus of Alexandria. Diophantus lived, apparently, in the 3rd century. n. e., the rest of the facts of his biography known to us are exhausted by such a riddle poem, according to legend, engraved on his tombstone:

The ashes of Diophantus the tomb rests; marvel at her and the stone

The age of the departed will tell him with wise art.

By the will of the gods, he lived a sixth of his life as a child.

And he met half of the sixth with fluff on his cheeks.

Only the seventh passed, he got engaged to his girlfriend.

With her, after spending five years, a wise man waited for his son;

His beloved son lived only half his father's life.

He was taken from his father by his early grave.

Twice two years the parent mourned the heavy grief,

Here I saw the limit of my sad life.

How many years did Diophantus of Alexandria live?

Task 2. There are nails in the warehouse in boxes of 16.17 and 40 kg. Can a storekeeper give out 100 kg of nails without opening the boxes? (direct enumeration method)

Let us analyze the method of solving with respect to one unknown.

Task 3. There are 96 paintings in the catalog of the art gallery. On some pages there are 4 paintings, and on some 6. How many pages of each type are there in the catalog?

Solution. Let x be the number of pages with four pictures,

y is the number of pages with six pictures,

We solve this equation with respect to that of the unknowns for which the smallest (modulo) coefficient. In our case, this is 4x, that is:

We divide the whole equation by this factor:

4x=96-6y | :4;

Remainders when divided by 4: 1,2,3. Substitute these numbers for y.

If y=1, then x=(96-6∙1):4=90:4 - Doesn't work, the solution is not in integers.

If y=2, then x=(96-6∙2):4=21 - Suitable.

If y=3, then x=(96-6∙3):4=78:4 - Doesn't work, the solution is not in integers.

So, a particular solution is the pair (21;2), which means that there are 4 pictures on 21 pages, and 6 pictures on 2 pages.

Let's analyze the solution method using the Euclid algorithm.

Problem 4. The store sells two types of chocolate: milk and bitter. All chocolate is stored in boxes. There are 7 boxes of milk chocolate in the warehouse, and 4 of dark chocolate. It is known that there was one more bar of dark chocolate. How many chocolate bars are in each type of box?

Solution. Let x be the number of milk chocolate bars in one box,

y is the number of dark chocolate bars in one box,

Then, according to the condition of this problem, we can write an equation:

Let's solve this equation using Euclid's algorithm.

Express 7=4∙1+3, => 3=7-4∙1.

Express 4=3∙1+1, => 1=4-3∙1=4-(7-4∙1)=4-7+4∙1=4∙ 2 -7∙1 =1.

So, it turns out x=1; y=2.

And this means that milk chocolate is in a box of 1 piece, and bitter is 2 pieces.

Let us analyze the method of searching for a particular solution and the general solution formula.

Problem 5. In the African tribe Tumbe-Yumbe, two natives Tumba and Yumba work as hairdressers, and Tumba always braids 7 braids for his clients, and Yumba 4 braids each. How many clients were served individually by the masters during the shift, if it is known that together they braided 53 pigtails?

Solution. Let x be the number of Tumba customers,

y is the number of Yumba clients,

then 7x+4y=53 (1).

Now, in order to find particular solutions to the equation (,), we replace the sum of numbers given to us by 1. This will greatly simplify the search for suitable numbers. We get:

Let's solve this equation using the substitution method.

4y \u003d 1-7x │: 4;

Remainders when divided by 4: 1, 2, 3. Substitute these numbers instead of x:

If x=1, then y=(1-7):4 is not suitable, because the solution is not in integers.

If x=2, then y=(1-7∙2):4 is not suitable, because the solution is not in integers.

If x=3, then y=(1-7∙3):4=-5 is fine.

Then we multiply the resulting values ​​by the initial value of the sum, which we replaced by 1, i.e.

x=x 0 ∙53=3∙53=159;

y=y 0 ∙53=-5∙53=-265.

We have found a particular solution of equation (1). Let's check it by substituting the initial equation:

7∙159+4∙(-265)=53; (3)

The answer came together. If we were solving an abstract equation, we could stop there. However, we are solving the problem, and since Tumba could not braid a negative number of braids, we need to continue the solution. Now we will write formulas for the general solution. To do this, we subtract from the initial equation (1) the equation with substituted values ​​(3). We get:

Let's take the common factors out of brackets:

7(x-159)+4(y+265)=0.

Let's move one of the terms from one part of the equation to another:

7(x-159)=-4(y+265).

Now it became clear that in order for the equation to be solved (x-159) must be divisible by -4, and (y + 265) must be divisible by 7. Let's introduce the variable n, which will display this our observation:

Let's move the terms from one side of the equation to the other:

We have obtained a general solution to this equation, now we can substitute various numbers into it and get the corresponding answers.

For example, let n=39, then

And this means that Tumba braided pigtails for 3 clients, and Yumba for 8 clients.

Solve problems in various ways.

Task 6: Vovochka bought pens for 8 rubles and pencils for 5 rubles. Moreover, he paid 19 rubles more for all the pencils than for all the pens. How many pens and how many pencils did Little Johnny buy? (method of searching for a general solution, solution for one unknown, using the Euclidean algorithm).

Problem 7. Felt-tip pens were purchased for 7 rubles and pencils for 4 rubles each, totaling 53 rubles. How many felt-tip pens and pencils were bought?

Problem 8. (Municipal tour of VOSH 2014-2015): on planet C, there are two types of coins: 16 tugriks and 27 tugriks each. Is it possible to buy goods with the price of 1 tugrik with their help?

Problem 9. Scheherazade tells his tales to the great ruler. In total, she has to tell 1001 fairy tales. How many nights will it take Scheherazade to tell all her tales, if on some nights she tells 3 tales, and on some 5? In how many nights will Scheherazade tell all his tales if he wants to do it as quickly as possible? How many nights will Scheherazade need if she is tedious to tell five stories a night, so there should be as few such nights as possible?

Task 10. (remember "Aquarius") How to pour 3 liters of water, having a 9-liter and a 5-liter container?

Problem 11. Little Johnny is doing great in math. In his diary, he only has fives and fours, and there are more fives. The sum of all Vovochka's grades in mathematics is 47. How many Vovochka got fives and how many fours?

Problem 12. Koschey the Immortal set up a nursery for breeding Gorynych Serpents. In the last litter, he has 17-headed and 19-headed Serpents. In total, this brood has 339 goals. How many 17-headed and how many 19-headed Serpents did Koshchei breed?

Answers: Diophantus lived 84 years;

task 2: 4 boxes of 17 kg and 2 boxes of 16 kg;

task 6: 7 pencils and 8 pens were bought, i.e. (7,2) is a particular solution and y = 2 + 5n, x = 7 + 8n, where nє Z is a general solution;

task 7: (-53; 106) - a particular solution, x=4n-53, y=-7n+106 - general solutions, with n=14, x=3, y=8, that is, 3 felt-tip pens and 8 pencils were bought;

task 8: for example, pay 3 coins of 27 tugriks and get change of 5 coins of 16 tugriks;

task 9: (2002; -1001) - a particular solution, x=-5 n+2002, y=3n-1001 - a general solution, with n=350, y=49, x=252, i.e. 252 nights, 3 fairy tales each and 49 nights of 5 fairy tales - a total of 301 nights; the fastest option: 2 nights of three tales and 199 nights of 5 tales - a total of 201 nights; the longest option: 332 nights of 3 fairy tales and 1 night of 5 fairy tales - a total of 333 nights.

task 10: for example, pour water 2 times with a 9-liter jar and scoop it out 3 times with a 5-liter jar;

task 11: Little Johnny got 7 fives and 4 fours;

Problem 12: 11 Serpents with 17 heads and 8 Serpents with 19 heads.

To solve a linear Diophantine equation, you need to find the values ​​of the variables "x" and "y", which are integers. The integer solution is more complicated than the usual one and requires a certain set of actions. First you need to calculate the greatest common divisor (gcd) of the coefficients, and then find the solution. Once you have found one integer solution to a linear equation, you can apply a simple pattern to find an infinite number of other solutions.

Steps

Part 1

How to write an equation

Write the equation in standard form. A linear equation is an equation in which the exponents of the variables do not exceed 1. To solve such a linear equation, first write it in standard form. The standard form of a linear equation looks like this: A x + B y = C (\displaystyle Ax+By=C), Where A , B (\displaystyle A,B) And C (\displaystyle C)- whole numbers.

Simplify the equation (if possible). When you write the equation in standard form, look at the coefficients A , B (\displaystyle A,B) And C (\displaystyle C). If these coefficients have a GCD, divide all three coefficients by it. The solution of such a simplified equation will also be a solution to the original equation.

Check if the equation can be solved. In some cases, you can immediately declare that the equation has no solutions. If the coefficient "C" is not divisible by the GCD of the coefficients "A" and "B", the equation has no solutions.

Part 2

How to write the Euclid algorithm

1. Understand Euclid's algorithm. This is a series of repeated divisions in which the previous remainder is used as the next divisor. The last divisor that divides the numbers evenly is the greatest common divisor (gcd) of the two numbers.

   Apply Euclid's algorithm to the coefficients "A" and "B". When you write the linear equation in standard form, determine the coefficients "A" and "B" and then apply Euclid's algorithm to them to find the gcd. For example, given the linear equation 87 x − 64 y = 3 (\displaystyle 87x-64y=3).

   Find the greatest common divisor (gcd). Since the last divisor was 1, the GCD of 87 and 64 is 1. So 87 and 64 are prime numbers with respect to each other.

   Analyze the result. When you find the GCD of the coefficients A (\displaystyle A) And B (\displaystyle B), compare it with the coefficient C (\displaystyle C) original equation. If C (\displaystyle C) divided into NOD A (\displaystyle A) And B (\displaystyle B), the equation has an integer solution; otherwise, the equation has no solutions.

Part 3

How to Find a Solution Using Euclid's Algorithm

Number the steps for calculating GCD. To find a solution to a linear equation, one must use the Euclidean algorithm as the basis of the substitution and simplification process.

Pay attention to the last step, where there is a remainder. Rewrite the equation for this step to isolate the remainder.

Isolate the remainder of the previous step. This process is a step-by-step "moving up". Each time you will isolate the remainder in the equation from the previous step.

Make a change and simplify. Note that the equation in step 6 contains the number 2, but in the equation in step 5, the number 2 is isolated. So instead of "2" in the equation in step 6, substitute the expression in step 5:

Repeat the substitution and simplification process. Repeat the described process, moving through the Euclid algorithm in reverse order. Each time you will rewrite the equation of the previous step and substitute it into the last equation obtained.

1. Continue the process of substitution and simplification. This process will be repeated until you reach the initial step of the Euclid algorithm. The goal of the process is to write down an equation with coefficients 87 and 64 of the original equation to be solved. In our example:

   • 1 = 2 (18) − 7 (5) (\displaystyle 1=2(18)-7(5))
   • 1 = 2 (18) − 7 (23 − 18) (\displaystyle 1=2(18)-7(23-18))(substituted expression from step 3)
   • 1 = 9 (64 − 2 ∗ 23) − 7 (23) (\displaystyle 1=9(64-2*23)-7(23))(substituted expression from step 2)
   • 1 = 9 (64) − 25 (87 − 64) (\displaystyle 1=9(64)-25(87-64))(substituted expression from step 1)

Ministry of Education and Science of the Russian Federation

State educational institution of higher

vocational education

"Tobolsk State Social and Pedagogical Academy

them. DI. Mendeleev"

Department of Mathematics, TIMOM

Some Diophantine Equations

Course work

3rd year student of FMF

Mataev Evgeny Viktorovich

Scientific adviser:

Candidate of Physical and Mathematical Sciences A.I. Valitskas

Grade: ____________

Tobolsk - 2011

Introduction……………………………………………………………………........2

§ 1. Linear Diophantine equations…………………………………..3

§ 2. Diophantine equationx 2 – y 2 = a………………………………….....9

§ 3. Diophantine equationx 2 + y 2 = a…………………………………... 12

§ 4. Equation x 2 + x + 1 = 3y 2 …………………………………………….. 16

§ 5. Pythagorean triples…………………………………………………….. 19

§ 6. Fermat’s Last Theorem…………………………………………………23

Conclusion……………………………………………………………….….....29

Bibliography...........………………………………………………..30

INTRODUCTION

A Diophantine equation is an equation of the form P(x 1 , … , x n ) = 0 , where the left side is a polynomial in variables x 1 , … , x n with integer coefficients. Any ordered set (u 1 ; … ; u n ) integers with property P(u 1 , … , u n ) = 0 is called a (partial) solution of the Diophantine equation P(x 1 , … , x n ) = 0 . To solve a Diophantine equation means to find all its solutions, i.e. the general solution of this equation.

Our goal will be to learn how to find solutions to some Diophantine equations, if these solutions are available.

To do this, you need to answer the following questions:

A. Does the Diophantine equation always have a solution, find the conditions for the existence of a solution.

b. Is there an algorithm that allows finding a solution to a Diophantine equation.

Examples: 1. Diophantine equation 5 x – 1 = 0 has no solutions.

2. Diophantine equation 5 x – 10 = 0 has a solution x = 2 , which is the only one.

3. The equation ln x – 8 x 2 = 0 is not Diophantine.

4. Often equations of the form P(x 1 , … , x n ) = Q(x 1 , … , x n ) , Where P(x 1 , … , x n ) , Q(x 1 , … , x n ) are polynomials with integer coefficients, also called Diophantine. They can be written in the form P(x 1 , … , x n ) – Q(x 1 , … , x n ) = 0 , which is standard for Diophantine equations.

5. x 2 – y 2 = a is a Diophantine equation of the second degree with two unknowns x and y for any integer a. It has solutions for a = 1 , but has no solutions for a = 2 .

§ 1. Linear Diophantine Equations

Let a 1 , … , a n , WithZ . Type equation a 1 x 1 + … + a n x n = c is called a linear Diophantine equation with coefficients a 1 , … , a n , right side c and unknown x 1 , … , x n . If the right side c of a linear Diophantine equation is zero, then such a Diophantine equation is called homogeneous.

Our immediate goal is to learn how to find particular and general solutions of linear Diophantine equations in two unknowns. Obviously, any homogeneous Diophantine equation a 1 x 1 + … + a n x n = 0 always has a particular solution (0; … ; 0).

It is obvious that a linear Diophantine equation, all coefficients of which are equal to zero, has a solution only in the case when its right side is equal to zero. In general, we have the following

Theorem (on the existence of a solution to a linear Diophantine equation). Linear diophantine equation a 1 x 1 + … + a n x n = c, whose coefficients are not all equal to zero, has a solution if and only if GCD(a 1 , … , a n ) | c.

Proof. The necessity of the condition is obvious: GCD(a 1 , … , a n ) | a i (1 i n) , So GCD(a 1 , … , a n ) | (a 1 x 1 + … + a n x n ) , which means it divides and

c = a 1 x 1 + … + a n x n .

Let D= gcd(a 1 , … , a n ) , c =Dt And a 1 u 1 + … + a n u n = D – linear expansion of the greatest common divisor of numbers a 1 , … , a n. Multiplying both sides by t, we get a 1 (u 1 t) + … + a n (u n t) = Dt = c, i.e. integer

n-ka (x 1 t; … ; x n t) is a solution to the original equation with n unknown.

The theorem has been proven.

This theorem gives a constructive algorithm for finding particular solutions to linear Diophantine equations.

Examples: 1. Linear diophantine equation 12x+21y=5 has no solution because gcd(12, 21) = 3 does not divide 5 .

2. Find a particular solution of the Diophantine equation 12x+21y = 6.

Obviously now gcd(12, 21) = 3 | 6, so the solution exists. We write the linear expansion gcd(12, 21) = 3 = 122 + 21(–1). Therefore, a couple (2; –1) is a particular solution of the equation 12x+21y = 3, and a couple (4; –2) is a particular solution of the original equation 12x+21y = 6.

3. Find a particular solution to a linear equation 12x + 21y - 2z = 5.

Because (12, 21, –2) = ((12, 21), –2) = (3, –2) = 1 | 5 , then the solution exists. Following the proof of the theorem, we first find a solution to the equation (12.21)x–2y=5, and then, substituting the linear expansion of the greatest common divisor from the previous problem, we obtain the solution of the original equation.

To solve the equation 3x - 2y = 5 write down the linear expansion gcd(3, -2) = 1 = 31 - 21 obviously. So a couple of numbers (1; 1) is a solution to the equation 3 x – 2 y = 1 , and a couple (5; 5) is a particular solution of the Diophantine equation 3x - 2y = 5.

So, (12, 21)5 – 25 = 5 . Substituting here the previously found linear expansion (12, 21) = 3 = 122 + 21(–1) , we get (122+21(–1))5 – 25 = 5 , or 1210 + 21(–5) – 25 = 5 , i.e. triplet of integers (10; –5; 5) is a particular solution of the original Diophantine equation 12x + 21y - 2z = 5.

Theorem (on the structure of the general solution of a linear Diophantine equation). For a linear Diophantine equation a 1 x 1 + … + a n x n = c the following statements are true:

(1) if = (u 1 ; … ; u n ), = (v 1 ; … ; v n ) are its particular solutions, then the difference (u 1 –v 1 ; … ; u n –v n ) is a particular solution of the corresponding homogeneous equation a 1 x 1 + … + a n x n = 0 ,

(2) the set of particular solutions of the linear Diophantine homogeneous equation a 1 x 1 + … + a n x n = 0 closed under addition, subtraction and multiplication by integers,

(3) if M is the general solution of the given linear Diophantine equation, and L is the general solution of the corresponding homogeneous Diophantine equation, then for any particular solution = (u 1 ; … ; u n ) of the original equation, the equality M = +L .

Proof. Subtracting equality a 1 v 1 + … + a n v n = c from equality a 1 u 1 + … + a n u n = c, we get a 1 (u 1 –v 1 ) + … + a n (u n –v n ) = 0 , i.e., the set

(u 1 –v 1 ; … ; u n –v n ) is a particular solution of the linear homogeneous Diophantine equation a 1 x 1 + … + a n x n = 0 . Thus, it has been proven that

= (u 1 ; … ; u n ), = (v 1 ; … ; v n ) ML .

This proves assertion (1).

Statement (2) is proved similarly:

, L z Z L z L .

To prove (3), we first note that M+L. This follows from the previous one: M+L .

Conversely, if = (l 1 ; … ; l n ) L and = (u 1 ; … ; u n ) M, then M:

a 1 (u 1 +l 1 )+ …+a n (u n +l n ) = (a 1 u 1 + … + a n u n )+(a 1 l 1 + … + a n l n ) = c + 0 = c.

Thus, + LM, and eventually M = +L .

The theorem has been proven.

The proved theorem has a clear geometric meaning. If we consider the linear equation a 1 x 1 + … + a n x n = c, Where X i R, then, as is known from geometry, it determines in space R n hyperplane obtained from the plane L with homogeneous equation a 1 x 1 + … +a n x n =0 passing through the origin of coordinates by a shift by some vector R n. View Surface + L also called a linear manifold with guide space L and shift vector . Thus, it is proved that the general solution M diophantine equation a 1 x 1 + … + a n x n = c consists of all points of some linear manifold having integer coordinates. In this case, the coordinates of the shift vector are also integers, and the set L solutions of the homogeneous Diophantine equation a 1 x 1 + … + a n x n = 0 consists of all points in the guide space with integer coordinates. For this reason, it is often said that the set of solutions of an arbitrary Diophantine equation forms a linear manifold with a shift vector and leading space L.

Example: for the Diophantine equation x - y \u003d 1 common decision M has the form (1+y; y), where yZ, its particular solution = (1; 0) , and the general solution L homogeneous equation x – y = 0 will be written in the form (y; y), Where atZ. Thus, we can draw the following picture, in which the solutions of the original Diophantine equation and the corresponding homogeneous Diophantine equation are shown by thick dots in the linear manifold M and space L respectively.

2. Find the general solution of the Diophantine equation 12x + 21y - 2z = 5.

Private solution (10; –5; 5) this equation was found earlier, we find the general solution of the homogeneous equation 12x + 21y - 2z = 0, equivalent to the Diophantine equation 12 x + 21 y = 2 z.

For this equation to be solvable, it is necessary and sufficient that the condition gcd(12, 21) = 3 | 2z, those. 3 | z or z = 3t for some integer t. Reducing both parts to 3 , we get 4x + 7y = 2t. Particular solution (2; –1) of the Diophantine equation 4x+7y= 1 found in the previous example. That's why (4t ; -2t) is a particular solution of the equation 4x + 7y = 2t for any

t Z. General solution of the corresponding homogeneous equation

(7 u ; –4 u) already found. Thus, the general solution of the equation 4x + 7y = 2t looks like: (4t + 7u; -2t - 4u) , and the general solution of the homogeneous equation 12x + 21y - 2z = 0 will be written like this:

(4t + 7u; -2t - 4u; 3t).

It is easy to verify that this result corresponds to the theorem stated above without proof on solutions of the homogeneous Diophantine equation A 1 X 1 + … + a n X n = 0 : If P = , That R And

(u; t) P is the general solution of the considered homogeneous equation.

So, the general solution of the Diophantine equation 12x + 21y - 2z = 5 looks like that: (10 + 4t + 7u; –5 – 2t – 4u; 5+3t).

3. On the example of the previous equation, we illustrate another method for solving Diophantine equations in many unknowns, which consists in successively decreasing the maximum value of the modules of its coefficients.

12x + 21y - 2z = 5 12x + (102 + 1)y - 2z = 5

12x + y - 2(z - 10y) = 5

Thus, the general solution of the considered equation can be written as follows: (x; 5 - 12x + 2u; 50 - 120x + 21u), Where x, u are arbitrary integer parameters.

§ 2. Diophantine equationx 2 – y 2 = a

Examples: 1. At a = 0 we get an infinite number of solutions: x = y or x = – y for anyone y Z.

2. At a = 1 we have x 2 – y 2 = 1 (x + y)(x – y) = 1 . Thus, the number 1 is decomposed into the product of two integer factors x + y And x – y(important, that x, y- whole!). Because the number 1 only two expansions into the product of integer factors 1 = 11 And 1 = (–1)(–1) , we get two possibilities: .

3. For a = 2 we have x 2 – y 2 = 2 (x + y)(x – y) = 2. Proceeding similarly to the previous one, we consider the expansions

2=12=21=(–1)(–2)=(–2)(–1), we compose systems:, which, unlike the previous example, have no solutions. So there are no solutions for the considered Diophantine equation x 2 – y 2 = 2.

4. The previous considerations lead to some conclusions. Equation solutions x 2 – y 2 = a are in decomposition a = km into the product of integers from the system . This system has entire solutions if and only if k + m And k – m are even, i.e. when the numbers k And m the same parity (simultaneously even or odd). Thus, the Diophantine equation x 2 – y 2 = a has a solution if and only if a can be expanded into a product of two integer factors of the same parity. It remains only to find all such a .

Theorem (on the equationx 2 – y 2 = a ). (1) Equation x 2 – y 2 = 0 has an infinite number of solutions .

(2) Any solution of the equation is obtained as , Where a = km is the decomposition of the number a into the product of two integer factors of the same parity.

(3) Equation x 2 – y 2 = a has a solution if and only if a 2 (mod 4).

Proof.(1) has already been proven.

(2) has already been proven.

(3) () Let first the Diophantine equation x 2 – y 2 = a has a solution. Let's prove that a 2 (mod 4) . If a = km is the expansion into a product of integers of the same parity, then for even k And m we have k = 2 l, m = 2 n And a = km = 4 ln 0 (mod 4) . In the case of odd k, m their work a also odd, difference a – 2 odd and not divisible by 4 , i.e. again

a 2 (mod 4).

() If now a 2 (mod 4) , then we can construct a solution to the equation x 2 – y 2 = a. Indeed, if a is odd, then a = 1 a is a product decomposition of odd integers, so that is the solution of the Diophantine equation. If a is even, then in view of a 2 (mod 4) we get that 4 | a, a = 4 b = 2(2 b) is a product decomposition of even integers, so that is the solution of the Diophantine equation.

The theorem has been proven.

Examples: 1. Diophantine equation x 2 – y 2 = 2012 has no solutions, since 2010 = 4502 + 2 2 (mod 4).

2. Diophantine equation x 2 – y 2 = 2011 has solutions, because

2011 3 (mod 4). We have obvious expansions

2011 = 12011 = 20111 = (–1)(–2011) = (–2011)(–1),

for each of which we find solutions (any combination of characters). There are no other solutions, because number 2011 simple (?!).

§ 3. Diophantine equationx 2 + y 2 = a

Examples: 1. 0 = 0 2 + 0 2 , 1 = 0 2 + 1 2 , k 2 = 0 2 + k 2 . Thus, it is obvious that any square can be trivially represented as a sum of two squares.

2. 2 = 1 2 + 1 2 , 5 = 1 2 + 2 2 , 8 = 2 2 + 2 2 , 10 = 1 2 + 3 2 , 13 = 2 2 + 3 2 , 17 = 1 2 + 4 2 , 18 = 3 2 + 3 2 , 20 = 2 2 + 4 2 , …

3. No solutions for a = 3, 6 = 23, 7, 11, 12 = 2 2 3, 14 = 27, 15 = 35, 19, 21 = 37, 22 = 211, 23, 24 = 32 3 , …

An analysis of the above results can suggest that the absence of solutions is somehow connected with prime numbers of the form

4 n+3 present in the factorization of numbers that cannot be represented as sums of two squares.

Theorem (on the representation of natural numbers by sums of two squares). A natural number a can be represented as a sum of two squares if and only if, in its canonical expansion, prime numbers of the form 4 n + 3 have even exponents.

Proof. First we prove that if a natural number a can be represented as a sum of two squares, then in its canonical expansion all prime numbers of the form 4 n + 3 must have even exponents. Suppose, contrary to what has been proved, that a= p 2 k +1 b = x 2 + y 2 , Where

R - prime number of the form 4 n+3 And b p. Imagine numbers X And at as

x =Dz, y = Dt, WhereD= gcd(x, y) = p s w, p w; z, t, s N 0 . Then we get the equality R 2 k +1 b = D 2 (z 2 + t 2 ) = p 2 s w 2 (z 2 + t 2 ) , i.e. R 2( k – s )+1 b = w 2 (z 2 + t 2 ) . There is p on the left side of the equality (the odd power is not equal to zero), which means that one of the factors on the right side is divisible by the prime number p. Because the p w, That p | (z 2 + t 2 ) , where the numbers z, t mutually simple. This contradicts the next lemma (?!).

Lemma (on the divisibility of the sum of two squares by a prime number of the form

4 n + 3 ). If a prime number p = 4n+3 divides the sum of the squares of two natural numbers, then it divides each of these numbers.

Proof. From the contrary. Let x 2 + y 2 0(mod p) , But x0(mod p) or y 0 (mod p) . Because the x And y are symmetrical, they can be interchanged, so we can assume that x p.

Lemma (on reversibility modulop ). For any integer x, not divisible by a prime number p, there is an inverse element modulo p – such an integer 1 u < p, What xi 1 (mod p).

Proof. Number x coprime with p, so we can write a linear expansion GCD(x, p) = 1 = xi + pv (u, v Z) . It's clear that xi1(modp) , i.e. u- inverse element to x modulo p. If u does not satisfy the constraint 1 u < p, then dividing u with the remainder on p, we get the remainder r u (mod p) , for which xr xi 1 (mod p) And 0 r < p.

Modulo reversibility lemma p proven.

Multiplying Comparison x 2 + y 2 0 (mod p) per square u 2 inverse element to x modulo p, we get 0 = 0u 2 x 2 u 2 +y 2 u 2 = (xu) 2 + (yu) 2 1+t 2 (mod p).

So for t = yu comparison done t 2 –1 (mod p) , which we bring to a contradiction. It's clear that t p: otherwise t 0 (mod p) And 0 t 2 –1 (mod p) , which is impossible. By Fermat's theorem we have t p –1 1 (mod p), which together with t 2 –1 (mod p) And p = 4 n + 3 leads to a contradiction:

1 t p–1 = t 4n+3–1 = t 2(2n+1) = (t 2 ) 2n+1 (–1) 2n+1 = –1 (modp).

The obtained contradiction shows that the assumption about x 0 (mod p) was not correct.

Lemma on divisibility of the sum of two squares by a prime number 4 n+3 proven.

Thus, it is proved that the number whose canonical decomposition includes a prime number p = 4 n + 3 to an odd power, cannot be represented as the sum of two squares.

Let us now prove that any number in whose canonical expansion the prime numbers p = 4 n + 3 participate only in even powers, representable as the sum of two squares.

The idea of ​​the proof is based on the following identity:

(A 2 +b 2 )(c 2 +d 2 ) = (ac – bd) 2 + (ad + bc) 2 ,

which can be obtained from the well-known property of the modulus of complex numbers - the modulus of the product is equal to the product of the modules. Really,

| z|| t| = | zt| | a + bi|| c + di| = |(a + bi)(c + di)|

|a+bi| 2 |c + di| 2 = |(ac – bd) + (ad + bc)i| 2

(A 2 +b 2 )(c 2 +d 2 ) = (ac – bd) 2 + (ad + bc) 2 .

It follows from this identity that if two numbers u, v can be represented as the sum of two squares: u = x 2 + y 2 , v = z 2 + t 2 , then their product uv can also be represented as the sum of two squares: UV = (xz – yt) 2 + (xt + yz) 2 .

Any natural number a > 1 can be written in the form a= p 1 … R k m 2 , Where R i are pairwise distinct prime numbers, m N . To do this, it suffices to find the canonical decomposition , write down each degree of the form r in the form of a square (r) 2 for even = 2, or in the form r = r(r) 2 for odd = 2 + 1 , and then group separately the squares and the remaining single primes. For example,

29250 = 23 2 5 3 13 = 2513(35) 2 , m = 15.

Number m 2 has a trivial representation as the sum of two squares: m 2 = 0 2 + m 2 . If we prove representability as a sum of two squares of all prime numbers R i (1 i k) , then using the identity, the representation of the number a will also be obtained. By condition, among the numbers R 1 , … , R k can only meet 2 = 1 2 + 1 2 and prime numbers of the form 4 n + 1 . Thus, it remains to obtain a representation as the sum of two squares of a prime number p = 4m + 1. We separate this statement into a separate theorem (see below)

For example, for a = 29250 = 2513(15) 2 successively we get:

2 = 1 2 + 1 2 , 5 = 1 2 + 2 2 , 13 = 2 2 + 3 2 ,

25 = (11 – 12) 2 + (12 + 11) 2 = 1 2 + 3 2 ,

2513 = (12 – 33) 2 + (13 + 32) 2 = 7 2 + 9 2 ,

29250 = 2513(15) 2 = (715) 2 + (915) 2 = 105 2 + 135 2 .

The theorem has been proven.

§ 4. Equationx + x + 1 = 3y

Let's now deal with the equation x+x+1=Zu. It already has its history. In 1950, R. Oblat suggested that, in addition to solving

x=y=1. it has no other solutions in natural numbers x, y where x is an odd number. In the same year, T. Nagel pointed out the solution x= 313, y = 181. A method similar to the one above for the equation x+x-2y=0, will allow us to determine all solutions of the equation x+x+1=3y (1)

in natural numbers x, at. Let's pretend that (x, y) is a solution of equation (1) in natural numbers, and x > 1. It can be easily seen that equation (18) has no solutions in natural numbers x, y, Where x = 2, 3. 4, 5, 6, 7, 8, 9; so it should be x10.

Let us show that 12y<7 x+3, 7y>4x+ 2. 4y > 2x+1 . (2)

If it were 12y> 7x+3, we would have 144y> 49 x+42 x+9 . and since, in view of (18), 144y= 48x+ 48 x + 48 , then it would be X< 6 x +3 9, from where

(x-z)< 48 and, therefore, given that x> 10, 7 < 148 , which is impossible. Thus, the first of inequalities (2) is proved.

If it were 7y< 4 x+2 , we would have 49y< 16 x+ 16 x+4 , and since, in view of (1), 16 x+ 16 x+ 16 = 48y, then it would be 49y< 48u- 12, which is impossible. Thus, the second of the inequalities (2) is proved, from which the third follows directly. So, inequalities (2) are true.

Let's put now

w\u003d 7x - 12y + 3,h = -4 x+ 7u-2. (3)

Based on (2), we find that w > 0 , h > 0 And X -w=3(4 y-2 x-1)>0 and, therefore, w<х . According to (3), we have w 2 + w+1=3 h 2 whence, in view of (1), we accept g(x, y) = (7x - 12y + 3, -4x + 7y -2).

So, we can say that, based on any solution (x, y) equations (1) in natural numbers, where x > 1, we get a new solution (w, h) = g(x, y) equations (1) in natural numbers w, h Where w < х (and hence the solution in smaller natural numbers). Hence, acting as above, we find that for each solution of Eq. (1) in natural numbers x, y, Where x > 1, there is a natural number n such that g(x, y) = (l, 1).

Having accepted f(x, y) = (7x+12y + 3, 4x+ 7y + 2), (4) we can easily find that f(g(x, y)) = (x, y) and hence (x, y) = f(1,1) On the other hand, it is easy to check that if (x, y) is a solution of equation (1) in natural numbers, then f(x, y) there is also a solution of equation (1) in natural numbers (respectively, larger than X And at).

Having accepted x=y=1(x, y) = f(1, 1) For n=2,3,…..,

we get the sequence { x, y} For n= 1, 2,….., containing all solutions of equation (1) in natural numbers and only such solutions.

Here we have (X,y)= f(1,1)= f(x, y), therefore, due to (4), we obtain

x=7x+12y+3,y=4x+7y+2 (5) (n=1, 2, ...)

Formulas that allow you to consistently determine all solutions (x, y) equations (1) in natural numbers. In this way, we easily obtain solutions (1,1),(22,13),(313,181),.(4366,2521),(60817,35113),..

There are obviously an infinite number of these solutions. From equalities

x=y=1 and (4) by induction we easily find that the numbers X with odd indices are odd, with even indices they are even, and the numbers y essence odd for n = 1, 2, ... To obtain all solutions of equation (1) in integers x, y, as it is easy to prove, it would follow to the already obtained solutions (x, y) join (x, -y) And (-x-1,±y) For n=1, 2, .. .

So here we have, for example, more such solutions: (-2,1) (-23,13), (-314,181). A. Rotkevich noted that of all solutions of equation (1) in natural numbers x > 1 and y can get all solutions of the equation (z+1)-z=y (6)

in natural numbers z, y. Indeed, suppose that the natural numbers z, y satisfy equation (5). Putting x=3z+l, we get, as it is easy to check, natural numbers x > 1 And at satisfying equation (1).

On the other hand, if natural numbers x > 1 And at satisfy equation (1), then we have, as it is easy to check, (x-1)= 3(y-x), whence it follows that the number (natural) x-1 divided by 3 , hence x-1=3 z, where z is a natural number, and the equality 3z=y-x=y3z-1 , which proves that the numbers z And at satisfy equation (6). Thus, based on the solutions (22,13),(313,181), (4366,2521) equation (1), we obtain solutions (7,13),(104,181),(1455,2521) equations (6). We also note here that if the natural numbers z, y satisfy equation (6), it is proved that at is the sum of two consecutive squares, for example 13=2+3,181=9+10, 2521=35+ 36 . In a similar way, as before for equation (1), we could find all solutions of the equation x+(x+1)= y in natural numbers x, y, taking for x > 3 g (x. y) \u003d (3x -2y + 1, 3y - 4x - 2) and for x> 1 f(x, y) = (3x+ 2y+l, 4x + Zu + 2), which leads to the formula ( x, y)f(3,5) and to the conclusion that all solutions of equation (6) in natural numbers x, y are contained in the sequence { x, y} For n= 1, 2,…., Where x=3, y=5, andx=3 x+2 y+1 . y = 4 x+3 y+2 (n=1, 2, ...). For example, x \u003d 3 3 + 2 5 + 1 \u003d 20, y \u003d 4 3 + Z 5 + 2 \u003d 29;x=119, y=169:x=69b, y=985;x=4059, y=5741.

The geometric meaning of the considered equation is that it gives all Pythagorean triangles (rectangular with natural sides), whose legs are expressed by successive natural numbers. There are an infinite number of such triangles (*).

The equation is x+(x+1)= y, has been proven to have no solutions in natural numbers x, y.

MUNICIPAL BUDGET GENERAL EDUCATIONAL INSTITUTION

SECONDARY EDUCATIONAL SCHOOL № 28 of the city of SMOLENSK

SMOLENSK STATE UNIVERSITY

Section Mathematics

Essay

Diophantine equations

Completed the work: Goncharov Evgeniy Igorevich,

11th grade student

Head: Soldatenkova Zoya Alexandrovna,

mathematic teacher

Smolensk

Why am I interested in this topic?

Once, while leafing through a textbook, I came across a small sidebar about Diophantine equations. I immediately noticed that text problems within this topic have an intriguing, sometimes comical, condition, and due to the large number of different methods for solving them, they do not seem typical at all. In addition, some gave me difficulty.

Finding ways to rationally solve them, I became more closely acquainted with this topic. The deeper I dived, the more complex and interesting tasks I met, the more questions arose. I soon realized that much of this topic lay outside the school curriculum.

Therefore, I did not get ahead of events and delve into the theory (CTO, Hilbert's 10th problem, Fermat's Last Theorem, etc.). And he began to master exclusively the algorithms for solving Diophantine equations and systems of equations, while simultaneously getting acquainted with the history of their discovery.

Diophantus of Alexandria is an ancient Greek mathematician. The chronicles did not retain practically any information about this scientist. Diophantus presents one entertaining riddle in the history of mathematics. of We do not know who he was, the exact years of his life, we do not know his predecessors who would have worked in the same field as Diophantus himself:

Diophantus quotes Hypsicles of Alexandria (an ancient Greek mathematician and astronomer who lived in the 2nd century BC);

About Diophantus writes Theon of Alexandria (Greek mathematician of the late Hellenistic era, philosopher and astronomer, who lived in the III century AD);

Diophantus dedicates his works to Dionysius of Alexandria (a bishop who lived in the middle of the 3rd century AD). Thus, scientists suggest that this mathematician lived in the 3rd century AD.

The anthology of Maxuim Planud (a Greek monk of the 14th century AD) contains an epigram-task "Epitaph of Diophantus":

The ashes of Diophantus the tomb rests; marvel at her - and a stone

The age of the departed will tell him with wise art.

By the will of the gods, he lived a sixth of his life as a child.

And he met half of the sixth with fluff on his cheeks.

Only the seventh passed, he got engaged to his girlfriend.

With her, after spending five years, the wise man waited for his son;

His beloved son lived only half his father's life.

He was taken from his father by his early grave.

Twice two years the parent mourned the heavy grief,

Here I saw the limit of my sad life.

(Translated by S. N. Bobrov).

This task is reduced to compiling and solving the simplest linear equation:

(1/6)x+(1/12)x+(1/7)x+5+(1/2)x+4=x,

where x is the number of years lived by Diophantus.

x+7x+12x+42x+9*84=84x;

x = 84 - that's how many years Diophantus lived.

And over the years, Diophantus wrote compositions On the measurement of surfaces and On multiplication , treatise About polygonal numbers . The main work of Diophantus is Arithmetic in 13 books.

Unfortunately, not all of his works have survived. Those that have come down to us contain 189 problems with solutions that reduce to certain equations of the first and second degrees and indefinite ones. The contribution of this scientist to the development of mathematics is enormous.

Diophantus introduces special symbols for subtraction, abbreviated words for individual definitions and actions. That is, it was he who was the author of the first algebraic language.

A crater on the Moon is named after Diophantus.

However, Diophantus did not look for general solutions, but was content with some one, as a rule, positive solution to an indefinite equation.

Diophantine equations as a mathematical model of life situations

Every person, even infinitely far from mathematics, met and, moreover, solved the simplest Diophantine equations without knowing it. Indeed, they serve as a mathematical model for many tasks that arise at the everyday level.

Task #1

In the warehouse there are boxes with nails weighing 16, 17 and 40 kg. Will the storekeeper be able to give out 100 kg of nails without opening the boxes?

It is easy to see that 17 kg + 17 kg + 16 kg = 50 kg. Then, in order to give out 100 kg (2 times more), you need to take 4 boxes of 17 kg and 2 boxes of 16 kg.

Answer: Yes, it can.

Here we were lucky: the solution was reduced to the simplest enumeration, and the answer turned out to be obvious. Let's consider another problem:

Task #2

There are one-headed centipedes and three-headed snakes in the paddock. In total they have 298 legs and 26 heads. How many legs do three-headed snakes have?

Let there be x centipedes and y Gorynychs in the corral, and each snake has p legs. We immediately stipulate that each of these variables must be integer and positive. Then:

3y=26x=26-3yx=26-3yx=26-3y

x+py=29840x+py=298120y-742=py p=120-742/y

x>026-3y>0y?8 y?8

y>0 p>0p>0 120-742/y>0>0y>0y>0y>0

p=120-742/yThen: x=5

Since p is an integer, p=27.25 does not suit us.

This task was somewhat more difficult than the first one, but by introducing constraints on the variables, we were able to narrow the search down to just two cases. Go ahead:

Task #3

It is required to pour 20.5 liters of juice into jars of 0.7 liters and 0.9 liters so that all the jars are full. How many cans do you need to prepare? What is the smallest number of jars that can be needed?

Let x be the number of cans of 0.7 liters each and y be 0.9 liters. Then we set up the equation:

It is obvious that direct enumeration of numbers head-on will take a lot of time. A there is no place in the world for ugly mathematics ©G. Hardy.

Let's consider a method for solving such equations, and then we will return directly to our problem and complete it.

Scattering method

The Diophantine equation has the form: (x1,x2…xn)=0, where P is an integer function, and the variables xi take integer values. Solving problem number 2, we are faced with an equation of the form ax + by = c, where a, b and c are integer coefficients, and x and y are variables that take only integer values. This is a linear Diophantine equation with two unknowns.

A general method for solving such equations originated in India in the 12th century. Its appearance was caused by astronomical requests and calendar

calculations. First hints on the general solution of Diophantine equations was made by Ariabhatt. The method itself was created by Bhaskara and Brahmagupta. It is now known as the scattering method. Let's analyze it with an example:

Example #1: Find all integer solutions of the equation 19x-8y=13.

We express y in terms of x (since the coefficient of y is the smallest) and select the integer part:

y \u003d (19x-13) / 8 \u003d (3x-13) / 8 + 2x

The expression (3x-13)/8 must be an integer. Let's denote it as k.

Then 8k=3x-13. Let's repeat the above operation:

x=(8k+13)/3=2k+(2k+13)/3= (2k+13)/3. Then 3h=2k+13,=(3h-13)/2=(h-13)/2+h= (h-13)/2. Then 2p= h-13. h=13+2p

It is obvious from equality (4) that h takes integer values ​​for any integer values ​​of p.

By successive substitutions (4) we find expressions for the unknowns: k=13+3p, x= 39+8p and, finally, y=91+18p.

Answer: (39+8p; 91+18p).

Now, having a sufficient stock of knowledge, let's return to problem number 3.

x=29+(2-9y)/7; let t=(2-9y)/7, where t is an integer;

t=2-9y; t=(2-2y)/7-y; let (2-2y)/7=p, where p is an integer;

Y=7k, where k is an integer; y=1-7k, where k is an integer. Then x=28+9k.

x>0; 28+9k>0;k?-3.

y>0; 1-7k>0;k?0.

That is, k can take values: -3, -2, -1.0.

x+y=1-7k+28+9k; x+y=29+2k.

That is, the smallest number of jars corresponds to the smallest k.

(x+y)smallest=29-6=23.

Answer: (28+9k;1-7k), where k takes the values ​​-3,-2,-1.0. The smallest number of cans is 23.

Number expansion problems

It is worth noting that text tasks, which boil down to finding a number, know its divisors and remainders, occupy a special, honorable place among text tasks on this topic. They are also the most complex, and therefore interesting. Let's consider some of them.

A peasant woman was carrying a basket of eggs to the market. A careless rider, overtaking a woman, touched the basket, and all the eggs were broken. Wanting to make amends, he asked the peasant woman how many eggs were in the basket. She replied that she did not know the number of eggs, but when she laid them out in 2, 3, 4, 5 and 6, each time one egg remained superfluous, and when she laid out 7, there were no extra eggs left. What is the smallest number of eggs a peasant woman could carry to the market?

Solution: Let's denote the desired number of eggs as n, then we will compose a system of equations:

2a+1 n-1=2a (1)=3b+1 n-1=3b (2)=4c+1 n-1=2*2c (3)=5d+1 n-1=5d (4)= 6e+1 n-1=2*3e (5)=7fn=7f

From equations (1), (2), (3), (4), (5) it follows that the number n-1=2*3*2*5k, where k is an integer;

n-1=60k;n=60k+1.

When substituting the resulting n in (7), we get the equation: 60k+1=7f.

f= (60k+1)/7 = (4k+1)/7 + 8k;=(4k+1)/7, where r is an integer, (1)

7r=4k+1; 4k=7r-1; k=(3r-1)/4+r;=(3r-1)/4, where s is an integer

3r-1=4s; 3r=4s+1;r= (s+1)/3+r;= (s+1)/3,where u is integer,then

s+1=3u; s=3u-1,

that is, s always takes integer values ​​for any integer u. By successive substitutions, we get:

r=4u-1; k=7u-2; f=420u -119.

Obviously, when u=1, f takes the smallest positive value, namely 301.

Answer: 301.

* It should be noted that it is not necessary to blindly follow this algorithm to the very end. In fact, within the framework of the problem, we do not have to find all possible integer values ​​of k: just one, the smallest, is enough. And already after (1) transformation, it is obvious that the k we are looking for is equal to 5, which means f=60*5+1=301.

Suppose there are some tourists. Breaking them into triples, we get the remainder 2, breaking into fives - 3, breaking into sevens - 2. How many tourists are in the group, if their total number does not exceed 100 people.

Let there be k tourists in total. Then:

3a+2 k=3a+2=5b+3 5b+3=3a+2=7c+2 7c+2=3a+2

And here the obvious part of our solution comes to a standstill. To get out of it, you need to remember that:

1) a*b+c?c (moda) ? c (modb). For example, 15? 1 (mod 7), that is, the number 15 gives a remainder of 1 when divided by 7.

2) a*b+d ? c (modr) ó a*b? c-d (modr) ó b? a(c-d) (modr) oa? b(c-d) (modr). Then:

3a+2 k=3a+2 k=3a+2

a+2 ? 3 (mod 5) 3a= 1 (mod 5) a ? 3 (mod 5)

a+2 ? 2 (mod 7) 3a= 0 (mod 7) 3a ? 0 (mod7)

3a+2 k=3a+2= 3 +5p, wherep integer a=3 + 5p

15p? 0 (mod 7) p= -135 (mod 7)

3a+2 k=3a+2k=105d-2014=3 + 5pa=35d-672 a=35d-672=-135 + 7d, where d is an integer p=-135 + 7dp= -135 + 7d

So k=105d-2014. If d=20, then k = 86, if d<20 , то k<0, если d>20, then k>100. Answer: 86.

Let's try to give it practical utility, for example, derive a general formula for a tour guide to count tourists. Let r1, r2, r3 be the remainders when dividing the total number of tourists into groups of 3, 5.7, respectively, and the total number of tourists will still not exceed 100 people. Arguing similarly, we get:

3a+r1 3a? (r2-r1) (mod 5)a=3(r2-r1) + 5d where dinteger=5b+r2 3a+r1=7c+r39r2-8r1+15d?r3 (mod 7)=7c+r3k=3a+1 k=3a+1

a=3(r2-r1) + 5d d = 15(r3-9r2+8r1)+7p where p is an integer

d?15(r3-9r2+8r1) (mod 7) a = 3(r2-r1) + 5d

k=9r2-8r1+15d k=225r3-1792r1-2016r2+105p

Answers: 86; k=225r3-1792r1-2016r2+105p.

So, we have obtained a formula for k. But in addition to r1,r2,r3, it contains an integer d. A logical question arises: will the number k always be determined in a unique way if it is less than 100? Less than 150? 43? and so on.

Chinese remainder theorem

The Chinese Remainder Theorem (CRT) is a series of related statements formulated in a treatise by the Chinese mathematician Sun Tzu (3rd century AD) and summarized by Qin Jiushao (18th century AD) in his book Mathematical Reasoning in 9 Chapters. It sounds like this:

Let the numbers M1 , M2, …, Mk be pairwise coprime, and M= M1*M2*…*Mk . Then the system

x?B1(modM1)? B2 (modM2)

has a unique solution among the numbers (0,1,…,M-1).

Simply put, the answer will always be unambiguous if the desired number of tourists is less than the product of the divisors by which it is divided. Returning to problem No. 4, we say that it will be possible to count them if their total number does not exceed 104. (M-1=3*5*7-1=104). So, in order to count a person, starting from our formula, it is necessary to calculate 225r3-1792r1-2016r2, and then subtract the number 105 from it until we get a number less than 105, but greater than 0. This is long and inconvenient. And, frankly, the number of about a hundred people can be counted without using such complex algorithms.

The simplest non-linear Diophantine equations

Diophantus completely analyzed indefinite equations of the second degree with two unknowns. To solve equations and systems of higher degrees, he developed even more subtle and complex methods that attracted the attention of many modern European mathematicians. But almost all equations of this type within the framework of the school course are solved by the factorization method.

Example #2: Solve the equation x2-3xy+2y2=7 in integers.

x2-xy-2xy+2y2=7;

x(x-y) -2y(x-y)=7;

Obviously, we can get the number 7 in the following ways: 1*7=7;7*1=7;-1*(-7)=7;-7*(-1).

Then we compose and solve the system of equations:

x-2y=1 x=13y=7y=6y=7 x=-5y=1 y=-6y=-1 x=-13y=-7 y=-6y=-7 x=5y=-1 y=6

Answer: (13;6), (-5;-6), (-13;-6), (5.6).

Example #3: Prove that the equation x5+3x4y- 5x3y2-15x2y3 + 4xy4+12y5=33 has no integer roots.

x4(x+3y)-5x2y2 (x+3y)+4y4(x+3y)=33;

(x4-4x2y2+4y4-x2y2)(x+3y)=33;

(x2(x2-y2)-4y2(x2-y2))(x+3y)=33;

(x-y)(x+y)(x+2y)(x-2y)(x+3y)=33;

If y=0, then the original equation will take the form x5=33. Then x is not an integer. This means that for y=0 this equation has no entire solutions. If, y?0, then all five factors on the left side of the equation are different. On the other hand, the number 33 can be represented as a product of at most four different factors (33=1 3 11 or 33=-1 3 (-11) (-1), etc.). Therefore, for y?0, this equation also has no entire solutions.

Hilbert's Tenth Problem

One way or another, the question arises: can any Diophantine equation be solved, that is, find its roots or prove their absence.

August 1900, the II International Congress of Mathematicians took place. On it, David Hilbert proposed 23 problems. The tenth was:

Let a Diophantine equation be given with arbitrary unknowns and integer rational numerical coefficients. Indicate a method by which it is possible, after a finite number of operations, to determine whether this equation is solvable in rational integers.

Many bright minds of the 20th century struggled with this task: AxelThue, TuralfSkolem, Emil Post, Julia Robinson, Martin Davis and Hilary Putnam, Martina Davis and others. And only in 1970, Yuri Matiyasevich completed the proof of the algorithmic unsolvability of this problem.

David Hilbert (January 23, 1862 - February 14, 1943) was a German mathematician who made a significant contribution to the development of many areas of mathematics. In the 1910s and 1920s (after the death of Henri Poincaré) he was the recognized world leader in mathematicians. In 1970, the International Astronomical Union named a crater on the far side of the Moon after Gilbert.

Yuri Vladimirovich Matiyasevich (born March 2, 1947, Leningrad) - Soviet and Russian mathematician, researcher at the St. Petersburg Department of the Mathematical Institute. V. A. Steklova RAS, Member of the Expert Commission of the RSOS in Mathematics, Academician of the Russian Academy of Sciences, Doctor of Physical and Mathematical Sciences

diophantine equation mathematical

Conclusion

This topic is multifaceted and almost boundless. It is not for nothing that world-famous scientists have puzzled over it throughout the history of the development of mathematics. It touches on fundamental concepts in mathematics, and knowledge of Diophantine equations, it seems to me, will never be exhaustive.

While doing this essay, I mastered the scattering method, learned how to solve systems of equations for problems about residuals, got acquainted with the history of mastering methods for solving Diophantine equations.

In the world of mathematics, which has long been wise and majestic, we are following the beaten path.

But everyone can become a pioneer: at first for themselves, and in the future, maybe for others ...

I think to continue working on this topic, to expand my knowledge in solving indefinite equations. The study of new solution methods enriches the knowledge base of any person, especially since they may be relevant for the USE (C6).

Bibliography

1. Magazine "Quantum" 1970 #7

.“Encyclopedia of a young mathematician” 520 p.

http://ilib.mirror1.mccme.ru/djvu/serp-int_eq.htm

Pichugin L.F. "Behind the pages of the textbook of algebra", M., 1990, 224p.

Glazer G.I. "History of mathematics at school 10-11", 351s

Petrakov I.A. "Mathematics for the Curious", M., 2000. 256s.

http://bars-minsk.narod.ru/teachers/diofant.html

Tutoring

Need help learning a topic?

Our experts will advise or provide tutoring services on topics of interest to you.
Submit an application indicating the topic right now to find out about the possibility of obtaining a consultation.