研FMIS-Ch2-TheoryofDivisibility.ppt

1、1,有限域与计算数论 Finite Field and Computational Number Theory,张文芳 信息科学与技术学院 ,西南交通大学 2012级硕/博研究生课程,2,Zhang Wenfang Email: School of Information Science similarly, m|b. Therefore, m is a common divisor of a and b. Since d=gcd(a, b), md. Since d | a and d | b, then d|m, dm. Thus, we must have d=m.,21,Relativ

2、ely prime,Definition 2.2.2. Two integers a and b are called relatively prime (互素) if gcd(a, b)=1. We say that integers a1, a2,ak are pairwise relatively prime if, whenever ij, we have gcd(ai, aj)=1.,Example 2.2.3. 91 and 111 are relatively prime, since gcd(91, 111)=1.,22,Relatively prime,Proof. If a

3、 and b are relatively prime, so that gcd(a, b)=1, then Theorem 2.2.2 guarantees the existence of integers x and y satisfying ax+by=1. As for the converse, suppose that ax+by=1 and that gcd(a, b)=d. Since d | a and d | b , d | (ax+by), that d | 1. Thus d =1.,Theorem 2.2.3. Let a and b be integers, no

4、t both zero, then a and b are relatively prime if and only if there exists integers x and y such that a x + b y = 1.,23,Relatively prime,Proof. By Theorem 2.2.2, we can write ax+by=1 for some choice of integers x and y. Multiplying this equation by c we get acx+bcy= c. Since a|ac and a|bc, it follow

5、ing that a|(acx+bcy). That is a|c.,Theorem 2.2.4. If a | bc and gcd(a, b)=1, then a | c.,24,The least common multiple (LCM),Definition 2.2.3 If d is a multiple of a and also a multiple of b, then d is a common multiple of a and b. The least common multiple (lcm: 最小公倍数) of two integers a and b, is th

6、e smallest common multiple of a and b. The least common multiple of a and b is denoted by lcm(a, b).,Theorem 2.2.5. If,25,The least common multiple (LCM),Theorem 2.2.6. Suppose a and b are positive integers, then,Example 2.2.3. Find gcd(240, 560) and lcm(240, 560).,26,Chapter 2 Theory of Divisibilit

7、y,2.1 Basic Concepts and Properties of Divisibility 2.2 Fundamental Theorem of Arithmetic 2.3 Mersenne Prime and Fermat Number 2.4 Euclids Algorithm 2.5 Continued Fraction,27,Mersenne prime,Definition 2.3.1. A number is called a Mersenne number if it is in the form of Mp=2p1, where p is a prime. If

8、a Mersenne number is a prime, then a it is called a Mersenne prime.,Example 2.3.1. The following numbers 221=3, 231=7, 251=31, 271=127, 2131=8191, 2171=131071. are all Mersenne numbers as well as Mersenne primes, but 2111 is only a Mersenne numbers, not a Mersenne primes, since 2111=2047=2389 is a c

9、omposite.,28,Mersenne prime,The known Mersenne primes Mp=2p1,29,Fermat number,Definition 2.3.2. Numbers of the form,Fermat was wrong Fermat in 1640 conjectured, in a letter to Mersenne, that all Fermat number were primes after he had verified it up to n=4; but Euler in 1732 found that the fifth Ferm

10、at number is not a prime, since F5=6416700417. To date, the Fermat numbers F5, F6, F11 have been completely factored.,called Fermat number. A Fermat number is called a prime Fermat number if it is prime. A Fermat number is called a composite Fermat number if it is composite.,30,Chapter 2 Theory of D

11、ivisibility,2.1 Basic Concepts and Properties of Divisibility 2.2 Fundamental Theorem of Arithmetic 2.3 Mersenne Prime and Fermat Number 2.4 Euclids Algorithm 2.5 Continued Fraction,31,2.4 Euclids Algorithm,Proof. Let X=gcd(a, b) and Y=gcd(b, r), it suffices to show X=Y. If integer c is a divisor of

12、 a and b, it follows from the equation a=bq+r and the divisibility properties that c is a divisor of r also. By the same argument, every common divisor of b and r is a divisor of a.,Theorem 2.4.1. Let a, b, q, r be integers with b 0 and 0 r b such that a = bq + r. Then gcd(a, b)=gcd(b, r).,32,2.4 Eu

13、clids Algorithm,Then (1) gcd(a, b)=rn.,Theorem 2.4.2. Let a and b be positive integers with a b. Apply the division algorithm repeatedly as follows:,33,2.4 Euclids Algorithm,(2) Values of x and y in gcd(a, b)=ax + by = rn can be obtained by writing each ri as a linear combination of a and b. rn = rn

14、2 rn1 qn1=ax + by.,34,2.4 Euclids Algorithm,Remark 2.4.1. Euclids algorithm is found in Book VII, Proposition 1 and 2 of his Elements(几何原本), but it probably wasnt his own invention. Scholars believe that the method was known up to 200 years earlier. However, it first appeared in Euclids Elements, an

15、d more importantly, it is first nontrivial algorithm that has survived to this day.,Remark 2.4.2. If Euclids algorithm is applied to two positive integers a and b with a b, then the number of divisions required to find gcd(a, b) is O(log b), a polynomial-time complexity. The big-O notation is used t

16、o denote the upper bound of a complexity function, i.e., f(n)=O (g(n) if there exists some constant c 0 such that f(n) cg(n).,35,2.4 Euclids Algorithm,Example 2.4.1. Use Euclids algorithm to find the gcd of 1281 and 243. Since 1281=2435+66, 243=663+45, 66=451+21, 45=212+3, 21=37+0, we have gcd(1281,

17、 243)=3, and 3=45212=45(66 451)2 =453662 =(243663)3662 =2433 6611 =2433 (12812435)11 =24358 128111 = 1281x +243y, where x = 11, y = 58.,36,Chapter 2 Theory of Divisibility,2.1 Basic Concepts and Properties of Divisibility 2.2 Fundamental Theorem of Arithmetic 2.3 Mersenne Prime and Fermat Number 2.4

18、 Euclids Algorithm 2.5 Continued Fraction,37,2.5 Continued Fraction (连分数),Definition 2.5.1. Let a and b be positive integers and let Euclids algorithm run as,a = b q0 + r1, b = r1 q1 + r2, r1 = r2 q2 + r3, r2 = r3 q3 + r4, rn2 = rn1 qn1 + rn, rn1 = rn qn +0.,where q0, q1, , qn1, qn are called the partial quotients of the continued fraction.,38,2.5 Continued Fraction,39,Exercise 2,Exercise 2.1 Let a , b and c be integers. Show that (1) 1 | 0, a | a, a | 0. (2) If a | b and b | a, then a = b. (3) If a | b and b | c, then for all inte