Elementary Number Theory modify content

Brief Introduction

This book divides the main content, congruence, diophantine equation, one dollar more than the same equations, quadratic residues, primitive roots and indicators, and even scores, algebraic number and beyond the number of number theoretic function and composite numbers break down, and several issues related to prime numbers in the Chapter II also introduced.

This book is intended as a science and engineering universities and colleges of school textbooks or teaching reference books, part of the content can be used as post-high school elective curriculum reform in paragraph or secondary school mathematics teachers teaching reference books.

Introduction

Number theory is the study of mathematics, the number of properties, in particular the nature of the branches of an integer. Number theory this ancient branch of mathematics, far away in Ancient Greece Euclids "Geometry" in, you can find information on number theorys exposition. Diophantus written in the year before and after 250 years of "arithmetic," a book , deals with, such as seeking x2- 30y2=1this type of integer solutions of the equations number theory, including many of the problems, which discusses the entire order to determine the coefficient of the agenda of the integer solutions of the problem. in ancient China a number of mathematical works, such as " Nine Chapters on Arithmetic "," Sun Tzu, "also has a lot about the content of number theory.

Number theory has always been active in is the emergence of new problems continue to get new results of the branch of mathematics, history, many well-known mathematicians such as Gauss, Euler, Fermat, Lagrange, etc. have been made in number theory important contributions. In modern times, our mathematician Hua, Yin-lin, Wang Yuan, Pan-dong, Pan Cheng Biao, later were pottery, Ding Xiaqi, Chens, Ke Zhao, Sun Qideng problems in number theory have made outstanding achievements. Number Theory In the application of theory and practice, but also with the development of science and technology, more and more widely, in the calculation method, algebraic coding, portfolio theory, approximate analysis, both come in handy,

In particular, the development of computer science and formed a branch of the current very active - computational number theory.

Number theory, according to the different nature of their research, is divided into elementary number theory, analytic number theory, algebraic number theory and geometry number theory. The very nature of the use of a full and logical reasoning methods to prove the thesis branches of number theory called elementary number theory; to a number theory problem is transformed into analyze problems, using mathematical analysis, complex variable function, such as tools to study and demonstration of a branch of number theory proposition called Analytic number theory; the use of algebraic integers of the nature of the method of algebraic number theory as a branch of algebraic number theory; the use of geometric methods to study the problem of some number theory of number theory Geometric number theory branch claimed.

Elementary number theory the meaning of the proposition is often very clear and understandable, but it is the method used to solve the problem, techniques for learning math has its own special training value, therefore, workers have been more and more attention to mathematics teaching. In China, due to primary number theory mathematics in secondary schools did not occupy its rightful place, it can not but be a regret, but the problem itself and the subject of number theory is difficult to do relevant. Curriculum Reform High School Section has made "Elementary Number Theory" included in the elective content, broken like this Door ancient and early integration into a dynamic discipline among secondary school mathematics.

This book on "Elementary Number Theory," the main elements of a dollar more than the same equation and Quadratic Congruence Equation done a great improvement to alleviate these two chapters the subject is difficult to act. Due to the limitations of the level and field of vision, but also has Teaching is not subject to first-line test of its shortcomings and wrong with the inevitable, I would urge readers to hearing.

Song Kaifu

April 2007

Directory

In addition to the first chapter of integers that can be …………………………………………(1)

§ 1.1 Divisibility …………………………………………………………………………(1)

§ 1.2 Prime Number • Fundamental theorem of arithmetic ………………………………(4)

§ 1.3 common denominator least common multiple ………………………………………(7)

§ 1.4 Gaussian function [x] ………………………………………………………………(15)

Chapter II prime problem ………………………………………………………………………(20)

§ 2.1 the distribution of prime numbers………………………………………………… (20)

§ 2.2 twin primes distribution (27)

§2.3 Sansheng distribution of prime numbers and the n²－n＋p prime number distribution…(30)

§ 2.4 even prime number pairs………………………………………………………… (36)

Chapter III of the indeterminate equation ……………………………………………………(42)

§ 3.1 Diophantine Equation …………………………………………………………… (42)

§ 3.2 supplier of high Diophantine Equations …………………………………………(47)

§ 3.3 Fermats introduction to the question …………………………………………… (51)

Chapter IV congruence theory …………………………………………………………………(54)

§ 4.1 The concept of congruence and basic nature……………………………………… (54)

§ 4.2 Department of the remaining classes and complete the remaining ………………(58)

§ 4.3 simplify the remainder of the Department and the Euler function ………………(63)

§ 4.4 Eulers theorem • Fermats Theorem and Its Applications……………………… (70)

Chapter unary congruence equation…………………………………………………………… (74)

§ 5.1 a congruence equation…………………………………………………………… (74)

§ 5.2 of the higher-quality digital-analog congruence equation………………………… (81)

§ 5.3 kg of high order digital-analog congruence equation……………………………… (89)

§ 5.4 congruence equation the necessary and sufficient solvability conditions …(94)

Chapter VI squared residual and secondary congruence equation ……………………………(98)

§ 6.1 Basic Properties…………………………………………………………………… (98)

§ 6.2 Legendre symbol………………………………………………………………… (102)

§ 6.3 Jacobi symbol…………………………………………………………………… (111)

§ 6.4 odd prime model of secondary congruence equation…………………………… (115)

§ 6.5 together with more than twice the number of modules equation …………………(119)

§ 6.6 the square of two numbers, and………………………………………………… (126)

Chapter VII of the original roots and Indicators…………………………………………… (133)

§ 7.1 Order number ……………………………………………………………………(133)

§ 7.2 of the original root existence of necessary and sufficient conditions ……………(137)

§ 7.3 to simplify the construction of the remaining line……………………………… (143)

§ 7.4 Indicators………………………………………………………………………… (147)

Chapter VIII fraction…………………………………………………………………… ……(152)

§ 8.1 scores and circulator of each of………………………………………………… (152)

§ 8.2 fraction……………………………………………………………………………(155)

§ 8.3 points and the asymptotic properties…………………………………………… (159)

§ 8.4 fraction of the value……………………………………………………………… (164)

§ 8.5 Application of continued fraction………………………………………………… (170)

Chapter IX of algebraic number and surpass the number of………………………………… (182)

§ 9.1 Quadratic number………………………………………………………………… (182)

§ 9.2 Decomposition of quadratic algebraic integers …………………………………(189)

§ 9.3 n times the number of algebraic number and Beyond…………………………… (195)

§ 9.4 e • π transcendence……………………………………………………………… (198)

Chapter number-theoretic function • composite number decomposition…………………… (208)

§ 10.1 Multiplicative function………………………………………………………… (208)

§ 10.2 Characteristic Functions………………………………………………………… (214)

§ 10.3 divisor problems with circle grid points in the introduction…………………… (225)

§ 10.4 Discrimination and co-prime factorization………………………………………（232）

"Elementary Number Theory" update instructions

Chapter divisibility theory

1, divides a problem and can not be divisible by two aspects of narrative together to make the structure more compact, but also to facilitate comparison and contrast. Similarly, the divisor and common multiple, greatest common divisor, least common multiple narrative together is also true book many will be discussed together some related properties is also based on this point.

2, the fundamental theorem of arithmetic proof of reductio ad absurdum by the inductive method to simplify the certification process.

3, "If a, b ∈ Z, and a²+b² ≠ 0, then there exists x, y ∈ Z, making ax + by = (a, b) set up" to Syria and reasonable style. Of the original material is the first to use inductive method prove that "if a, b ∈ Z +, then the Q_ka-P_kb=（-1）^k-1r_k,k, k = 1,2, ..., n". and then deduce the theorem directly. And this theorem using the same theory also brings more than easy to prove, so this theorem in the first chapter with the Syrian-style state a reason, to give proof of the third chapter.

4, the new notation equation with variable demand a, b of the common denominator. This notation is mainly reflected out of two points, one way unique, is easy to derive the second mission to ax + by = (a, b) establishment of x, y.

5, will be the largest integer that standard decomposition of the Convention and the least common multiple in front of the book is different.

Chapter II Primes

6, this chapter use two main tactics ——-"I get Sum" and "overall relative" to address some long-standing issues. One approach to solve this by taking more than the sum of: ① the distribution of prime numbers; ② arithmetic series distribution; ③ the distribution of twin primes; ④n²+1 the distribution of prime numbers; ⑤ Sansei distribution of prime numbers; ⑥n²-n+Pi distribution of prime numbers; with the overall relative resolved; ⑦ even number of prime numbers right. These issues are by a long-term food for thought, pondering results, coupled with some restrictions on the chart by the layout, there is no book in the present, which also brings some difficulties in reading comprehension, so on these issues,

Readers will take some time to slowly comprehend. To avoid possible disputes, it will be in this chapter before the addition of "interest to read." (Publication of Final Appeal to remove)

Chapter III of the congruence theory

7, in § 3.2, by using the theory of congruence to § 1.3 of the proof of theorem 3.

8, the new "On the complete model m (Full or simplified), Department A, a decomposition of the remaining" definition. How the remainder of the Department of A (security or simplification) expressed as a₁A₁+ a₂A₂ in the form of the remainder of the research department to discuss one aspect of the need to define such issues.

9, new theorem 3, "if m ∈ S, A complete on the remaining system module m, then there is no decomposition of A-type."

10, added Theorem 5, is the (m, n) = 1 extended to (m, n) = d＞1 range.

11, in § 3.3, the new inference 5.1, "set m, n ∈ Z +, (m, n) = d, then (m, n) φ [m, n] = φ (m) φ (n). "This is the (m, n) = 1 extended to (m, n) = d＞1 range.

12, add "break" in the definition and Theorem 6, its meaning and the same as in § 3.2, there is not tired out.

Chapter IV indeterminate equation

13, in § 4.1, the introduction of an indeterminate equation a different solution, this method can be very easy to find ax + by = c in a solution （x₀，y₀）.

14, in § 4.2, the new "If x, y, z ∈ Z +, when x＞ 2, the Diophantine Equation x²+y²=z² group of at least one solution."

15, summed up by a number of written Pythagorean triple, the number with the number written about the number of relevant conclusions. The two first theoretically proved that an integer greater than 2 there Pythagorean triple, the second was to remind out from this how to write Pythagorean triple the number of questions. such as the demand x = 40 when all the Pythagorean triple, some people believe can only write three groups, and the writing out of 7 groups.

Chapter V unary congruence equation

16, introduction of the "countdown to number theory" definition. Because of the definition in the fifth chapter, Chapter VI, and Chapter X are involved, so the introduction of the definition.

17, in § 5.1 to add Theorem 4 and Theorem 5, its meaning is in the solution of a group with similar problems, do not rigidly stick to mold 22 are coprime, precisely because of this, with a new method of theorem revealed significantly lower understanding of difficult question.

18, in § 5.2 added theorem 3, the theorem first determine the necessary and sufficient conditions for the solvability of equations, and second, can not the same equation and the equation number of solutions into the same number of times, it is this type of problem can be reduced an important part.

19, in § 5.3 added theorem 1, the theorem proved in § 5.1 with the conclusions of Theorem 5 to give evidence.

20, the contents of a new § 5.4. In theory, divisibility, congruence of the concepts and the nature can not be difficult to prove in a similar way Zhengshi established, but to make use of a specific task is not easy, if not in front of the new theorem, where there is difficult to make specific use, of course, the use of the content is also very rich.

Chapter VI squared residual and secondary congruences

21, using new theorem (§ 5.3 of Theorem 3), the conclusion to the Eulers Criterion (i) another proof method.

22, the new odd prime number mode and 2k-mode "base equation" definition.

23, in § 6.4, the new theorem 1 and theorem 2, using the base equation to solutions of odd-mode quadratic congruence equation, to abandon the old methods, new methods First, a significant reduction in the difficulty of understanding and calculation of the second is the whole process can be programmed to run on the computer.

24, in § 6.5, the new theorem 1 and theorem 3, the same equation to solve this problem using the base combined digital-analog quadratic congruence equation in § 6.4 of its meaning and the same.

25, in § 6.6, the new how to make a few tables and the square of two numbers a general way.

Chapter VII of the original roots and indicators

26, find m of the original root of the problem is essentially seeking prime primitive root of the problem P, when P is larger, the demand of the original P, the root method is very troublesome, first of all φ (p) is decomposed into the product of prime numbers is not easy to matter, followed by the simplification in the P surplus lines, seeking to satisfy (2) a_i is more difficult, but more than this, we still do not know if there is a general easy way to exist in the § 7.2, replace the original root of the number of P return to the equation f (a) ≡ 0 (mod p) in, if the sub-r (a) = t, then P has t one of the original root.

27, in Chapter VIII of the continued fraction, IX and surpass the number of algebraic number, there is no new theorems and methods, but in his discussion of the order made an appropriate adjustment.

Chapter number-theoretic function, co-factorization

28, the new "in § 10.3 Discrimination and co-prime factorization", given the number of discrimination and co-prime factorization of a polynomial algorithm, if there is decomposition of a number of factors x_i, then a is a composite number, otherwise a is a prime number, to determine and decomposition simultaneously.

29, the sections were made to refer to answer or Exercise tips.

30, the words "Elementary Number Theory" means signed by the "compiled" to "ed."

As I level by the vision and the limitations of the book please put my mistakes and shortcomings hesitate Zhi Jiao.

"Elementary Number Theory," the revised draft

Chapters	Modifications
§1.1	1 ° will be divisible and can not be divisible by (with I division) The description of the two definitions together. 2 ° the introduction of integers, Z, positive integers, Z+ symbol.
§1.2	1 ° with the S that set of prime numbers, using S奇 said the set of odd prime number. 2 ° to Theorem 3 (Fundamental theorem of arithmetic) to a reductio ad absurdum proof.
§1.3	1 ° the "greatest common factor and the Euclidean algorithm" and "further the nature and the least common multiple divides" into the "greatest common denominator • least common multiple." 2 ° will be the greatest common divisor and least common multiple the two definitions together narrative. 3 ° will use the euclidean division seeking the greatest common divisor of the division magic formula to rewrite the formula for the short division. 4 ° the theorem "if a, b ∈ Z, and not are all 0, then there exists two integers x, y, making ax + by = (a, b)", into Syria and reasonable style. 5 ° additional cases of 2, with uncertain demand equation notation greatest common divisor of two numbers. 6 ° Add Theorem "set a, b, m ∈ Z, there is a | m, b | m [a, b] | m".
§1.4	1 ° with the R+ indicated positive real number set. 2 ° This section focuses on the simple nature of the Gaussian function.
§2.1	New prime number distribution, 1 ° come within the scope of the prime number P the number of Sn=. 2 ° P within the scope of arithmetic progression an + r in (a, r) = 1 the distribution of prime numbers=..
§2.2	1 ° obtained Pwithin the scope of twin primes Ln=, in the range of natural numbers without the largest twin primes.
§2.3	1 ° Sansheng distribution of prime numbers, and n2-n+p prime number distribution obtained within the scope of Sansei Pthe number of prime numbers. En=, in the range of natural numbers not the largest twin primes. 2 ° obtained Pwithin the scope of n2-n+p prime number distribution of the number of Qn=. In the context of natural numbers, when N = 2,3, then there is countless number of prime numbers pi, when 0 ≤ n ≤ N, when, n2-n+piJie Wei prime number; when N = pi-1, the only natural number, there are some special N, when 0 ≤ n ≤ N, when, n2-n + pi Jie Wei prime, and this N is not too much.
§2.4	1 ° even prime number pairs come within the scope of an even M the number of pairs of prime numbers Cn=（Sn′－Sn′/2）2，, where Sn′=，Sn′/2=. Obtained within the framework of the natural numbers, even the larger the number of pairs of prime even more so that any one can form an even larger than for the sum of two primes.
§3.1	1°introducing the different aspects of the indeterminate equation solution.

Modifications

New theorem, if x, y, z ∈Z+ ,when x＞2, the Diophantine Equation x2+y2=z2, there exists at least one group of solution. That is, when x = 2m +1, there are x = 2m +1, y = 2 m2+2 m, z = 2 m2 +2 m +1 satisfy the equation; when x = 2m, there are x = 2m, y = 2 m2-1, z = m2 +1 satisfy the equation.

New theorem, if a ≡ b (modm), a ≡ b (modm), then a ≡ b (mod [m, n]).

1 ° additional lemma, let m, n ∈Z+, (m, n) ＞ d, then (, n) = 1 and (m, ) = 1 in at least one type was established. 2 ° Add Theorem 4 (or § 4.3 of Theorem 6), let m, n ∈Z+, (m, n) = d, (m, ) = 1, A, B respectively, on the module m, Complete (simplified) residual system, then the A + mB is about the module [m, n] complete (simplified) left the Department.

1°additional corollary 5.1, let m, n ∈Z+, (m, n) = d, then （(m,n)）（[m,n]）=（m）(n).

1 ° additional number theory countdown concept. 2 ° new theorem 1, if a ∈ Z, m ∈Z+, and (a, m) = 1, then a few on the countdown to a★. 3 ° additional cases of 1, Example 2, Example 3, an increase over time with solutions of equations of examples. 4 ° New Theorem 4, with more than equations the necessary and sufficient solvability condition a + mt ≡ b (mod n), t ∈ Z, if this condition is, then the equations is x ≡ a + mt (mod [m, n]). 5 ° Add Theorem 5, with the solution of equations the solution is x≡b1+m1t1+[m1,m2] t2+…+[ m1，m2…，mn -1] tn-1(mod[m1，m2…，mn]). Ti which satisfy the b1+m1t1+[m1,m2] t2+…+[ m1，m2…，mi] ti≡bi+1(modmi+1).

1 ° New Theorem 3, n times congruence equation f (x) ≡ 0 (modp) is a sufficient condition for the solvability of f (x) exists r (x), r (x) for the module P is f (x) The result type, and to meet the xp-x = g (x) f (x) + r (x) ≡ 0 (modp), if r (x) the number of m, then f (x) ≡ o (modp) has m-not the same solution. This theorem can not the same equation and the equation number of solutions into an equal number of times. 2 ° change and new Example, increasing congruence equation solution of high-order training.

1 ° Add Theorem 1, derived f (x) ≡ 0 (modpk) the necessary and sufficient solvability conditions are f′(x)piti+f(xi)≡0modpi+1),i=1,2,…,k-1.

1 ° Add, I equations with the necessary and sufficient conditions for solvability, I will work with the equations in the f, r1，r2 and mode m, n integers by the extension to the exhibition-style range.

1°given Euler Criterion (I) Another Proof.

1°New definition and theorem 1, theorem 2, using the benchmark solutions of quadratic equations for congruences.

1 ° new definition and theorem 1, theorem 3. 2 ° to the module is power of prime numbers congruent equation x2≡a(modpk),pトa; Suites a discussion of the solution was appropriate modifications. 3 ° to x2≡a(mod 2α),α＞1，（2，a）=1 the necessary conditions for solvability instead of necessary and sufficient conditions, namely, the adequacy of proof of the theorem.

1 ° additional ways to a number of the square of the number of tables for two and a general way.

1 °Will be the root of the number of p original return to the equation r (a) ≡ 0 (mod p), where an r (a) the number of t, then P has t one of the original root.

1 ° the "Mody number" replaced by "unit number".

1 ° the "characteristic function" into introduce the number-theoretic function.

1 ° Added "Discrimination and co-prime factorization", given the number of prime discriminant and co-determine the polynomial algorithm, if there is decomposition of a number of factors xi, then a is a composite number, otherwise a is a prime number, so that discrimination and decomposition simultaneously.