Rank and classes. Numbers

Integers

The numbers used in counting are called natural numbers. For example, $1,2,3$, etc. The natural numbers form the set of natural numbers, which is denoted by $N$. This designation comes from the Latin word naturalis- natural.

Opposite numbers

Definition 1

If two numbers differ only in signs, they are called in mathematics opposite numbers.

For example, the numbers $5$ and $-5$ are opposite numbers, because They differ only in signs.

Note 1

For any number there is an opposite number, and only one.

Note 2

The number zero is the opposite of itself.

Whole numbers

Definition 2

Whole numbers are the natural numbers, their opposites, and zero.

The set of integers includes the set of natural numbers and their opposites.

Denote integers $Z.$

Fractional numbers

Numbers of the form $\frac(m)(n)$ are called fractions or fractional numbers. Fractional numbers can also be written in decimal form, i.e. in the form of decimal fractions.

For example: $\ \frac(3)(5)$ , $0.08$ etc.

Just like whole numbers, fractional numbers can be either positive or negative.

Rational numbers

Definition 3

Rational numbers is a set of numbers containing a set of integers and fractions.

Any rational number, both integer and fractional, can be represented as a fraction $\frac(a)(b)$, where $a$ is an integer and $b$ is a natural number.

Thus, the same rational number can be written in different ways.

For example,

This shows that any rational number can be represented as a finite decimal fraction or an infinite decimal periodic fraction.

The set of rational numbers is denoted by $Q$.

As a result of performing any arithmetic operation on rational numbers, the resulting answer will be a rational number. This is easily provable, due to the fact that when adding, subtracting, multiplying and dividing ordinary fractions, you get an ordinary fraction

Irrational numbers

While studying a mathematics course, you often have to deal with numbers that are not rational.

For example, to verify the existence of a set of numbers other than rational ones, let’s solve the equation $x^2=6$. The roots of this equation will be the numbers $\surd 6$ and -$\surd 6$. These numbers will not be rational.

Also, when finding the diagonal of a square with side $3$, we apply the Pythagorean theorem and find that the diagonal will be equal to $\surd 18$. This number is also not rational.

Such numbers are called irrational.

So, an irrational number is an infinite non-periodic decimal fraction.

One of the frequently encountered irrational numbers is the number $\pi $

When performing arithmetic operations with irrational numbers, the resulting result can be either a rational or an irrational number.

Let's prove this using the example of finding the product of irrational numbers. Let's find:

$\ \sqrt(6)\cdot \sqrt(6)$

$\ \sqrt(2)\cdot \sqrt(3)$

By decision

$\ \sqrt(6)\cdot \sqrt(6) = 6$

$\sqrt(2)\cdot \sqrt(3)=\sqrt(6)$

This example shows that the result can be either a rational or an irrational number.

If rational and irrational numbers are involved in arithmetic operations at the same time, then the result will be an irrational number (except, of course, multiplication by $0$).

Real numbers

The set of real numbers is a set containing the set of rational and irrational numbers.

The set of real numbers is denoted by $R$. Symbolically, the set of real numbers can be denoted by $(-?;+?).$

We said earlier that an irrational number is an infinite decimal non-periodic fraction, and any rational number can be represented as a finite decimal fraction or an infinite decimal periodic fraction, so any finite and infinite decimal fraction will be a real number.

When performing algebraic operations the following rules will be followed

When multiplying and dividing positive numbers, the resulting number will be positive
When multiplying and dividing negative numbers, the resulting number will be positive
When multiplying and dividing negative and positive numbers, the resulting number will be negative

Real numbers can also be compared with each other.

Number is an abstraction used to quantify objects. Numbers arose in primitive society in connection with the need of people to count objects. Over time, as science developed, number turned into the most important mathematical concept.

To solve problems and prove various theorems, you need to understand what types of numbers there are. Basic types of numbers include: natural numbers, integers, rational numbers, real numbers.

Integers- these are numbers obtained by natural counting of objects, or rather by numbering them (“first”, “second”, “third”...). The set of natural numbers is denoted by a Latin letter N (can be remembered based on the English word natural). It can be said that N ={1,2,3,....}

Whole numbers– these are numbers from the set (0, 1, -1, 2, -2, ....). This set consists of three parts - natural numbers, negative integers (the opposite of natural numbers) and the number 0 (zero). Integers are denoted by a Latin letter Z . It can be said that Z ={1,2,3,....}.

Rational numbers are numbers represented as a fraction, where m is an integer and n is a natural number. The Latin letter is used to denote rational numbers Q . All natural numbers and integers are rational.

Real numbers are numbers that are used to measure continuous quantities. The set of real numbers is denoted by the Latin letter R. Real numbers include rational numbers and irrational numbers. Irrational numbers are numbers that are obtained as a result of performing various operations with rational numbers (for example, taking roots, calculating logarithms), but are not rational.

1. Number systems.

A number system is a way of naming and writing numbers. Depending on the method of representing numbers, they are divided into positional - decimal and non-positional - Roman.

PCs use 2-digit, 8-digit and 16-digit number systems.

Differences: the recording of a number in the 16th number system is much shorter compared to another recording, i.e. requires less bit capacity.

In a positional number system, each digit retains its constant value regardless of its position in the number. In a positional number system, each digit determines not only its meaning, but also depends on the position it occupies in the number. Each number system is characterized by a base. A base is the number of different digits that are used to write numbers in a given number system. The base shows how many times the value of the same digit changes when moving to an adjacent position. The computer uses a 2-number system. The base of the system can be any number. Arithmetic operations on numbers in any position are performed according to rules similar to the 10 number system. Number 2 uses binary arithmetic, which is implemented in a computer to perform arithmetic calculations.

Addition of binary numbers:0+0=1;0+1=1;1+0=1;1+1=10

Subtraction:0-0=0;1-0=1;1-1=0;10-1=1

Multiplication:0*0=0;0*1=0;1*0=0;1*1=1

The computer widely uses the 8 number system and the 16 number system. They are used to shorten binary numbers.

2. The concept of set.

The concept of “set” is a fundamental concept in mathematics and has no definition. The nature of the generation of any set is diverse, in particular, surrounding objects, living nature, etc.

Definition 1: The objects from which a set is formed are called elements of this set. To denote a set, capital letters of the Latin alphabet are used: for example, X, Y, Z, and its elements are written in lowercase letters in curly brackets separated by commas, for example: (x,y,z).

An example of notation for a set and its elements:

X = (x 1, x 2,…, x n) – a set consisting of n elements. If the element x belongs to the set X, then it should be written: xÎX, otherwise the element x does not belong to the set X, which is written: xÏX. Elements of an abstract set can be, for example, numbers, functions, letters, shapes, etc. In mathematics, in any section, the concept of set is used. In particular, we can give some specific sets of real numbers. The set of real numbers x satisfying the inequalities:

· a ≤ x ≤ b is called segment and is denoted by ;

a ≤ x< b или а < x ≤ b называется half-segment and is denoted by: ;

· A< x < b называется interval and is denoted by (a,b).

Definition 2: A set that has a finite number of elements is called finite. Example. X = (x 1 , x 2 , x 3 ).

Definition 3: The set is called endless, if it consists of an infinite number of elements. For example, the set of all real numbers is infinite. Example entry. X = (x 1, x 2, ...).

Definition 4: A set that does not have a single element is called an empty set and is denoted by the symbol Æ.

A characteristic of a set is the concept of power. Power is the number of its elements. The set Y=(y 1 , y 2 ,...) has the same cardinality as the set X=(x 1 , x 2 ,...) if there is a one-to-one correspondence y= f(x) between the elements of these sets. Such sets have the same cardinality or are of equal cardinality. An empty set has zero cardinality.

3. Methods for specifying sets.

It is believed that a set is defined by its elements, i.e. the set is given, if we can say about any object: it belongs to this set or does not belong. You can specify a set in the following ways:

1) If a set is finite, then it can be defined by listing all its elements. So, if the set A consists of elements 2, 5, 7, 12 , then they write A = (2, 5, 7, 12). Number of elements of the set A equals 4 , they write n(A) = 4.

But if the set is infinite, then its elements cannot be enumerated. It is difficult to define a set by enumeration and a finite set with a large number of elements. In such cases, another method of specifying the set is used.

2) A set can be specified by indicating the characteristic property of its elements. Characteristic property- This is a property that every element belonging to a set has, and not a single element that does not belong to it. Consider, for example, a set X of two-digit numbers: the property that each element of this set has is “to be a two-digit number.” This characteristic property makes it possible to decide whether an object belongs to the set X or does not belong. For example, the number 45 is contained in this set because it is two-digit, and the number 4 does not belong to the set X, because it is unambiguous and not two-valued. It happens that the same set can be defined by indicating different characteristic properties of its elements. For example, a set of squares can be defined as a set of rectangles with equal sides and as a set of rhombuses with right angles.

In cases where the characteristic property of the elements of a set can be represented in symbolic form, a corresponding notation is possible. If the set IN consists of all natural numbers less than 10, then they write B = (x N | x<10}.

The second method is more general and allows you to specify both finite and infinite sets.

4. Numerical sets.

Numerical - a set whose elements are numbers. Numerical sets are specified on the axis of real numbers R. On this axis, the scale is chosen and the origin and direction are indicated. The most common number sets:

· - set of natural numbers;

· - set of integers;

· - set of rational or fractional numbers;

· - set of real numbers.

5. Power of the set. Give examples of finite and infinite sets.

Sets are called equally powerful or equivalent if there is a one-to-one or one-to-one correspondence between them, that is, a pairwise correspondence. when each element of one set is associated with a single element of another set and vice versa, while different elements of one set are associated with different elements of another.

For example, let's take a group of thirty students and issue exam tickets, one ticket to each student from a stack containing thirty tickets, such a pairwise correspondence of 30 students and 30 tickets will be one-to-one.

Two sets of equal cardinality with the same third set are of equal cardinality. If the sets M and N are of equal cardinality, then the sets of all subsets of each of these sets M and N are also of equal cardinality.

A subset of a given set is a set such that each element of it is an element of the given set. So the set of cars and the set of trucks will be subsets of the set of cars.

The power of the set of real numbers is called the power of the continuum and is denoted by the letter “alef” א . The smallest infinite domain is the cardinality of the set of natural numbers. The cardinality of the set of all natural numbers is usually denoted by (alef-zero).

Powers are often called cardinal numbers. This concept was introduced by the German mathematician G. Cantor. If sets are denoted by symbolic letters M, N, then cardinal numbers are denoted by m, n. G. Cantor proved that the set of all subsets of a given set M has a cardinality greater than the set M itself.

A set equal to the set of all natural numbers is called a countable set.

6. Subsets of the specified set.

If we select several elements from our set and group them separately, then this will be a subset of our set. There are many combinations from which a subset can be obtained; the number of combinations only depends on the number of elements in the original set.

Let us have two sets A and B. If each element of set B is an element of set A, then set B is called a subset of A. Denoted: B ⊂ A. Example.

How many subsets of the set A=1;2;3 are there?

Solution. Subsets consisting of elements of our set. Then we have 4 options for the number of elements in the subset:

A subset can consist of 1 element, 2, 3 elements and can be empty. Let's write down our elements sequentially.

Subset of 1 element: 1,2,3

Subset of 2 elements: 1,2,1,3,2,3.

Subset of 3 elements: 1;2;3

Let's not forget that the empty set is also a subset of our set. Then we find that we have 3+3+1+1=8 subsets.

7. Operations on sets.

Certain operations can be performed on sets, similar in some respects to operations on real numbers in algebra. Therefore, we can talk about set algebra.

Association(connection) of sets A And IN is a set (symbolically it is denoted by ), consisting of all those elements that belong to at least one of the sets A or IN. In form from X the union of sets is written as follows

The entry reads: “unification A And IN" or " A, combined with IN».

Set operations are visually represented graphically using Euler circles (sometimes the term “Venn-Euler diagrams” is used). If all elements of the set A will be concentrated within the circle A, and the elements of the set IN- within a circle IN, the operation of unification using Euler circles can be represented in the following form

Example 1. Union of many A= (0, 2, 4, 6, 8) even digits and sets IN= (1, 3, 5, 7, 9) odd digits is the set = =(0, 1, 2, 3, 4, 5, 6, 7, 8, 9) of all digits of the decimal number system.

8. Graphic representation of sets. Euler-Venn diagrams.

Euler-Venn diagrams are geometric representations of sets. The construction of the diagram consists of drawing a large rectangle representing the universal set U, and inside it - circles (or some other closed figures) representing sets. The shapes must intersect in the most general way required by the problem and must be labeled accordingly. Points lying inside different areas of the diagram can be considered as elements of the corresponding sets. With the diagram constructed, you can shade certain areas to indicate newly formed sets.

Set operations are considered to obtain new sets from existing ones.

Definition. Association sets A and B is a set consisting of all those elements that belong to at least one of the sets A, B (Fig. 1):

Definition. By crossing sets A and B is a set consisting of all those and only those elements that belong simultaneously to both set A and set B (Fig. 2):

Definition. By difference sets A and B is the set of all those and only those elements of A that are not contained in B (Fig. 3):

Definition. Symmetrical difference sets A and B is the set of elements of these sets that belong either only to set A or only to set B (Fig. 4):

Cartesian (or direct) product of setsA And B such a resulting set of pairs of the form ( x,y) constructed in such a way that the first element from the set A, and the second element of the pair is from the set B. Common designation:

A× B={(x,y)|x∈A,y∈B}

Products of three or more sets can be constructed as follows:

A× B× C={(x,y,z)|x∈A,y∈B,z∈C}

Products of the form A× A,A× A× A,A× A× A× A etc. It is customary to write it as a degree: A 2 ,A 3 ,A 4 (the base of the degree is the multiplier set, the exponent is the number of products). They read such an entry as a “Cartesian square” (cube, etc.). There are other readings for the main sets. For example, R n It is customary to read as “er nnoe”.

Properties

Let's consider several properties of the Cartesian product:

1. If A,B are finite sets, then A× B- final. And vice versa, if one of the factor sets is infinite, then the result of their product is an infinite set.

2. The number of elements in a Cartesian product is equal to the product of the numbers of elements of the factor sets (if they are finite, of course): | A× B|=|A|⋅|B| .

3. A np ≠(A n) p- in the first case, it is advisable to consider the result of the Cartesian product as a matrix of dimensions 1× n.p., in the second - as a matrix of sizes n× p .

4. The commutative law is not satisfied, because pairs of elements of the result of a Cartesian product are ordered: A× B≠B× A .

5. The associative law is not fulfilled: ( A× B)× C≠A×( B× C) .

6. There is distributivity with respect to basic operations on sets: ( A∗B)× C=(A× C)∗(B× C),∗∈{∩,∪,∖}

10. The concept of utterance. Elementary and compound statements.

Statement is a statement or declarative sentence that can be said to be true (I-1) or false (F-0), but not both.

For example, “It’s raining today,” “Ivanov completed laboratory work No. 2 in physics.”

If we have several initial statements, then from them, using logical unions or particles we can form new statements, the truth value of which depends only on the truth values of the original statements and on the specific conjunctions and particles that participate in the construction of the new statement. The words and expressions “and”, “or”, “not”, “if..., then”, “therefore”, “then and only then” are examples of such conjunctions. The original statements are called simple , and new statements constructed from them with the help of certain logical conjunctions - composite . Of course, the word “simple” has nothing to do with the essence or structure of the original statements, which themselves can be quite complex. In this context, the word “simple” is synonymous with the word “original”. What matters is that the truth values of simple statements are assumed to be known or given; in any case, they are not discussed in any way.

Although a statement like “Today is not Thursday” is not composed of two different simple statements, for uniformity of construction it is also considered as a compound, since its truth value is determined by the truth value of the other statement “Today is Thursday.”

Example 2. The following statements are considered as components:

I read Moskovsky Komsomolets and I read Kommersant.

If he said it, then it's true.

The sun is not a star.

If it is sunny and the temperature exceeds 25 0, I will arrive by train or car

Simple statements included in compounds can themselves be completely arbitrary. In particular, they themselves can be composite. The basic types of compound statements described below are defined independently of the simple statements that form them.

11. Operations on statements.

1. Negation operation.

By negating the statement A ( reads "not A", "it is not true that A"), which is true when A false and false when A– true.

Statements that deny each other A And are called opposite.

2. Conjunction operation.

Conjunction statements A And IN is called a statement denoted by A B(reads " A And IN"), the true values of which are determined if and only if both statements A And IN are true.

The conjunction of statements is called a logical product and is often denoted AB.

Let a statement be given A- “in March the air temperature is from 0 C to + 7 C" and saying IN- “It’s raining in Vitebsk.” Then A B will be as follows: “in March the air temperature is from 0 C to + 7 C and it’s raining in Vitebsk.” This conjunction will be true if there are statements A And IN true. If it turns out that the temperature was less 0 C or there was no rain in Vitebsk, then A B will be false.

3 . Disjunction operation.

Disjunction statements A And IN called a statement A B (A or IN), which is true if and only if at least one of the statements is true and false - when both statements are false.

The disjunction of statements is also called a logical sum A+B.

The statement " 4<5 or 4=5 " is true. Since the statement " 4<5 " is true, and the statement " 4=5 » – false, then A B represents the true statement " 4 5 ».

4 . Operation of implication.

By implication statements A And IN called a statement A B("If A, That IN", "from A should IN"), whose value is false if and only if A true, but IN false.

In implication A B statement A called basis, or premise, and the statement IN – consequence, or conclusion.

12. Tables of truth of statements.

A truth table is a table that establishes a correspondence between all possible sets of logical variables included in a logical function and the values of the function.

Truth tables are used for:

Calculating the truth of complex statements;

Establishing the equivalence of statements;

Definitions of tautologies.

This article is devoted to the topic "Real numbers". The article gives a definition of real numbers, illustrates their position on the coordinate line, and discusses ways to specify real numbers using numerical expressions.

Definition of real numbers

Whole numbers and fractions together make up rational numbers. In turn, rational and irrational numbers make up real numbers. How to define what real numbers are?

Definition 1

Real numbers- these are rational and irrational numbers. The set of real numbers is denoted by R.

This definition can be written differently, taking into account the following:

Rational numbers can be represented as a finite decimal or an infinite periodic decimal.
Irrational numbers are infinite non-periodic decimal fractions.

Definition 2

Real numbers- numbers that can be written as a finite or infinite (periodic or non-periodic) decimal fraction.

Real numbers are any rational and irrational numbers. Here are examples of such numbers: 0 ; 6; 458; 1863; 0, 578; - 3 8; 26 5; 0, 145 (3); log 5 12 .

Zero is also a real number. By definition, there are both positive and negative real numbers. Zero is the only real number that is neither positive nor negative.

Another name for real numbers is real numbers. These numbers make it possible to describe the value of a continuously changing quantity without introducing a reference (unit) value of this quantity.

The coordinate line and real numbers

Each point on a non-coordinate line corresponds to a specific and unique real number. In other words, real numbers occupy the entire coordinate line, and there is a one-to-one correspondence between the points of the curve and the numbers.

Real number representations

The definition of real numbers includes:

Integers.
Whole numbers.
Decimals.
Ordinary fractions.
Mixed numbers.

Also, real numbers are often represented as expressions with powers, roots, and logarithms. The sum, difference, product and quotient of real numbers are also real numbers.

The value of any expression made up of real numbers will also be a real number.

For example, the values of the expressions sin 2 3 π · e - 2 8 5 · 10 log 3 2 and t g 6 7 6 693 - 8 π 3 2 are real numbers.

If you notice an error in the text, please highlight it and press Ctrl+Enter

The concept of a real number: real number- (real number), any non-negative or negative number or zero. Real numbers are used to express measurements of each physical quantity.

Real, or real number arose from the need to measure the geometric and physical quantities of the world. In addition, for performing root extraction operations, calculating logarithms, solving algebraic equations, etc.

Natural numbers were formed with the development of counting, and rational numbers with the need to manage parts of a whole, then real numbers (real) are used to measure continuous quantities. Thus, the expansion of the stock of numbers that are considered led to the set of real numbers, which, in addition to rational numbers, consists of other elements called irrational numbers.

Set of real numbers(denoted R) are sets of rational and irrational numbers collected together.

Real numbers divided byrational And irrational.

The set of real numbers is denoted and often called real or number line. Real numbers consist of simple objects: whole And rational numbers.

A number that can be written as a ratio, wherem is an integer, and n- natural number, isrational number.

Any rational number can easily be represented as a finite fraction or an infinite periodic decimal fraction.

Example,

Infinite decimal, is a decimal fraction that has an infinite number of digits after the decimal point.

Numbers that cannot be represented in the form are irrational numbers.

Example:

Any irrational number can easily be represented as an infinite non-periodic decimal fraction.

Example,

Rational and irrational numbers create set of real numbers. All real numbers correspond to one point on the coordinate line, which is called number line.

For numerical sets the following notation is used:

N- set of natural numbers;
Z- set of integers;
Q- set of rational numbers;
R- set of real numbers.

Theory of infinite decimal fractions.

A real number is defined as infinite decimal, i.e.:

±a 0 ,a 1 a 2 …a n …

where ± is one of the symbols + or −, a number sign,

a 0 is a positive integer,

a 1 ,a 2 ,…a n ,… is a sequence of decimal places, i.e. elements of a numerical set {0,1,…9}.

An infinite decimal fraction can be explained as a number that lies between rational points on the number line like:

±a 0 ,a 1 a 2 …a n And ±(a 0 ,a 1 a 2 …a n +10 −n) for all n=0,1,2,…

Comparison of real numbers as infinite decimal fractions occurs place-wise. For example, suppose we are given 2 positive numbers:

α =+a 0 ,a 1 a 2 …a n …

β =+b 0 ,b 1 b 2 …b n …

If a 0 0, That α<β ; If a 0 >b 0 That α>β . When a 0 =b 0 Let's move on to the comparison of the next category. Etc. When α≠β , which means that after a finite number of steps the first digit will be encountered n, such that a n ≠b n. If a n n, That α<β ; If a n >b n That α>β .

But it is tedious to pay attention to the fact that the number a 0 ,a 1 a 2 …a n (9)=a 0 ,a 1 a 2 …a n +10 −n . Therefore, if the record of one of the numbers being compared, starting from a certain digit, is a periodic decimal fraction with 9 in the period, then it must be replaced with an equivalent record with a zero in the period.

Arithmetic operations with infinite decimal fractions are a continuous continuation of the corresponding operations with rational numbers. For example, the sum of real numbers α And β is a real number α+β , which satisfies the following conditions:

∀ a′,a′′,b′,b′′∈ Q(a′⩽ α ⩽ a′′)∧ (b′⩽ β ⩽ b′′)⇒ (a′+b′⩽ α + β ⩽ a′′+b′′)

The operation of multiplying infinite decimal fractions is defined similarly.

Numbers are divided into classes. Positive integers - N = (1, 2, 3, ...) - make up the set of natural numbers. Often, 0 is considered a natural number.

The set of integers Z includes all natural numbers, the number 0 and all natural numbers taken with a minus sign: Z = (0, 1, -1, 2, -2, ...).

Each rational number x can be specified as a pair of integers (m, n), where m is the numerator, n is the denominator of the number: x = m/n. An equivalent representation of a rational number is to express it as a number written in positional decimal notation, where the fractional part of the number can be a finite or infinite periodic fraction. For example, the number x = 1/3 = 0,(3) is represented as an infinite periodic fraction.

Numbers defined by infinite non-periodic fractions are called irrational numbers. These are, for example, all numbers of the form vp, where p is a prime number. The numbers known to everyone and e are irrational.

The union of the sets of integers, rational and irrational numbers constitutes the set of real numbers. The geometric image of the set of real numbers is a straight line - the real axis, where each point on the axis corresponds to a certain real number, so that the real numbers densely and continuously fill the entire real axis.

The plane represents the geometric image of a set of complex numbers, where two axes are introduced - real and imaginary. Each complex number, defined by a pair of real numbers, is representable in the form: x = a+b*i, where a and b are real numbers, which can be considered as the Cartesian coordinates of the number on the plane.

Divisors and multipliers

Let us now consider a classification that divides the set of natural numbers into two subsets - prime and composite numbers. This classification is based on the concept of divisibility of natural numbers. If n is divisible by d, then we say that d “divides” n, and write it in the form: . Note that this definition may not correspond to the intuitive understanding: d "divides" n if n is divisible by d, and not vice versa. The number d is called the divisor of n. Each number n has two trivial factors - 1 and n. Divisors other than trivial ones are called factors of n. A number n is called prime if it has no divisors other than trivial ones. Prime numbers are divisible only by 1 and themselves. Numbers that have factors are called composite numbers. The number 1 is a special number because it is neither a prime nor a composite number. Negative numbers also do not belong to either prime or composite numbers, but you can always consider the modulus of a number and classify it as a prime or composite number.

Any composite number N can be represented as a product of its factors: . This representation is not unique, for example 96 = 8*12 = 2*3*16. However, for each composite number N there is a unique representation in the form of a product of powers of prime numbers: , where are prime numbers and . This representation is called the factorization of the number N into prime factors. For example .

If and , then d is a common divisor of the numbers m and n. Among all common divisors, we can distinguish the greatest common divisor, denoted as gcd(m,n). If gcd(m,n) = 1, then the numbers m and n are called coprime. Prime numbers are coprime, so gcd(q,p) =1 if q and p are prime numbers.

If and , then A is a common multiple of m and n. Among all common multiples, we can distinguish the least common multiple, denoted as LCM(m,n). If LCM(m,n) = m*n, then the numbers m and n are relatively prime. LCM(q, p) =q*p if q and p are prime numbers.

If we denote the sets of all prime factors of the numbers m and n by and, then

If the decomposition of the numbers m and n into prime factors is obtained, then, using the given relations, it is easy to calculate GCD(m,n) and LCM(m,n). There are also more efficient algorithms that do not require factoring a number.

Euclid's algorithm

An effective algorithm for calculating GCD(m,n) was proposed by Euclid. It is based on the following properties of GCD(m,n), the proof of which is left to the reader:

If , then according to the third property it can be reduced by the value n. If, then according to the second property, the arguments can be swapped and again come to the previously considered case. When, as a result of these transformations, the values of the arguments become equal, the solution will be found. Therefore, we can propose the following scheme:

while(m != n) ( if(m< n) swap(m,n); m = m - n; } return(m);

Here the swap procedure exchanges the values of the arguments.

If you think a little, it becomes clear that it is not at all necessary to exchange values - it is enough to change the argument with the maximum value at each step of the loop. As a result, we come to the diagram:

while(m != n) ( if(m > n) m = m - n; else n = n - m; ) return(m);

If you think a little more, you can improve this scheme by moving to a loop with an identically true condition:

while(true) ( if(m > n) m = m - n; else if (n > m) n = n - m; else return(m); )

The last diagram is good because it clearly shows the need to prove the completeness of this cycle. It is not difficult to prove the completeness of a loop using the concept of a loop variant. For this loop, an option can be an integer function - max(m,n) , which decreases at each step, always remaining positive.

The advantage of this version of the Euclid algorithm is that at each step an elementary and fast operation on integers is used - subtraction. If you allow the operation of calculating the remainder when dividing by an integer, then the number of loop steps can be significantly reduced. The following property is true:

This results in the following diagram:

int temp; if(n>m) temp = m; m = n; n = temp; //swap(m,n) while(m != n) ( temp = m; m = n; n = temp%n; )

If you think about it a little, it becomes clear that it is not at all necessary to perform a check before starting the cycle. This leads to a simpler GCD calculation scheme, usually used in practice:

int temp; while(m != n) ( temp = m; m = n; n = temp%n; )

To calculate LCM(m, n) you can use the following relation:

Is it possible to calculate LCM(m, n) without using multiplication and division operations? It turns out that you can simultaneously calculate LCM(m,n) while calculating GCD(m,n). Here is the corresponding diagram:

int x = v = m, y = u = n,; while(x != y) ( if(x > y)( x = x - y; v = v + u;) else (y = y - x; u = u + v;) ) GCD = (x + y )/2; LCM = (u+v)/2;

The proof that this scheme correctly calculates the GCD follows from the previously given properties of the GCD. The correctness of the LCM calculation is less obvious. To prove this, notice that the loop invariant is the following expression:

This relationship is satisfied after the variables are initialized before the loop begins execution. At the end of the cycle, when x and y become equal to GCD, the correctness of the scheme follows from the truth of the invariant. It is easy to verify that the loop body statements leave the statement true. The details of the proof are left to the readers.

The concept of GCD and LCM can be expanded by defining them for all integers. The following relations are valid:

Extended Euclidean Algorithm

Sometimes it is useful to represent gcd(m,n) as a linear combination of m and n:

In particular, the calculation of coefficients a and b is necessary in the RSA algorithm - public key encryption. I will give an algorithm diagram that allows you to calculate the triple - d, a, b - the greatest common divisor and expansion coefficients. The algorithm can be conveniently implemented as a recursive procedure

ExtendedEuclid(int m, int n, ref int d, ref int a, ref int b),

which, given input arguments m and n, calculates the values of arguments d, a, b. The non-recursive branch of this procedure corresponds to the case n = 0, returning as a result the values: d = m, a = 1, b = 0. The recursive branch calls

ExtendedEuclid(n, m % n, ref d, ref a, ref b)

and then modifies the resulting values of a and b as follows:

It is not difficult to construct a proof of the correctness of this algorithm. For the non-recursive branch, the correctness is obvious, and for the recursive branch it is easy to show that from the truth of the result returned by the recursive call, it follows that it is true for the input arguments after recalculating the values of a and b.

How does this procedure work? First, a recursive descent occurs until n becomes zero.

At this point, the value of d and the values of the parameters a and b will be calculated for the first time. After this, the rise will begin and parameters a and b will be recalculated.

Tasks

49. Given m and n are natural numbers. Calculate gcd(m, n). When making calculations, do not use multiplication and division operations.
50. Given m and n are natural numbers. Calculate LCM(m, n).
51. Given m and n are natural numbers. Calculate LCM(m, n). When making calculations, do not use multiplication and division operations.
52. Given m and n are integers. Calculate gcd(m, n). When making calculations, do not use multiplication and division operations.
53. Given m and n are integers. Calculate LCM(m, n). When making calculations, do not use multiplication and division operations.
54. Given m and n are integers. Calculate gcd(m, n). When making calculations, use the operation of taking the remainder of division by an integer.
55. Given m and n are integers. Calculate LCM(m, n). When making calculations, use the operation of taking the remainder of division by an integer.
56. Given m and n are integers. Compute a triple of numbers - (d, a, b) using the extended Euclidean algorithm.
57. Given m and n are natural numbers. Think of GCD(m, n) as a linear combination of m and n.
58. Given m and n are integers. Think of GCD(m, n) as a linear combination of m and n.
59. Given m and n are integers. Check whether the numbers m and n are coprime.

Prime numbers

Among the even numbers there is only one prime number - this is 2. There are as many prime odd numbers as you like. It is not difficult to prove that the number , where are consecutive prime numbers, is prime. So, if prime numbers have been constructed, then we can construct another prime number greater than . It follows that the set of prime numbers is unlimited. Example: the number N = 2*3*5*7 + 1 = 211 is a prime number.

Sieve of Eratosthenes

How to determine that N is a prime number? If the operation N % m is valid, giving the remainder when dividing N by number m, then the simplest algorithm is to check that the remainder is not equal to zero when dividing N by all numbers m less than N. An obvious improvement of this algorithm is to reduce the test range - it is enough to consider the numbers m in the range .

Back in the 3rd century BC. Greek mathematician Eratosthenes proposed an algorithm for finding prime numbers in a range that does not require division operations. This algorithm is called the “Sieve of Eratosthenes”. In the computer version, the idea of this algorithm can be described as follows. Let's build an array Numbers, the elements of which contain consecutive odd numbers, starting with 3. Initially, all numbers in this array are considered uncrossed out. Let's put the first uncrossed number from this array into the SimpleNumbers array - and this will be the first odd prime number (3). Then we will perform sifting, going through the Numbers array with a step equal to the found prime number, crossing out all the numbers that come across during this pass. On the first pass, the number 3 and all numbers that are multiples of 3 will be crossed out. On the next pass, the next prime number 5 will be entered into the table of prime numbers, and numbers that are multiples of 5 will be crossed out from the Numbers array. The process is repeated until all numbers in the array are crossed out Numbers. As a result, the SimpleNumbers array will contain a table of the first prime numbers less than N.

This algorithm is good for finding relatively small prime numbers. But if you need to find a prime number with twenty significant digits, then the computer memory will no longer be enough to store the corresponding arrays. Note that modern encryption algorithms use prime numbers containing several hundred digits.

Prime Density

We have shown that the number of prime numbers is unlimited. It is clear that there are fewer of them than odd numbers, but how much less? What is the density of prime numbers? Let be a function that returns the number of prime numbers less than n. It is not possible to specify this function precisely, but there is a good estimate for it. The following theorem is true:

The function asymptotically approaches its limit from above, so the estimate gives slightly underestimated values. This estimate can be used in the Sieve of Eratosthenes algorithm to select the dimension of the SimpleNumbers array when the dimension of the Numbers array is given, and, conversely, given the dimension of the table of primes, one can select the appropriate dimension for the Numbers array.

Tabular algorithm for determining the primeness of numbers

If you keep a table of prime numbers, SimpleNumbers, in which the largest prime number is M, then you can simply determine whether the number N less than is prime. If N is less than M, then it is enough to check whether the number N is in the SimpleNumbers table. If N is greater than M, then it is enough to check whether the number N is divisible by numbers from the SimpleNumbers table that do not exceed the value of vN. It is clear that if the number N has no prime factors less than vN, then the number N is prime.

Using a prime number table requires adequate computer memory and therefore limits the algorithm's capabilities, preventing it from being used to find large prime numbers.

Trivial algorithm

If N is an odd number, then you can check that it is prime based on the definition of primeness of a number. In this case, no memory is required to store tables of numbers - but, as always, winning in memory, we lose in time. Indeed, it is enough to check whether the number N is divisible by consecutive odd numbers in the range . If the number N has at least one factor, then it is composite, otherwise it is prime.

All of the algorithms discussed stop working effectively when numbers go beyond the computer's bit grid for representing numbers, so if there is a need to work with integers outside the System.Int64 range, then the task of determining the primality of such a number becomes far from simple. There are some recipes to determine that a number is composite. Let us at least recall the algorithms known from school times. If the last digit of a number is divisible by 2, then the number is divisible by 2. If the last two digits of the number are divisible by 4, then the number is divisible by 4. If the sum of the digits is divisible by 3 (by 9), then the number is divisible by 3 (by 9). If the last digit is 0 or 5, then the number is divisible by 5. Mathematicians have spent a lot of effort proving that a number is (or is not) a prime number. Now there are special techniques that allow you to prove that numbers of a certain type are prime. The most suitable candidates for prime are numbers of the form , where p is a prime number. For example, a number with more than 6000 digits has been proven to be prime, but it cannot be said which prime numbers are the nearest neighbors of that number.

Tasks

Projects

67. Construct a “Temperature” class that allows you to set temperature in different units of measurement. Build a Windows project that supports an interface for working with the class.
68. Construct a “Distance” class that allows you to use different systems of measures. Build a Windows project that supports an interface for working with the class.
69. Build a class "Prime numbers". Build a Windows project that supports an interface for working with the class.
70. Build a class “Number systems”. Build a Windows calculator that supports calculations in a given number system.
71. Construct a class "Rational numbers". Build a Windows calculator that supports calculations with these numbers.
72. Construct the class "Complex numbers". Build a Windows calculator that supports calculations with these numbers.