Chapter 20      Elementary Number Theory

This chapter briefly introduces the basic knowledge of elementary number theory . It is divided into six sections . The first five sections discuss the properties of integers and the method of division , continuous fractions and Fibonacci sequences , congruence and Sun Tzu's theorem , and introduce several important The number-theoretic functions and Mobius transforms of algebraic numbers are listed , and the discrimination methods of several types of irreducible polynomials are listed . The last section gives a brief introduction to the basic concepts and properties of algebraic numbers .

§ 1 Integer

[ Integer part and fractional part ]   Let a be a real number , the largest integer not exceeding a is called the integer part of α , denoted as . And called the fractional part of a .  For example , , etc.   The integer part has the following relation :   , n is a natural number , n is a natural number  or Note that the meaning of "rounding operation" in computer programs is different from the meaning of "integer part" here : it was consistent at the time ; it was inconsistent at the time , for example , but after rounding on the computer .     [ Divisibility ]   If there is an integer c , such that the integers a and b are suitable for Then b is said to be divisible by a , denoted as . In this case, a is called a multiple of b , and b is called a factor ( or submultiple ) of a. If b is not divisible by a , it is recorded as b a . Divisibility has the following properties ( the following equations ): 1 ° If , , then ;   2 ° If , then ;  3 ° If ​​, , then for any integer m,n we have   4 ° If b is a true factor ( ie ) of a, then  [ Prime numbers and Eratos sieve method ] An integer greater than 1 that has exactly 1 and itself two natural numbers as its factors is called a prime number , denoted as . Except for 2 , which is an even prime number , the other prime numbers are odd numbers . Prime numbers have the properties :

There are infinitely many 1 ° prime numbers . If the number of prime numbers not exceeding the natural number n is denoted as p (n) , then at that time , there is * , and further there are   2 ° Let p be a prime number , if , then or .   The power of the square containing the prime number p in 3 ° is equal to  4 ° If it is a positive integer , it cannot be divisible by all prime numbers not exceeding , then n must be a prime number . This method of judging whether a natural number is a prime number is called the Eratosian sieve method . This method can establish a prime number table .  [ Unique Decomposition Theorem ] All natural numbers   greater than 1 can be uniquely decomposed into the product of prime powers . If , is a natural number , then n can be uniquely represented as   ( for natural numbers ) ( for prime numbers )

This is called the standard decomposition of n . The number s of different prime factors in n does not exceed . Obviously , any natural number n can be expressed as ( k,m are natural numbers or zero )

This expression is unique .

[ Mason number ]   integer ( p is a prime number )

Those who are prime numbers are called Meissen numbers . So far only 27 have been found , namely Whether there are infinite Meissen numbers has not yet been proved .

[ Fermat number ]   integer ( n is a natural number )

It is called the Fermat number . So far, only 5 Fermat numbers have been found to be prime , namely None of the following 46 Fermat numbers are prime : [ Reversing and dividing method * ] Each integer a can be uniquely represented by a positive integer b as In the formula, q is called the incomplete quotient obtained by dividing a by b , and r is called the remainder obtained by dividing a by b . The rolling division method refers to the following finite series of equations : ( 1 )

Example 1 set a = 525, b = 231, according to the formula (1) , the following formulas and formulas can be listed :

arithmetic grass _    [ The greatest common factor and the least common multiple ]   Let a and b be integers . A positive integer that can divide both a and b is called the common factor of a and b , and the largest one is called the greatest common factor of a and b * , denoted as _  Especially at that time , it is said that a and b are mutually prime . Let a and b be positive integers . A positive integer that is divisible by both a and b is called the common multiple of a and b, and the smallest one is called the least common multiple of a and b * , which is written as  Let n positive integers , and define their greatest common factor by induction as  Its least common multiple is The greatest common factor and the least common multiple have the following properties :

1 ° There are integers x, y, such that x , y can be specifically obtained by the rolling division method . It is also obtained by a series of equations of the rolling division method , namely    Example 2 obtains (525,231)=21 from Example 1. Because the formula from Example 1 has So we get x = 4, y = - 9 .

2 ° must exist for any two integers x, y . 3 ° If , , then .   4 ° if then  If , then  5 ° If a and b are two positive integers , they are their prime factors , and the standard decomposition formulas are   but 6 ° If 7 ° is a co-prime positive integer , that is , then   * In number theory, the natural logarithm is usuallywritten as.

* Qin Jiushao, an ancient Chinese mathematician(also known as Euclid's algorithm)in "Nine Chapters of the Shushu"1247

* In foreign books and periodicals,the greatest common divisor of a and b is often written as gcd( a , b ),the least common multiple of a and b is often written as lcm ( a , b ).