Luận văn Thạc sĩ Khoa học: Bất phương trình Diophante tuyến tính

Chia sẻ: Na Na | Ngày: | Loại File: PDF | Số trang:66

Thêm vào BST

Báo xấu

63
lượt xem 12
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Trong luận văn này tác giả không tham vọng bao quát hết các vấn đề bất phương trình Diophante tuyến tính mà chủ yếu đi sâu nghiên cứu bất phương trình dạng này với hai biến, ba biến hoặc bốn biến. Hi vọng đây sẽ là một tài liệu bổ ích cho các thầy cô giáo và các em học sinh trong quá trình ôn luyện thi học sinh giỏi.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận văn Thạc sĩ Khoa học: Bất phương trình Diophante tuyến tính

I HÅC QUÈC GIA H NËI TR×ÍNG I HÅC KHOA HÅC TÜ NHIN TRN TR×ÍNG SINH BT PH×ÌNG TRNH DIOPHANTE TUYN TNH Chuy¶n ng nh: PH×ÌNG PHP TON SÌ CP M¢ sè: 60.46.01.13 LUN VN THC Sß KHOA HÅC NG×ÍI H×ÎNG DN KHOA HÅC GS.TSKH NGUYN VN MU H NËI - 2015
Möc löc Mð ¦u 2 1 Mët sè ki¸n thùc chu©n bà 4 1.1 ×îc sè chung lîn nh§t. Thuªt to¡n Euclid . . . . . . . . . . . . . . . . 4 1.2 Li¶n ph¥n sè . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.3 Ph÷ìng tr¼nh Diophante tuy¸n t½nh . . . . . . . . . . . . . . . . . . . . 15 1.3.1 T¼m nghi»m ri¶ng düa v o gi£n ph¥n . . . . . . . . . . . . . . . 18 1.3.2 T¼m nghi»m ri¶ng düa v o thuªt to¡n Euclid . . . . . . . . . . . 19 1.4 Nghi»m nguy¶n d÷ìng cõa ph÷ìng tr¼nh Diophante tuy¸n t½nh . . . . . 24 2 B§t ph÷ìng tr¼nh Diophante tuy¸n t½nh 26 2.1 B§t ph÷ìng tr¼nh Diophante tuy¸n t½nh . . . . . . . . . . . . . . . . . . 26 2.2 B§t ph÷ìng tr¼nh Diophante tuy¸n t½nh "bà ch°n" . . . . . . . . . . . . 30 2.3 Nghi»m nguy¶n d÷ìng cõa b§t ph÷ìng tr¼nh Diophante tuy¸n t½nh . . . 34 2.3.1 Mët sè v½ dö li¶n quan . . . . . . . . . . . . . . . . . . . . . . . 35 2.3.2 B§t ph÷ìng tr¼nh Diophante d¤ng li¶n ph¥n sè . . . . . . . . . . 41 3 Mët sè b i to¡n li¶n quan 43 3.1 Nghi»m nguy¶n cõa ph÷ìng tr¼nh, h» ph÷ìng tr¼nh, b§t ph÷ìng tr¼nh, h» b§t ph÷ìng tr¼nh l÷ñng gi¡c . . . . . . . . . . . . . . . . . . . . . . 43 3.2 Ph÷ìng tr¼nh, h» ph÷ìng tr¼nh, b§t ph÷ìng tr¼nh, h» b§t ph÷ìng tr¼nh l÷ñng gi¡c câ i·u ki»n . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 3.3 X¡c ành ph¥n thùc ch½nh quy thäa m¢n i·u ki»n cho tr÷îc . . . . . . 56 K¸t luªn 64 T i li»u tham kh£o 65 1
Mð ¦u Ph÷ìng tr¼nh nghi»m nguy¶n hay cán gåi l ph÷ìng tr¼nh Diophante l mët trong nhúng d¤ng to¡n l¥u íi nh§t cõa To¡n håc. Thæng qua vi»c gi£i ph÷ìng tr¼nh Diophante, c¡c nh to¡n håc ¢ t¼m ra ÷ñc nhúng t½nh ch§t s¥u sc cõa sè nguy¶n, sè húu t¿, sè ¤i sè. Gi£i ph÷ìng tr¼nh Diophante ¢ ÷a ¸n sü ra íi cõa li¶n ph¥n sè, lþ thuy¸t ÷íng cong elliptic, lþ thuy¸t x§p x¿ Diophant, th°ng d÷ b¼nh ph÷ìng, sè håc modular,. . . B§t ph÷ìng tr¼nh Diophante tuy¸n t½nh thüc ch§t l ph÷ìng tr¼nh Dio- phante tuy¸n t½nh câ chùa tham sè. Câ thº nâi ¥y l mët d¤ng to¡n kh¡ mîi m´ v ch÷a phê bi¸n trong c¡c ký thi håc sinh giäi bªc phê thæng. Trong luªn v«n n y, t¡c gi£ khæng câ tham vång bao qu¡t h¸t c¡c v§n · v· b§t ph÷ìng tr¼nh Diophante tuy¸n t½nh m chõ y¸u i s¥u nghi¶n cùu b§t ph÷ìng tr¼nh d¤ng n y vîi hai bi¸n, ba bi¸n ho°c bèn bi¸n. Hi vång ¥y s³ l mët t i li»u bê ½ch cho c¡c th¦y cæ gi¡o v c¡c em håc sinh trong qu¡ tr¼nh æn luy»n thi håc sinh giäi. Luªn v«n ÷ñc chia l m 3 ch÷ìng: Ch÷ìng 1. Mët sè ki¸n thùc chu©n bà Ch÷ìng 2. B§t ph÷ìng tr¼nh Diophante tuy¸n t½nh Ch÷ìng 3. Mët sè b i to¡n li¶n quan. Nh¥n ¥y, t¡c gi£ xin b y tä sü k½nh trång v láng bi¸t ìn s¥u sc tîi GS.TSKH Nguy¹n V«n Mªu. Th¦y ¢ d nh nhi·u thíi gian h÷îng d¨n công nh÷ gi£i ¡p c¡c thc mc cõa håc trá trong suèt qu¡ tr¼nh håc tªp, nghi¶n cùu v gióp ï t¡c gi£ ho n th nh luªn v«n n y. T¡c gi£ công xin gûi líi c£m ìn ch¥n th nh nh§t tîi Ban gi¡m hi»u, Pháng o t¤o Sau ¤i håc, Khoa To¡n - Cì - Tin håc, c¡c th¦y cæ gi¡o ¢ t¤o i·u ki»n thuªn lñi º t¡c gi£ câ thº ho n th nh nhi»m vö cõa m¼nh. 2
T¡c gi£ xin c£m ìn gia ¼nh, b¤n b± ¢ luæn quan t¥m, ëng vi¶n, cê vô v t¤o i·u ki»n tèt nh§t cho t¡c gi£ trong suèt thíi gian m t¡c gi£ håc tªp t¤i tr÷íng ¤i håc Khoa håc Tü nhi¶n - ¤i håc Quèc gia H Nëi. M°c dò ¢ câ nhi·u cè gng nh÷ng do thíi gian v tr¼nh ë cán nhi·u h¤n ch¸ n¶n luªn v«n khâ tr¡nh khäi nhúng thi¸u sât. V¼ vªy t¡c gi£ r§t mong nhªn ÷ñc sü gâp þ cõa c¡c th¦y gi¡o, cæ gi¡o công nh÷ c¡c b¤n çng nghi»p º b£n luªn v«n ÷ñc ho n thi»n hìn. T¡c gi£ xin ch¥n th nh c£m ìn! H Nëi, th¡ng 09 n«m 2015 Håc vi¶n thüc hi»n Tr¦n Tr÷íng Sinh 3
Ch÷ìng 1 Mët sè ki¸n thùc chu©n bà 1.1 ×îc sè chung lîn nh§t. Thuªt to¡n Euclid ành ngh¾a 1.1 (xem [1]). Sè nguy¶n c ÷ñc gåi l mët ÷îc sè chung cõa hai sè nguy¶n a v b (khæng çng thíi b¬ng khæng) n¸u c chia h¸t a v c chia h¸t b. ành ngh¾a 1.2 (xem [1]). Mët ÷îc sè chung d cõa hai sè nguy¶n a v b (khæng çng thíi b¬ng khæng) ÷ñc gåi l ÷îc sè chung lîn nh§t cõa a v b n¸u måi ÷îc sè chung c cõa a v b ·u l ÷îc cõa d. Chó þ 1.1. N¸u d l ÷îc sè chung lîn nh§t cõa a v b th¼ −d công l ÷îc sè chung lîn nh§t cõa a v b. Vªy ta quy ÷îc r¬ng ÷îc sè chung lîn nh§t cõa a v b l sè nguy¶n d÷ìng. ×îc sè chung lîn nh§t cõa hai sè a v b ÷ñc kþ hi»u l (a,b) hay gcd(a,b) (greatest common divisor). Nh÷ vªy d = (a,b) hay d = gcd(a,b). V½ dö 1.1. (25,30) = 5, (25,-72) = 1. ành ngh¾a 1.3 (xem [1]). Mët sè nguy¶n c ÷ñc gåi l mët ÷îc sè chung cõa n sè nguy¶n a1 , a2 , a3 , . . . , an (khæng çng thíi b¬ng khæng) n¸u c l ÷îc cõa méi sè â. ành ngh¾a 1.4 (xem [1]). Mët ÷îc sè chung d cõa n sè nguy¶n a1, a2, a3, . . . , an (khæng çng thíi b¬ng khæng) ÷ñc gåi l ÷îc sè chung lîn nh§t cõa a1 , a2 , a3 , . . . , an n¸u måi ÷îc sè chung c cõa a1 , a2 , a3 , . . . , an ·u l ÷îc cõa d. T÷ìng tü, ta công quy ÷îc r¬ng ÷îc sè chung lîn nh§t cõa n sè nguy¶n a1 , a2 , a3 , . . . , an l sè nguy¶n d÷ìng. ×îc sè chung lîn nh§t cõa a1 , a2 , a3 , . . . , an kþ hi»u l (a1 , a2 , a3 , . . . , an ) hay gcd(a1 , a2 , a3 , . . . , an ). Nh÷ vªy d = (a1 , a2 , a3 , . . . , an ) hay d = gcd(a1 , a2 , a3 , . . . , an ). 4
ành l½ 1.1. (v· sü tçn t¤i ÷îc sè chung lîn nh§t cõa nhi·u sè, xem [1]) Cho c¡c sè nguy¶n a1 , a2 , a3 , . . . , an khæng çng thíi b¬ng khæng. Khi â tçn t¤i ÷îc sè chung lîn nh§t cõa a1 , a2 , a3 , . . . , an . T½nh ch§t 1.1 (xem [1]). Cho a, b, q, r l c¡c sè nguy¶n (a2 + b2 6= 0). N¸u a = bq + r v 0 ≤ r < |b| th¼ (a,b) = (b,r). Thuªt to¡n Euclid (thuªt to¡n t¼m ÷îc sè chung lîn nh§t cõa hai sè nguy¶n d÷ìng ). Gi£ sû r0 = a, r1 = b l c¡c sè nguy¶n d÷ìng. Ta ¡p döng li¶n ti¸p thuªt to¡n chia ri = ri+1 qi+1 + ri+2 , trong â 0 ≤ ri+2 < ri+1 , ∀i = 0, 1, 2, . . . v nhªn ÷ñc c¡c ph¦n d÷ r1 , r2 , . . . vîi r1 > r2 > . . . ¸n khi l¦n ¦u ti¶n nhªn ÷ñc ph¦n d÷ rn = 0 (n ≥ 2, 0 < ri+2 < ri+1 , ∀i = 0, 1, . . . , n − 3). Khi â (a, b) = (r0 , r1 ) = (r1 , r2 ) = . . . = (rn−2 , rn−1 ) = (rn−1 .qn−1 , rn−1 ) = rn−1 . Vªy (a, b) = rn−1 . V½ dö 1.2. Dòng thuªt to¡n Euclid t¼m ÷îc sè chung lîn nh§t cõa 3484 v 3276. Líi gi£i. Ta câ 3484 = 3276.1 + 208 3276 = 208.15 + 156 208 = 156.1 + 52 156 = 52.3 + 0. Vªy gcd(3484, 3276) = 52. V½ dö 1.3. T¼m mët c°p sè nguy¶n x, y º 3484x + 3276y = 52. Líi gi£i. Theo v½ vö tr¶n ta câ 5
52 = 208 − 156.1 ⇒ 52 = 208 − (3276 − 208.15) .1 = 16.208 − 3276 156 = 3276 − 208.15 52 = −3276 + 16.208 ⇒ 52 = −3276 + 16. (3484 − 3276.1) = 16.3484 − 17.3276 208 = 3484 − 3276.1 Do â 3484.16 + 3276.(−17) = 52. Vªy (x; y) = (16; −17). 1.2 Li¶n ph¥n sè ành ngh¾a 1.5. (Li¶n ph¥n sè húu h¤n, xem [3]) Li¶n ph¥n sè húu h¤n câ ë d i n (n ∈ N) l biºu thùc câ d¤ng 1 a0 + 1 a1 + 1 a2 + . . . + 1 an−1 + an trong â a0 l sè nguy¶n, ai l c¡c sè nguy¶n d÷ìng (∀i = 1, 2, . . . , n), an > 1 vîi n > 0. Li¶n ph¥n sè tr¶n ÷ñc kþ hi»u l [a0 ; a1 , a2 , . . . , an ]. ành ngh¾a 1.6. (Li¶n ph¥n sè væ h¤n, xem [3]) Cho a0, a1, a2, . . . l d¢y væ h¤n c¡c sè nguy¶n, ai > 0 vîi ∀i ≥ 1. Vîi méi k, °t Ck = [a0 ; a1 , a2 , . . . , ak ]. Khi â tçn t¤i giîi h¤n lim Ck = α. k→+∞ (Sü tçn t¤i n y s³ ÷ñc nâi rã trong t½nh ch§t ( 1.9) d÷îi ¥y). Lóc n y ta gåi α l gi¡ trà cõa li¶n ph¥n sè væ h¤n [a0 ; a1 , a2 , . . .] v kþ hi»u l α = [a0 ; a1 , a2 , . . .] . T½nh ch§t 1.2 (xem [3]). Méi sè húu t¿ l mët li¶n ph¥n sè húu h¤n. a Chùng minh. Gi£ sû x = , b > 0, a, b ∈ Z. °t r0 = a, r1 = b ta câ b   r0 = r1 q1 + r2 (0 < r2 < r1 )   r1 = r2 q2 + r3 (0 < r3 < r2 ) ...    rn−2 = rn−1 qn−1 + rn (0 < rn < rn−1 ) rn−1 = rn qn +0 6
Suy ra a r0 r2 1 1 1 x= = = q1 + = q 1 + r1 = q 1 + r = . . . = q1 + b r1 r1 q2 + 3 1 r2 r2 q2 + . . . + 1 qn−1 + qn ⇒ x = [q1 ; q2 , . . . , qn ] . V½ dö 1.4. H¢y biºu di¹n c¡c sè húu t 327 , 243 37 ,− 243 62 , 37 23 th nh li¶n ph¥n sè. Líi gi£i. Ta câ 32 = 4.7 + 4 7 = 1.4 + 3 4 = 1.3 + 1 3 = 3.1 32 1 ⇒ = [4; 1, 1, 3] = 4 + l li¶n ph¥n sè câ ë d i 3. T÷ìng tü ta công câ 7 1 1+ 1 1+ 3 243 243 62 = [6; 1, 1, 3, 5], − = [−7; 2, 3, 5], = [2; 1, 2, 3, 2]. 37 37 23 T½nh ch§t 1.3. (V· t½nh duy nh§t cõa li¶n ph¥n sè húu h¤n, xem [3]) Sü biºu di¹n mët sè húu t¿ q d÷îi d¤ng li¶n ph¥n sè [a0 ; a1 , a2 , . . . , an ] l duy nh§t. T½nh ch§t 1.4. (Cæng thùc t½nh gi£n ph¥n, xem [3]) Cho li¶n ph¥n sè húu h¤n [a0 ; a1 , a2 , . . . , an ]. X²t hai d¢y (pk )nk=0 v (qk )nk=0 ÷ñc x¡c ành nh÷ sau ( ( p 0 = a0 q0 = 1 p 1 = a1 a0 + 1 , q 1 = a1 , ∀k = 2, 3, . . . pk = ak pk−1 + pk−2 qk = ak qk−1 + qk−2 pk Khi â gi£n ph¥n thù k cõa li¶n ph¥n sè [a0 ; a1 , a2 , . . . , an ] l Ck = [a0 ; a1 , . . . , ak ] = . qk pk Chùng minh. Ta s³ chùng minh Ck = [a0 ; a1 , . . . , ak ] = b¬ng quy n¤p theo k, qk 1 vîi l÷u þ l Ck (k > 0) ÷ñc suy ra tø Ck−1 b¬ng c¡ch thay ak−1 bði ak−1 + . ak Thªt vªy a0 p0 C0 = [a0 ] = a0 = = , 1 q0 1 a1 a0 + 1 p1 C1 = [a0 ; a1 ] = a0 + = = , a1 a1 q1 7
1 a1 + a0 + 1 a2 C2 = [a0 ; a1 , a2 ] = 1 a1 + a2 a2 (a1 a0 + 1) + a0 a2 p 1 + p 0 p2 = = = . a2 a1 + 1 a2 q 1 + q 0 q2 Gi£ sû ak pk−1 + pk−2 pk Ck = [a0 ; a1 , . . . , ak ] = = , k ≥ 2. ak qk−1 + qk−2 qk Khi â 1 ak + pk−1 + pk−2 ak+1 Ck+1 = 1 ak + qk−1 + qk−2 ak+1 ak+1 (ak pk−1 + pk−2 ) + pk−1 ak+1 pk + pk−1 = = . ak+1 (ak qk−1 + qk−2 ) + qk−1 ak+1 qk + qk−1 Do â pk+1 Ck+1 = . qk+1 Vªy ta ¢ chùng minh ÷ñc pk Ck = [a0 ; a1 , . . . , ak ] = . qk V½ dö 1.5. T¼m c¡c gi£n ph¥n cõa li¶n ph¥n sè [6; 1, 1, 3, 5]. Líi gi£i. Ta câ b£ng sau k 0 1 2 3 4 ak 6 1 1 3 5 pk 6 7 13 46 243 qk 1 1 2 7 37 Vªy 13 46 243 C0 = 6, C1 = 7, C2 = , C3 = , C4 = . 2 7 37 T½nh ch§t 1.5 . (xem [3]) Cho Ck l gi£n ph¥n thù k cõa [a0 ; a1 , a2 , . . . , an ], vîi 1 ≤ k ≤ n v pk , qk ÷ñc x¡c ành nh÷ trong t½nh ch§t ( 1.4). Khi â pk qk−1 − pk−1 qk = (−1)k−1 . T½nh ch§t 1.6 (xem [3]). Gi£ sû {Ck } l d¢y gi£n ph¥n cõa li¶n ph¥n sè húu h¤n [a0 ; a1 , a2 , . . . , an ]. Khi â ta câ c¡c mèi li¶n h» sau 8
(−1)k−1 i) Ck − Ck−1 = , vîi 1 ≤ k ≤ n. qk qk−1 ak (−1)k ii) Ck − Ck−2 = , vîi 2 ≤ k ≤ n. qk qk−2 T½nh ch§t 1.7 (xem [3]). Vîi c¡c gi£n ph¥n Ck cõa li¶n ph¥n sè húu h¤n [a0; a1, a2, . . . , an] ta câ c¡c d¢y b§t ¯ng thùc sau i) C1 > C3 > C5 > . . . ii) C0 < C2 < C4 < . . . iii) méi gi£n ph¥n l´ C2j−1 ·u lîn hìn méi gi£n ph¥n ch®n C2i . T½nh ch§t 1.8 (xem [3]). Vîi måi k = 0, 1, . . . , n th¼ (pk , qk ) = 1 (tùc l pk , qk nguy¶n tè còng nhau). T½nh ch§t 1.9 (xem [3]). Cho a0, a1, a2, . . . l d¢y væ h¤n c¡c sè nguy¶n, ai > 0 vîi ∀i ≥ 1. Vîi méi k, °t Ck = [a0 ; a1 , a2 , . . . , ak ]. Khi â tçn t¤i giîi h¤n lim Ck . k→+∞ Chùng minh. Theo t½nh ch§t ( 1.7) ta câ C1 > C3 > C5 > . . . > C2n−1 > C2n+1 > . . . C0 < C2 < C4 < . . . < C2n−2 < C2n < . . . C2j−1 > C2i , vîi måi i, j. Tø â suy ra d¢y {C2k+1 }, k = 0, 1, . . . l d¢y gi£m v bà ch°n d÷îi bði C0 , cán d¢y {C2k }, k = 0, 1, . . . l d¢y t«ng v bà ch°n tr¶n bði C1 . Theo lþ thuy¸t v· giîi h¤n cõa d¢y sè th¼ tçn t¤i c¡c giîi h¤n lim C2k+1 = α , lim C2k = β. k→+∞ k→+∞ Theo t½nh ch§t ( 1.6) ta câ (−1)2k 1 C2k+1 − C2k = = > 0. (a) q2k+1 q2k q2k+1 q2k 9
M°t kh¡c ta l¤i câ qk ≥ k. (b) Ta s³ chùng minh (b) b¬ng quy n¤p nh÷ sau - vîi k = 0 th¼ q0 = 1 n¶n q0 > 0. - vîi k = 1 th¼ q1 = a1 n¶n q1 ≥ 1 (do a1 nguy¶n d÷ìng). - gi£ sû (b) ¢ óng ¸n k, tùc l qk ≥ k. - vîi k + 1 ta câ qk+1 = ak+1 qk + qk−1 . Theo gi£ thi¸t quy n¤p th¼ qk ≥ k, qk−1 ≥ k − 1 cán ak ≥ 1 n¶n ta câ qk+1 ≥ k + k − 1 ≥ k + 1 (hiºn nhi¶n, vîi ∀k ≥ 2). Vªy (b) óng vîi k + 1 n¶n vîi måi k = 0, 1, . . . th¼ qk ≥ k. Nh÷ vªy ta suy ra 1 1 0< ≤ , ∀k ≥ 1. q2k+1 q2k 2k (2k + 1) Cho k → +∞ ta thu ÷ñc 1 lim = 0. k→+∞ q2k+1 q2k Vªy lim (C2k+1 − C2k ) = 0. k→+∞ Tø â ta câ α = β. (c) H» thùc (c) chùng tä tçn t¤i giîi h¤n lim Ck = α. k→+∞ â l i·u ph£i chùng minh. Nhªn x²t 1.1. Tø t½nh ch§t (1.9) suy ra r¬ng ùng vîi d¢y a0, a1, a2, . . . th¼ tçn t¤i lim [a0 ; a1 , a2 , . . . , ak ] = lim Ck = α. â ch½nh l lþ do v¼ sao ta l¤i chån α l m k→+∞ k→+∞ ành ngh¾a cho li¶n ph¥n sè væ h¤n [a0 ; a1 , a2 , . . . , ak , . . .]. 10
T½nh ch§t 1.10 (xem [3]). Cho a0, a1, a2, . . . l d¢y væ h¤n c¡c sè nguy¶n, ai > 0 vîi ∀i ≥ 1. X²t li¶n ph¥n sè væ h¤n α = [a0 ; a1 , a2 , . . .]. Khi â α l sè væ t¿. Chùng minh. Gi£ sû α l sè húu t¿, tùc l a α = , a, b ∈ Z, b > 0, (a, b) = 1. b Theo ph¦n chùng minh t½nh ch§t ( 1.9) ta câ lim C2k = α k→+∞ m d¢y {C2k }, k = 0, 1, . . . l d¢y t«ng n¶n C2k ≤ α, vîi måi k = 0, 1, . . . lim C2k+1 = α k→+∞ m d¢y {C2k+1 }, k = 0, 1, . . . l d¢y gi£m n¶n α ≤ C2k+1 , vîi måi k = 0, 1, . . . Vªy ta câ C2n ≤ α ≤ C2n+1 , ∀n = 0, 1, . . . Do α = [a0 ; a1 , a2 , . . .] n¶n α 6= Ck , vîi måi k = 0, 1, . . . Tø â ta câ C2n < α < C2n+1 , ∀n = 0, 1, . . . 1 ⇒ 0 < α − C2n < C2n+1 − C2n = , ∀n = 0, 1, . . . q2n+1 q2n p2n M°t kh¡c do C2n = n¶n theo tr¶n ta suy ra q2n 1 0 < αq2n − p2n < , ∀n = 0, 1, . . . q2n+1 a Thay α = ta i ¸n b b b 0 < aq2n − bp2n < ≤ , ∀n = 0, 1, . . . q2n+1 2n + 1 Do aq2n − bp2n l sè nguy¶n n¶n theo tr¶n ta suy ra b 1≤ , ∀n = 0, 1, . . . 2n + 1 Cho n → +∞ ta thu ÷ñc 1≤0 i·u n y l væ lþ. Vªy α l sè væ t¿. 11
T½nh ch§t 1.11 (xem [3]). Måi sè væ t¿ α ·u biºu di¹n ÷ñc mët c¡ch duy nh§t d÷îi d¤ng mët li¶n ph¥n sè væ h¤n. Chùng minh. i) Gi£ sû α = α0 l sè væ t¿. Ta x¥y düng d¢y a0, a1, a2, . . . mët c¡ch truy hçi nh÷ sau 1 a0 = [α0 ] , α1 = , α 0 − a0 1 a1 = [α1 ] , α2 = , α 1 − a1 1 a2 = [α2 ] , α3 = , α 2 − a2 ... ... 1 ak = [αk ] , αk+1 = . αk − ak Do α0 l sè væ t¿ n¶n 0 < α0 − a0 < 1, do â α1 tçn t¤i. Ta s³ chùng minh αk l sè væ t¿, vîi måi k = 0, 1, . . . b¬ng quy n¤p nh÷ sau - vîi k = 0 th¼ rã r ng α0 l sè væ t¿. - gi£ sû αk l sè væ t¿ (k ≥ 0 ), khi â 0 < αk − ak < 1 v ak l sè nguy¶n n¶n αk − ak 1 l sè væ t¿, do â αk+1 = tçn t¤i v l sè væ t¿, çng thíi αk+1 > 1. Khi â α k − ak ak+1 = [αk+1 ] ≥ 1. Tâm l¤i ta câ a0 , a1 , a2 , . . . l c¡c sè nguy¶n, ai > 0 vîi ∀i ≥ 1. ii) Ta s³ chùng minh b¬ng quy n¤p α = [a0 ; a1 , a2 , . . . , ak , αk+1 ] , k = 0, 1, . . . Thªt vªy 1 - vîi k = 0 th¼ [a0 ; α1 ] = a0 + = a0 + (α0 − a0 ) = α0 = α. α1 1 1 1 - vîi k = 1 th¼ [a0 ; a1 , α2 ] = a0 + = a0 + = a0 + = α. 1 a1 + (α1 − a1 ) α1 a1 + α2 - gi£ sû câ [a0 ; a1 , a2 , . . . , ak , αk+1 ] = α. Khi â [a0 ; a1 , a2 , . . . , ak+1 , αk+2 ] 1 1 = a0 + = a0 + , 1 1 a1 + a1 + 1 1 a2 + . . . + a2 + . . . + 1 1 ak+1 + ak + αk+2 αk+1 12
1 do ak+1 + = ak+1 + (αk+1 − ak+1 ) = αk+1 . αk+2 Do â [a0 ; a1 , a2 , . . . , ak+1 , αk+2 ] = [a0 ; a1 , a2 , . . . , ak , αk+1 ] = α. Vªy ta ¢ chùng minh ÷ñc α = [a0 ; a1 , a2 , . . . , ak , αk+1 ] , k = 0, 1, . . . iii) Ti¸p theo ta s³ chùng minh α = lim Ck , k→+∞ vîi Ck = [a0 ; a1 , a2 , . . . , ak ]. Thªt vªy, theo t½nh ch§t cõa gi£n ph¥n ta câ pk+1 pk α − Ck = − , qk+1 qk pk+1 = αk+1 pk + pk−1 trong â qk+1 = αk+1 qk + qk−1 . Vªy suy ra αk+1 pk + pk−1 pk − (pk qk−1 − pk−1 qk ) (−1)k α − Ck = − = = . αk+1 qk + qk−1 qk qk (αk+1 qk + qk−1 ) qk (αk+1 qk + qk−1 ) V¼ αk+1 qk + qk−1 > ak+1 qk + qk−1 = qk+1 n¶n 1 1 |α − Ck | < ≤ . qk qk+1 k (k + 1) Cho k → +∞ ta thu ÷ñc α = lim Ck . k→+∞ Nh÷ vªy α = [a0 ; a1 , a2 , . . .] . iv) B¥y gií ta chùng minh biºu di¹n â l duy nh§t. Gi£ sû α câ hai biºu di¹n α = [a0 ; a1 , a2 , . . .] = [b0 ; b1 , b2 , . . .] . Ta bi¸t r¬ng C2n < α < C2n+1 , ∀n = 0, 1, . . . 13
Do â C0 < α < C1 hay 1 a0 < α < a0 + . a1 Do a0 nguy¶n v a1 ≥ 1 n¶n suy ra [α] = a0 . T÷ìng tü [α] = b0 . Nh÷ vªy ta thu ÷ñc a0 = b0 , [a1 ; a2 , a3 , . . .] = [b1 ; b2 , b3 , . . .] Ti¸p töc qu¡ tr¼nh nh÷ tr¶n ta câ ai = bi , [ai+1 ; ai+2 , ai+3 , . . .] = [bi+1 ; bi+2 , bi+3 , . . .] , ∀i = 0, 1, . . . i·u â câ ngh¾a l ak = bk , ∀k = 0, 1, . . . Vªy måi sè væ t¿ α ·u biºu di¹n ÷ñc mët c¡ch duy nh§t d÷îi d¤ng mët li¶n ph¥n sè væ h¤n. √ V½ dö 1.6. H¢y biºu di¹n c¡c sè √ 5 v α = 3+ 7 2 th nh li¶n ph¥n sè væ h¤n. Líi gi£i. i) biºu di¹n sè √5 th nh li¶n ph¥n sè væ h¤n. √ a0 = 5 = 2, √ 1 a1 = √ = 5 + 2 = 4, 5−2 √ 1 a2 = √ = 5 + 2 = 4. 5+2−4 Vªy a0 = 2, an = 4 , ∀n = 1, 2, . . . 14
Do â √ 5 = [2; 4, 4, 4, . . .] . √ ii) biºu di¹n sè α = 3+ 7 2 th nh li¶n ph¥n sè væ h¤n. a0 = [α] = 2 , h 1 i √7 + 1 √ 7+1 a1 = = = 1, β = , α−2 3 3 √ √ 1 a2 = = 7 + 2 = 4, γ = 7 + 2, β−1 h 1 i √7 + 2 √ 7+2 a3 = = = 1, θ = , λ−4 3 3 h 1 i √7 + 1 √ 7+1 a4 = = = 1, δ = , θ−1 2 2 h 1 i √7 + 1 a5 = = = [β] = 1. δ−1 3 Vªy a0 = 2, a4n+1 = a4n+3 = a4n+4 = 1, a4n+2 = 4 , ∀n = 0, 1, . . . Do â √ 3+ 7 α= = 2; 1, 4, 1, 1 2 (li¶n ph¥n sè væ h¤n tu¦n ho n chu ký 4). 1.3 Ph÷ìng tr¼nh Diophante tuy¸n t½nh ành ngh¾a 1.7 (xem [3]). Ph÷ìng tr¼nh Dipophante tuy¸n t½nh l ph÷ìng tr¼nh câ d¤ng a1 x 1 + a2 x 2 + . . . + an x n = c n trong â c¡c h» sè ai , c ∈ Z, a2i 6= 0, c¡c bi¸n sè xi ∈ Z, ∀i = 1, 2, . . . , n. P i=1 V½ dö 1.7. 32x + 40y = 24 l mët ph÷ìng tr¼nh Diophante tuy¸n t½nh vîi hai ©n x, y. 15
ành l½ 1.2 (xem [3]). X²t ph÷ìng tr¼nh Diophante tuy¸n t½nh Ax + By = C. (1) i) (1) câ nghi»m khi v ch¿ khi d = (A, B) |C . ii) N¸u (x0 , y0 ) l mët nghi»m cõa ph÷ìng tr¼nh (1) th¼ måi nghi»m cõa ph÷ìng tr¼nh (1) ÷ñc cho bði cæng thùc  B  x = x0 + d t   , t ∈ Z.  y = y0 − A t   d Chùng minh. i) ⇒) Gi£ sû (x0 , y0 ) l nghi»m cõa ph÷ìng tr¼nh (1), tùc l Ax0 + By0 = C. d |A Ta câ d = (A, B) ⇒ ⇒ d |(Ax0 + By0 ) hay d |C . d |B ⇐) Gi£ sû d = (A, B) |C Khæng gi£m têng qu¡t, ta gi£ sû B > 0. V¼ d = (A, B) |C n¶n ∃a, b, c ∈ Z sao cho A = da, B = db, C = dc, (a, b) = 1. Khi â (1) t÷ìng ÷ìng vîi ax + by = c. (2) V¼ (a, b) = 1 n¶n tªp hñp {1a, 2a, . . . , ba} l mët h» th°ng d÷ ¦y õ modulo b n¶n ∃x ∈ {1, 2, . . . , b} : ax ≡ c (mod b) ⇒ ∃x ∈ {1, 2, . . . , b} : ax − c ≡ 0 (mod b) ⇒ ∃x ∈ {1, 2, . . . , b} , ∃y ∈ Z : ax − c = by ⇒ ∃x ∈ {1, 2, . . . , b} , ∃y ∈ Z : ax + by = c. i·u â câ ngh¾a l ∃x, y ∈ Z : ax + by = c. 16
Chùng tä ph÷ìng tr¼nh (2) câ nghi»m nguy¶n (x,y), tùc (1) câ nghi»m nguy¶n (x,y). ii)  B  x = x0 + d t   ⇐) N¸u , t ∈ Z th¼  y = y0 − A t   d B A Ax + By = A x0 + t + B y0 − t = Ax0 + By0 = C . d d Chùng tä (x,y) l nghi»m cõa ph÷ìng tr¼nh (1). ⇒) N¸u (x, y) l nghi»m cõa ph÷ìng tr¼nh (1), tùc ph÷ìng tr¼nh (2) th¼ ax + by = c = ax0 + by0 ⇒ a(x − x0 ) = b(y0 − y) ⇒ b |a(x − x0 ) . V¼ (a, b) = 1 n¶n b |(x − x0 ) ⇒ ∃t ∈ Z : x − x0 = bt ⇔ ∃t ∈ Z : x = x0 + bt. Tø â y = y0 − at. Vªy x = x0 + bt , t∈Z y = y0 − at hay  B  x = x0 + d t   , t ∈ Z.  y = y0 − A t   d Nhªn x²t 1.2. Vi»c gi£i ph÷ìng tr¼nh (1) quy v· vi»c t¼m i) d = (A, B). ii) Mët nghi»m ri¶ng (x0 , y0 ) cõa ph÷ìng tr¼nh (1) . Chóng ta bi¸t r¬ng ph÷ìng tr¼nh (1) câ nghi»m n¸u v ch¿ n¸u d = (A, B) |C . Trong tr÷íng hñp n y ta gi£ sû A = ad, B = bd, C = cd th¼ (a, b) = 1 v khi â ph÷ìng tr¼nh (1) t÷ìng ÷ìng vîi ph÷ìng tr¼nh ax + by = c. (2) N¸u (x0 , y0 ) l mët nghi»m cõa (2) th¼ måi nghi»m cõa (2) ÷ñc cho bði cæng thùc x = x0 + bt , t ∈ Z. y = y0 − at 17
Nh÷ vªy vi»c gi£i ph÷ìng tr¼nh (2) quy v· vi»c t¼m mët nghi»m (x0 , y0 ) cõa nâ. X²t ph÷ìng tr¼nh ax + by = 1. (3) N¸u (x1 , y1 ) l mët nghi»m cõa (3) th¼ (cx1 , cy1 ) l mët nghi»m cõa (2). Th nh thû ta quy v· b i to¡n: Cho (a, b) = 1. H¢y t¼m mët nghi»m cõa ph÷ìng tr¼nh (3). a Ta biºu di¹n ph¥n sè th nh li¶n ph¥n sè húu h¤n |b| a = [a0 ; a1 , a2 , . . . , an ] . |b| pn−1 pn Gåi Cn−1 = v Cn = l hai gi£n ph¥n cuèi còng cõa li¶n ph¥n sè n y. Ta câ qn−1 qn a |b| pn 1.5 = , (a, b) = 1, (pn , qn ) = 1 n¶n a = pn , |b| = qn . Theo t½nh ch§t ( ) ta câ qn pn qn−1 − pn−1 qn = (−1)n−1 ⇒ aqn−1 − |b| pn−1 = (−1)n−1 ⇒ a(−1)n−1 qn−1 − |b| (−1)n−1 pn−1 = 1. Vªy n¸u b > 0 th¼ ph÷ìng tr¼nh (3) câ mët nghi»m l x1 = (−1)n−1 .qn−1 y1 = (−1)n .pn−1 N¸u b < 0 th¼ ph÷ìng tr¼nh (3) câ mët nghi»m l x1 = (−1)n−1 .qn−1 y1 = (−1)n−1 .pn−1 1.3.1 T¼m nghi»m ri¶ng düa v o gi£n ph¥n Ti¸n h nh thüc hi»n theo c¡c b÷îc sau B÷îc 1: T¼m d = (A, B) v ÷a ph÷ìng tr¼nh (1) v· ph÷ìng tr¼nh (2) vîi (a, b) = 1. B÷îc 2: Vi¸t |b|a = [a0; a1, a2, . . . , an]. B÷îc 3: T½nh gi£n ph¥n Cn−1 = [a0; a1, . . . , an−1] = pqn−1 n−1 . Suy ra pn−1 v qn−1 . B÷îc 4: Suy ra mët nghi»m ri¶ng (x0, y0) cõa ph÷ìng tr¼nh (2) N¸u b > 0 th¼ x0 = (−1)n−1 .c.qn−1 n y0 = (−1) n−1 .c.pn−1 x0 = (−1) .c.qn−1 N¸u b < 0 th¼ y0 = (−1)n−1 .c.pn−1 18
V½ dö 1.8. Gi£i ph÷ìng tr¼nh Diophante tuy¸n t½nh 342x − 123y = 15. (4) Líi gi£i. Ph÷ìng tr¼nh ¢ cho t÷ìng ÷ìng vîi ph÷ìng tr¼nh 114x − 41y = 5. (4a) 114 Ta câ = [2; 1, 3, 1, 1, 4], vîi n = 5. 41 p4 25 ( C4 = = [2; 1, 3, 1, 1] = p4 = 25 q4 9 ⇒ q4 = 9. (p4 , q4 ) = 1 Do b = −41 < 0 n¶n mët nghi»m ri¶ng cõa (4a) l x0 = (−1)5−1 .5.9 = 45 y0 = (−1)5−1 .5.25 = 125. Vªy nghi»m cõa ph÷ìng tr¼nh (4a), tùc ph÷ìng tr¼nh (4) l x = 45 + 41t , t ∈ Z. y = 125 + 114t 1.3.2 T¼m nghi»m ri¶ng düa v o thuªt to¡n Euclid Ti¸n h nh thüc hi»n theo c¡c b÷îc sau B÷îc 1: T¼m d = (|A| , |B|) theo thuªt to¡n Euclid mð rëng. B÷îc 2: Biºu thà d nh÷ mët tê hñp tuy¸n t½nh cõa A v B, ch¯ng h¤n d = nA + mB (n, m ∈ Z) . B÷îc 3: Nh¥n hai v¸ ¯ng thùc tr¶n vîi Cd ta ÷ñc Cn Cm A +B = C. d d B÷îc 4: Suy ra mët nghi»m ri¶ng (x0, y0) cõa ph÷ìng tr¼nh (1) l  Cn  x0 =   d  y0 = Cm   d 19