研fmis-ch2-theoryofdivisibility(編輯修改稿)
2025-03-26 18:50 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 orizations: 643=643 231?1=2147483647 644=22 723 231+1=3715827883 645=3543 232?1=351725765537 646=21 719 232+1=6416 700417 647=647 231+2=25 2 1341611321 18 The greatest mon divisor ? Definition . Let a and b be integers, not both zero. The largest divisor d such that d | a and d | b is called the greatest mon divisor (gcd: 最大公因子 ) of a and b. The greatest mon divisor of a and b is denoted by gcd(a, b). ? Example . The set of positive divisor of 111 and 333 are as follows: 1, 3, 37, 111, 1, 3, 9, 37, 111, 333, so gcd(111, 333)=111. But gcd(91, 111)=1, since 91 and 111 have no mon divisors other than 1. 19 The greatest mon divisor ? Theorem . Let a and b be integers, not both zero. Then there exists integers x and y such that d = gcd(a, b)=a x + b y. Proof. Consider the set of all linear binations au+bv, where u and v range over all integers. Clearly this set of integers {au+bv} includes positive, negative as well as 0. Choose x and y such that m=ax+by is the smallest positive integer in the set. Use the Divisor algorithm, to write a=mq+r, where 0?rm. Then r =a?mq=a?q(ax+by)=(1?qx)a+(?qy)b and hence r is also a linear bination of a and b. But rm, so it follows from the definition of m that r=0. Thus a=mq, that is m|a。 similarly, m|b. Therefore, m is a mon divisor of a and b. Since d=gcd(a, b), m?d. Since d | a and d | b, then d|m, d?m. Thus, we must have d=m. 20 Relatively prime ? Definition . 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 i?j, we have gcd(ai, aj)=1. ? Example . 91 and 111 are relatively prime, since gcd(91, 111)=1. 21 Relatively prime Proof. If a and b are relatively prime, so that gcd(a, b)=1, then Theorem 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 . Let a and b be integers, not 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. 22 Relatively prime Proof. By Theorem , 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 following that a|(acx+bcy). That is a|c. ? Theorem . If a | bc and gcd(a, b)=1, then a | c. 23 The least mon multiple (LCM) ? Definition If d is a multiple of a and also a multiple of b, then d is a mon multiple of a and b. The least mon multiple (lcm: 最小公倍數(shù) ) of two integers a and b, is the smallest mon multiple of a and b. The least mon multiple of a and b is denoted by lcm(a, b). ? Theorem . If 1 2 1 212121 2 1 21212 ... , 0 , ... , 0 ,t hen g c d( , ) ... , l c m ( , ) ... ,w her e m i n( , ), m a x( , ).kkkkaba a b bk i k irrrkssski i i i i ia p p p a b p p p ba b p p pa b p p pr
研究報(bào)告相關(guān)推薦
鄂ICP備17016276號(hào)-1