Theory of small numbers. Number theory: theory and practice

Number theory or higher arithmetic is a branch of mathematics that studies integers and similar objects.

Number theory deals with the study of the properties of integers. Currently, number theory includes a much wider range of issues that go beyond the study of natural numbers.

In number theory, not only natural numbers are considered, but also the set of all integers, the set rational numbers, a bunch of algebraic numbers. Modern number theory is characterized by the use of very various methods research. In modern number theory, methods are widely used mathematical analysis.

Modern theory numbers can be broken down into the following sections:

1) Elementary number theory. This section includes questions of number theory, which are direct development theories of divisibility and questions about the representability of numbers in a certain form. A more general problem is the problem of solving systems of Diophantine equations, that is, equations in which the values of the unknowns must necessarily be integers.

2) Algebraic theory numbers. This section includes questions related to the study of various classes of algebraic numbers.

3) Diophantine approximations. This section includes questions related to the study of real number approximation rational fractions. Closely related to the same circle of ideas, Diophantine approximations are closely related to the study of the arithmetic nature of various classes of numbers.

4) Analytical theory of numbers. This section includes questions of number theory, for the study of which it is necessary to apply methods of mathematical analysis.

Basic concepts:

1) Divisibility is one of the basic concepts of arithmetic and number theory associated with the division operation. From the point of view of set theory, the divisibility of integers is a relation defined on the set of integers.

If for some integer a and an integer b there is an integer q such that bq = a, then we say that the number a is divisible by b or that b divides a. In this case, the number b is called the divisor of the number a, the dividend of a will be a multiple of the number b, and the number q is called the quotient of a divided by b.

2) A simple number? is a natural number that has exactly two different natural divisor: unit and yourself. All other numbers except one are called composite numbers.

3) Perfect number? (ancient Greek ἀριθμὸς τέλειος) - natural number, equal to the sum all its own divisors (i.e. all positive divisors, different from itself? numbers).

The first perfect number is 6 (1 + 2 + 3 = 6), the next is 28 (1 + 2 + 4 + 7 + 14 = 28). As the natural numbers increase, perfect numbers are becoming less and less common.

4) The greatest common divisor (GCD) for two integers m and n is the largest of their common divisors. Example: for numbers 70 and 105 the largest common divisor equals 35.

The greatest common divisor exists and is uniquely determined if at least one of the numbers m or n is not zero.

5) The least common multiple (LCM) of two integers m and n is the smallest natural number that is divisible by m and n.

6) Numbers m and n are called coprime if they have no common divisors other than one. For such numbers GCD(m,n) = 1. Conversely, if GCD(m,n) = 1, then the numbers are coprime.

7) Euclidean algorithm - an algorithm for finding the greatest common divisor of two integers or the greatest common measure of two homogeneous quantities.

You can also find the information you are interested in in the scientific search engine Otvety.Online. Use the search form:

More on topic No. 17. Basic concepts of number theory:

Number theory is a branch of mathematics that studies the properties of numbers.

The main object of number theory is natural numbers (see Number). Their main property, which is considered by number theory, is divisibility. The first range of problems in number theory is factoring numbers. The main “building blocks” in this decomposition are prime numbers, i.e. numbers divisible only by 1 and themselves; 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 - these are the first ten prime numbers(the number 1 is not considered prime). Wonderful theorem, called the fundamental theorem of arithmetic, states: every natural number can be decomposed into prime factors, and the only way(up to the order of their location). By factoring two numbers into prime factors, it is easy to determine whether one of them is divisible by the other or not. But it can still be difficult to find out whether this is big number simple, i.e. whether it is divisible by any number other than itself and one.

The series associated with factoring numbers into prime factors is arithmetic functions. Let's point out some of them. φ(n) - Euler function - the number of numbers from 1 to n that are coprime to the number n (i.e. not sharing with n common factors, except for one); α(n) is the number of divisors of the number n, t(n) is the sum of all divisors of the number n, π(n) is the Chebyshev function - the number of prime numbers not exceeding n. These functions express many properties of natural numbers. Euclid's theorem states that there are infinitely many prime numbers. This means that π(n)→∞ as the number n increases. We were able to find out how quickly the function π(n) tends to infinity. It turned out that it is approximately the same as the function

This theorem is called the asymptotic law of distribution of prime numbers. It was formulated and largely proven by P. L. Chebyshev (1849), and was fully proven only 50 years later.

The asymptotic law of distribution of prime numbers is the result of the so-called analytic number theory, which widely uses methods of mathematical analysis to study number-theoretic functions. Discovered in the second half of the 19th century. the fact of the connection between such a discrete object as integers and the deep properties of functions had a great influence on the development of number theory.

Factoring numbers takes into account only the structure of the set of natural numbers associated with multiplication, the deepest and difficult tasks number theories arise from the comparison of addition and multiplication. Such problems include, for example, Goldbach's problem - is it possible to do anything? even number represent it as the sum of two primes; great theorem Fermat (see Fermat's last theorem) - is it possible nth power represent the numbers as sum n's powers of any two numbers, etc.

Number theory is attractive because it contains many simple formulations, but difficult and interesting tasks. A lot of these problems, solved and unsolved, have accumulated, and number theory often seems like a collection of disparate elegant puzzles. However, it is not. Number theory has created its own wonderful methods, and many of them have been actively developed in recent decades, which has injected a new living current into this very the ancient part mathematics.

The classical method of number theory is the method of comparisons. By identifying numbers that give identical remainders when divided by a selected number, it is often possible to establish the impossibility of any relationship. For example, considering the remainders of division by 3 (or, as they say, modulo 3), it is easy to prove the unsolvability of the equation 3x 2 + 4y 2 = 5z 2 in natural numbers.

Analytical method consists, as we have already said, in the fact that, starting from numbers, they construct functions that are studied by methods of mathematical analysis. Yes, Soviet scientist academician I.M. Vinogradov proved a version of Goldbach's problem - the representability of a sufficiently large odd number as a sum of three primes.

We illustrate the geometric method of number theory using Fermat's last theorem as an example. In this theorem we're talking about on the solvability of the equation x n + y n = z n in integers. Dividing both sides of the equation by z n and replacing x/z with m and y/z with v, we obtain the equation u n + v n = 1. This equation defines a certain curve on the plane with coordinates (u, v). Solutions to the original equation in integers correspond to solutions to the new equation in rational numbers. Each such solution (u, v) can be spoken of as a point with rational coordinates on this plane. Now we can try to apply geometric methods to the curve u n + v n = 1 to study the set of points with rational coordinates on it.

A large section of number theory, dealing with finding solutions to equations in integers and rational numbers, is called the theory of Diophantine equations, named after the ancient Greek scientist Diophantus (3rd century).

One of the very old and well-known problems in number theory is the problem of representing numbers by sums of squares. We list some of the results obtained:

each integer can be represented as the sum of four squares of integers (for example: 7 = 2 2 + 1 2 + 1 2 + 1 2);

every prime number of the form 4n + 1 can be represented as the sum of two squares of integers (for example: 5 = 2 2 + 1 2, 41 = 4 2 + 5 2, etc.), but not a single integer (not just a prime) a number of the form 4n + 3 cannot be represented in this form;

Every prime number, except numbers of the form 8n - 1, can be represented as the sum of three squares of integers.

Simple algebraic identity

(a 2 + b 2) (x 2 + y 2) = (ax + by) 2 + (ay - bx) 2

allows us to conclude: if two numbers are representable as the sum of two squares, then their product is also representable as the sum of two squares. Algebraic methods V Lately widely used in number theory. This was facilitated by the development of such a general algebraic concept as a field, the very appearance of which was largely stimulated by problems in number theory.

Why is number theory so valuable? After all, it is difficult to find direct application of its results. Nevertheless, number theory problems have attracted both inquisitive young people and scientists for many centuries. What's the matter here? First of all, these problems, as already mentioned, are very interesting and beautiful. At all times, people have been amazed that simple questions It's so hard to find an answer about numbers. The search for these answers has often led to discoveries whose significance far exceeds the scope of number theory. Suffice it to mention the so-called theory of ideals German mathematician XIX century E. Kummer, who was born in connection with attempts to prove Fermat's last theorem.

Name: Number theory. 2008.

The textbook is based on the results elementary theory numbers, formed in the works of the classics - Fermat, Euler, Gauss and others. Issues such as prime and composite numbers, arithmetic functions, the theory of comparisons, primitive roots and indices, continued fractions, algebraic and transcendental numbers are considered. The properties of prime numbers, the theory of Diophantine equations, algorithmic aspects of number theory with applications in cryptography (testing large prime numbers for primality, factorization large numbers into factors, discrete logarithm) and using a computer.
For university students.

The subject of the study of number theory is numbers and their properties, i.e. numbers appear here not as a means or instrument, but as an object of study. Natural series
1,2,3,4, ...,9,10,11, ...,99,100,101, ...
- the set of natural numbers - is the most important area of research, extremely informative, important and interesting.
The study of natural numbers began in Ancient Greece. Euclid and Eratosthenes discovered the properties of divisibility of numbers, proved the infinity of the set of prime numbers and found ways to construct them. Problems associated with the solution indeterminate equations in whole numbers, were the subject of research by Diophantus, as well as scientists Ancient India and Ancient China, Central Asian countries.

Table of contents
Introduction
Chapter 1. On the divisibility of numbers
1.1. Divisibility Properties of Integers
1.2. Least common multiple and greatest common divisor
1.3. Euclid's algorithm
1.4. Integer solution linear equations

Chapter 2. Prime and composite numbers
2.1. Prime numbers. Sieve of Eratosthenes. The infinity of the set of prime numbers
2.2. Fundamental Theorem of Arithmetic
2.3. Chebyshev's theorems
2.4. Riemann Zeta Function and Properties of Prime Numbers
Problems to solve independently
Chapter 3. Arithmetic Functions
3.1. Multiplicative functions and their properties
3.2. Möbius function and inversion formulas
3.3. Euler function
3.4. Sum of divisors and number of divisors natural number
3.5. Estimates of the mean value of arithmetic functions
Problems to solve independently
Chapter 4: Numerical Comparisons
4.1. Comparisons and their basic properties
4.2. Deduction classes. Ring of residue classes for a given module
4.3. Complete and reduced systems of deductions
4.4. Wilson's theorem
4.5. Euler's and Fermat's theorems
4.6. Representation of rational numbers as infinite decimals
4.7. Testing for primality and constructing large prime numbers
4.8. Integer factorization and cryptographic applications
Problems to solve independently
Chapter 5. Comparisons with one unknown
5.1.Basic definitions
5.2. Comparisons of the first degree
5.3.Chinese remainder theorem
5.4. Polynomial comparisons by simple module
5.5. Polynomial comparisons by composite moduloProblems for independent solution
Chapter 6. Comparisons of the second degree
6.1. Comparisons of the second degree modulo prime
6.2. Legendre's symbol and its properties
6.3. Quadratic reciprocity law
6.4. Jacobi symbol and its properties
6.5. Sums of two and four squares
6.6. Representation of zero quadratic forms from three variables
Problems to solve independently
Chapter 7. Antiderivative roots and indices
7.1. Indicator of a number for a given module
7.2. Existence of primitive roots modulo prime
7.3. Construction of primitive roots using modules pk and 2pk
7.4. Theorem on the absence of primitive roots in moduli other than 2, 4, pk and 2pk
7.5. Indexes and their properties
7.6. Discrete logarithm
7.7. Binomial comparisons
Problems to solve independently
Chapter 8. Continued Fractions
8.1. Dirichlet's theorem on the approximation of real numbers by rational numbers
8.2. Finite continued fractions
8.3. Continued fraction real number
8.4. Best Approximations
8.5. Equivalent numbers
8.6. Quadratic irrationalities and continued fractions
8.7. Using continued fractions to solve some Diophantine equations
8.8. Decomposition of the number e into a continued fraction
Problems to solve independently
Chapter 9. Algebraic and transcendental numbers
9.1.Field of algebraic numbers
9.2. Approximations of algebraic numbers by rational ones. Existence of transcendental numbers
9.3. The irrationality of the numbers er and n
9.4. Transcendence of the number e
9.5. Transcendence of the number n
9.6. Impossibility of squaring a circle
Problems to solve independently
Answers and directions
Bibliography

Free download e-book in a convenient format, watch and read:
Download the book Number Theory - Nesterenko Yu.V. - fileskachat.com, fast and free download.

Download djvu
Below you can buy this book at the best price with a discount with delivery throughout Russia.

Number theory1

1. Basic concepts of divisibility theory

Î DEFINITION. Number a is divisible by a non-zero number b if there is an integer c such that the equality a = b · c holds.

Designations:

1) a .b a is divided by b ;

2) b | a b divides a;

3) a is a multiple (multiple) of b , b of divisor a .

Division with remainder

Let two numbers a èb ,a Z ,b N be given, let Z be a set of integers, and N be a set of natural numbers. Divisible íàb with remainder a =b · q +r , ãäår lies in the interval 0≤ r< b ,q неполное частное,r остаток. Например, 7 = 2· 3 + 1.

Theorem 1. For any integer a and natural number b, the representation

a = b q+ r,0 ≤ r< b

only.

Ä î ê à ç à ò å ë ü ñ ò â î

1. Existence.

Let's consider infinite set numbers (a − tb) , ãäåa ,b fixed numbers, t any number, t Z . From it we will choose the smallest non-negative number r =a − q · b. Let us prove that r lies within

0 ≤ r< b.

Let this number not belong to this interval. Then it is greater than or equal to b. Let's construct a new number r ′ =r−b =a−q·b−b =a−b (q +1).

From this we can see the following:

1) r ′ (a − tb);

2) r ′ non-negative;

1 S.V. Fedorenko. September 2012. Course of lectures and tasks. Distributed freely. The course was taught at St. Petersburg State University of Aviation Administration (1997 1999; 2008 2011) and St. Petersburg State Pedagogical University (2002 2005).

3) r ′< r .

Therefore, not r , a r ′ is the smallest non-negative number from the set (a − tb) , then the assumption r ≥ b is false.

Existence has been proven.

2. Uniqueness.

Let there be another representation a =bq ′ +r ′ , provided that 0≤r′< b ;a ,b фиксированные числа,q Z . Т.е., мы можем разделить числоa íàb двумя способами, тогдаbq +r =bq ′ +r ′ . Moving the termsñq in one direction, and сr in the other, we obtain b (q − q ′ ) =r ′ − r . It is seen,

÷òî (r ′ − r ) .b . Each of the remainders is less than b и

(r′ − r) . b. |r′ − r|< b

Consequently, r ′ − r = 0, which means r ′ =r èq =q ′ . So, we have proven

that one number can be divided by another in a unique way. The theorem has been proven.

Theorem 2. If a .b èb .c , tòa .c , ãäåb, c ≠ 0.

a = b · q. b=c t

Therefore, a =c · qt. By definition it is clear that a .c .

Theorem 3. Let the equality a 1 +a 2 =b 1 +b 2 and the numbers a 1, a 2, b 1 .d be satisfied, then b 2 .d.

Ä î ê à ç à ò å ë ü ñ ò â î

a 1 =d · t 1 ,a 2 =d · t 2 ,b 1 =d · t 3 . Let us express b 2 from the conditions of the theorem b 2 = a 1 +a 2 − b 1 =d (t 1 +t 2 − t 3 ). By the definition of divisibility it is clear that b 2 .d .

2. Greatest common divisor

Î deﬁnition. If the number c is a divisor of the number a èb , then the number c is called a common divisor of the number a èb .

Definition. The greatest of the common divisors of the numbers a èb is called the greatest common divisor (GCD) of the numbers a èb.

Notation: (a, b) =d, ãäåa èb numbers, ad is the greatest common

divisor of these numbers.

Let's look at an example for the numbers 12 and 9. Let's write down all the divisors of 12 and all the divisors of 9. For 12: 1, 2, 3, 4, 6 and 12; for 9: 1, 3 and 9; it is clear that they have common divisors 1 and 3. Let's choose the largest of them is 3. Thus, (12, 9) = 3.

Definition. Two numbers a and b are called coprime if their gcd is equal to 1.

Example. Because (10,9)=1, then 10 and 9 are relatively prime numbers.

This definition can be extended to any number of numbers. If (a, b, c, . . . ) = 1, then the numbers a, b, c, . . . mutually simple. For example:

Î ï ð å ä ë å í è å. (a 1 , a 2 , ...a n ) are pairwise coprime numbers if the gcd of any pair equal to one(a i , a j ) = 1,i ≠ j .

For example: 12,17,11 are not only relatively prime, but also pairwise coprime.

Theorem 1. If a .b , then (a, b ) =b .

Ä î ê à ç à ò å ë ü ñ ò â î

The number b cannot be divided by a number greater than itself. Therefore, b is a GCD of èb .

Theorem 2. Let there be a representation a =bq +r (r is not necessarily the remainder), then (a, b) = (b, r).

Ä î ê à ç à ò å ë ü ñ ò â î

1. Consider any common divisor a èb c . Åñëa .c èb .c , tî

by Theorem 1.3 r .c , t.å.c is also a common divisor of b èr . Any common divisor a èb is a common divisor b èr.

2. Any common divisor b èr is a divisor of a. This means that the common divisors a, b èb, r coincide. This is also true for GCD.

3. Euclid's algorithm

For any numbers a èb using the Euclidean algorithm one can find

Let a ,b N be the input data of the algorithm, and (a, b ) =d N be the output.

		Bq 0	0 < r1 < b
		R 1 q 1	0 < r2 < r1
		R 2 q 2	0 < r3 < r2

	r i−2	R i−1 q i−1	0 < ri < ri− 1

	r n−2 = r n−1 q n−1 + r n		0 < rn < rn− 1
n+1	r n−1 = r nq n

Step 1. Divide a íàb with the remainder a =bq 0 +r 1 , ãäå 0< r 1 < b . По теореме 2.2 (a, b ) = (b, r 1 ).

Step 2. Divide b íàr 1 with remainder b =r 1 q 1 +r 2 , ãäå 0< r 2 < r 1 . Ïî теореме 2.2 (b, r 1 ) = (r 1 , r 2 ).

And so on until it is completely divided. From the chain of equalities

(a, b) = (b, r 1) = (r 1, r 2) = (r 2, r 3) =... = (r n− 2, r n− 1) = (r n− 1, r n) =r n

it follows that the last non-zero remainder r n will be the greatest common divisord =r n = (a, b ). Because the remainders decrease, then the algorithm will complete in final number steps.

Theorems related to the Euclidean algorithm

Theorem 1. The gcd of two numbers is divisible by any common divisor of these

Åñëè (a, b) =d, òî (a c, c b) =d c, ãäå c common divisor a èb.

Ä î ê à ç à ò å ë ü ñ ò â î

Â entries of the Euclidean algorithm a, b и âñår i will divide us. We get

recording of the Euclidean algorithm with input data a b

name a		c èc . From it it is clear
name a
	è c	equals c.

Theorem 2. If two numbers are divided by their gcd, we obtain relatively prime numbers (a d, d b) = 1.

Ä î ê à ç à ò å ë ü ñ ò â î

Theorem 3. If

Instead of c (from Theorem 1) we substitute d.

(a, b) = 1, tòîc .b .ac . b

Ä î ê à ç à ò å ë ü ñ ò â î

For relatively prime numbers a èb, according to Theorem 7.1, there is a representation ax +by = 1. Multiplying this equality by c, we have ac ·x +byc =c,

íî ac =bq ,bqx +byc =c ,b (qx +yc ) =c . Therefore, c .b .

GCD of several numbers

(a1 , a2 , . . . , an ) = dn (a1 , a2 ) = d2

(d 2 , a 3 ) =d 3

(d n− 1 , a n ) =d n

4. Least common multiple

Î DEFINITION: Common multiple of two numbers a èb is a number that is divisible by both of these numbers a èb.

Î DEFINITION: Smallest common multiple a èb is called the least common multiple (LCM) of a èb.

Let M .a èM .b , then M is a common multiple of a èb . We denote the least common multiple of a èb as .

Theorem 1. LCM of two numbers equal to the ratio their works to

=(a, ab b) .

Ä î ê à ç à ò å ë ü ñ ò â î

Let us denote some common multiple of the numbers a èb by M , then M .

a èM .b . In addition,d = (a, b),a =a ′ d,b =b ′ d, and (a ′, b ′) = 1. By definition of divisibilityM =a · k, ãäåk Z




					a′ dk				a′ k
					b′ d				b′

a ′ is not divisible by b ′ , because they are relatively prime, therefore k .b ′ from Theorem 3.3

k = b′ t=




M = a · k=
					(a, b)

form of any common multiple of a èb. Ïðèt = 1M is the LCM of the number a èb .

LCM of several numbers

[a1, a2, . . . , an ] = Mn [ a1 , a2 ] = M2

M 3 = M 4

Åñëè (a, b) = 1, tòî =ab. Pr (a i , a j ) = 1,i ≠ j ,M =a 1 a 2 · . . . · a n .

5. Prime and composite numbers

Any number is divisible by 1 and itself. Let's call these divisors trivial.

Definition: A number is called prime if it has no nontrivial divisors. A number is called composite if it has a non-trivial divisor. The number 1 is neither prime nor composite.

Theorem 1. For any natural number a and prime number p

is satisfied or (a, p ) = 1 èëèa .p .

Ä î ê à ç à ò å ë ü ñ ò â î

The prime number p has two trivial divisors. Possible

two options: a .p èëèa ̸ .p . Åñëèa ̸ .p , then the GCD of èp is 1. Therefore, (a, p ) = 1.

Theorem 2. The smallest divisor of an integer different from one, greater than one, is a prime number.

Ä î ê à ç à ò å ë ü ñ ò â î

Åñëè a ≠ 1, òîa =p·q , ãäåp is the smallest non-trivial divisor. Suppose p is a composite number. This means that there is

such a number s , ÷òîp .s , but then a .s èp is not least divisor, which contradicts the condition. T.o.p is a prime number.

Theorem 3. Smallest nontrivial divisor composite number does not exceed its root.

Ä î ê à ç à ò å ë ü ñ ò â î

a = q b, q ≤ b, q2 ≤ bq= a, q ≤ a.

Sieve of Eratosthenes

Let's write down the set of natural numbers

1 ,2 ,3 ,4 ,5 ,6 ,7 ,8 ,9 ,10 ,11 ,12 ,13 ,14 ,15 ,16 ,17 ,18 , . . .

Unit is special number. We proceed with the remaining numbers in the following way: take a number, declare it prime and cross out the multiples of it.

For example, 2 is a prime number, we cross out the numbers that are multiples of two, therefore, there will be no even numbers left. Let's do the same with the three. You need to cross out 6, 9, 12, 15, 18, etc. All remaining numbers are prime.

Theorem 4. The set of prime numbers is infinite. Proof

Let ( 2, 3, 5, . . . , P) be a finite set of prime numbers and N = 2· 3· 5·. . .·P +1.N is not divisible by any of the prime numbers, because when divided, the remainder is 1. But the smallest non-trivial divisor N according to Theorem 2 is a prime number 2(, 3, 5, . . . , P). Consequently, the number of prime numbers is not a finite set, but an infinite one.

6. Canonical form of the number

Theorem 1 (Fundamental Theorem of Arithmetic). Any number other than 1 can only be represented as a product of prime numbers.

Ä î ê à ç à ò å ë ü ñ ò â î

1. Existence.

The number n, by Theorem 5.2, has a prime divisor p 1

n n 1 = p 1 .

Similar reasoning is valid for the number n 1

n2 = n 1 ,p 2

ãäå p 2 prime divisor n 1. And we will continue this way until we get n i = 1.

2. Uniqueness.

Let the number n have two prime number decompositions

n = p1 · p2 · . . . · pl = q1 · q2 · . . . · qs.

Without loss of generality, we accept l ≤ s. If left side equality is divisible by 1, then the right one is also divisible by 1. This means that some q i =p 1 . Let it be q 1 =p 1 . Divide both sides of the equality by 1

Similarly, let's accept q 2 = p 2 . We will continue this procedure until the expression takes the form

1 = ql +1 · . . . · qs.

Åñëè l< s , то произведение простых чисел не может быть равно 1. Следовательно, предположение о двух различных разложениях числаn невер-

íî. Åsëè s =l , tòp i =q i äëÿi and the two expansions coincide. The theorem has been proven.

Any number n N can be written in canonical form

n = p1 s 1 · . . . · pl s l ,

L p i are prime numbers, s i N .

The canonical representation allows you to write down all the divisors of a number and determine the GCD and LCM.

All divisors c of the number n have the form

c = p1 i 1 · p2 i 2 . . . pl i l ,ãäå ij .

Finding GCD and LCM

Let the numbers a and b be represented in the form

a = p1 s 1 · p2 s 2 · . . . · pl s l b= p1 t 1 · p2 t 2 · . . . · pl t l .

This representation differs from the canonical one in that some s i и t i can be equal to 0.

Then the greatest common divisor a èb

(a, b) = p1 min (s 1 ,t 1 ) · p2 min (s 2 ,t 2 ) · . . . · pl min (s l ,t l ) ,

and the least common multiple is:

[ a, b] = p1 max (s 1 ,t 1 ) · p2 max (s 2 ,t 2 ) · . . . · pl max (s l ,t l ) .

From here it is also clear that (a, b) is divisible by any common divisor a èb.

7. Linear Diophantine equations with two unknowns

Î D e ﬁ nition. A linear Diophantine equation with two unknowns is an equation of the form

ax + by= c,

where the coefficients a, b, c and the unknowns x, y are integers, aa and b are not equal to zero at the same time.

Theorem 1 (On the linear representation of GCD). For any pair of numbers (a, b) ((a, b) ≠ (0, 0)) there are such x, y Z, ÷òîax +by =(a, b).

Ä î ê à ç à ò å ë ü ñ ò â î

Consider the set of numbers (ax + by) and select the minimum from it positive number d =ax 0 +by 0 .

Let us prove that d is a divisor of b.

Let d not be a divisorb, therefore,b =d q +r, ãäå 0< r < d ,

r = b − dq= b −(ax0 + by0 ) q= a(−x0 q) + b(1 − y0 q). It's clear that:

1) number r (ax +by) ;

2) r is positive;

3) r< d .

But we assumed that d is the smallest positive number from this set, hence our assumption that r< d неверно, значитd делительb .

Similarly, we can prove that a .d .

From all this it follows that d is a common divisor of a èb.

a. (a, b)

Kostak, b. (a, b) d. (a, b), íîd is the common divisor of a èb, therefore, d ÍÎÄ a è b.

Theorem 2. The equation ax +by =c has a solution if and only ifc is divisible by (a, b).

Ä î ê à ç à ò å ë ü ñ ò â î

1. Letc. (a, b), then by Theorem 1 ax+by= (a, b). Multiply the equation by c

( a,b )

a (a,xcb) + b (a,ycb) = c.

A pair of numbers ( x0 , y0 ) will be a solution to the original equation

{ x0 = (a,bxc)y0 = (a,byc).

2. Let us prove that if the equation has a solution, then c. (a, b).

a. (a, b) , hence, c must also be divisible by ( a, b).

b . ( a, b )