სტატიები

5.5: მეტი ინფორმაცია GCD– ზე


ამ ნაწილში განვიხილავთ რამდენიმე ტექნიკურ შედეგს ( gcd (a, b) ) შესახებ.

თეორემა ( PageIndex {1} label {thm: EA} )

მოდით (d = gcd (a, b) ), სადაც (a, b in mathbb {N} ). შემდეგ [ {as + bt mid s, t in mathbb {Z} } = {nd mid n in mathbb {Z} }. nonumber ] მაშასადამე, (a ) და (b ) ყოველი ხაზოვანი კომბინაცია არის ( gcd (a, b) ) - ის ჯერადი და პირიქით, ( gcd (a , ბ) ) გამოხატულია როგორც (a ) და (b ) წრფივი კომბინაცია.

მტკიცებულება

მოკლედ რომ ვთქვათ, მოდით [S = {as + bt mid s, t in mathbb {Z} }, qquad mbox {and} qquad T = {nd mid n in mathbb { Z} }. nonumber ] ჩვენ ამას ვაჩვენებთ (S = T ) იმის დადასტურებით, რომ (S subseteq T ) და (T subseteq S ).

მოდით (x in S ). იმის დასამტკიცებლად, რომ (S subseteq T ), ჩვენ გვინდა ვაჩვენოთ რომ (x in T ) ასევე. (S ) - ში ყოფნა ნიშნავს (x = როგორც + bt ) ზოგიერთი მთელი (s ) და (t ) რიცხვებისთვის. მას შემდეგ, რაც (d = gcd (a, b) ), ჩვენ ვიცით, რომ (d შუა ა ) და (დ შუა ბ ). აქედან გამომდინარე, (a = da ') და (b = db' ) ზოგიერთი მთელი რიცხვისთვის (a ') და (b' ). შემდეგ [x = as + bt = da's + db't = d (a's + b't), nonumber ] სადაც (a's + b't ) არის მთელი რიცხვი. ეს გვიჩვენებს, რომ (x ) არის (d ) - ის ჯერადი. მაშასადამე, (x in T ).

იმის ჩვენება, რომ (T subseteq S ), საკმარისია ვაჩვენოთ, რომ (d in S ). მიზეზი არის ის, რომ თუ (d = as + bt ) ზოგიერთი მთელი რიცხვისთვის (s ) და (t ), მაშინ (nd = n (as + bt) = a (ns) + b (nt) ) ნიშნავს რომ (nd in S ).

იმის დასამტკიცებლად, რომ (d in S ), გაითვალისწინეთ (S ^ + ). მას შემდეგ, რაც (a = a cdot1 + b cdot0 ), გვაქვს (a in S ^ + ). მაშასადამე, (S ^ + ) არის პოზიტიური მთელი რიცხვების არაწმენდილი ნაკრები. კარგად დალაგების პრინციპი გულისხმობს, რომ (S ^ + ) - ს აქვს ყველაზე პატარა ელემენტი. დარეკეთ (e ). შემდეგ [e = as ^ * + bt ^ * nonumber ] ზოგიერთი მთელი რიცხვისთვის (s ^ * ) და (t ^ * ). ჩვენ უკვე ვიცით, რომ (a in S ^ + ). როგორც ყველაზე პატარა ელემენტი (S ^ + ) - ში, უნდა გვქონდეს (e leq a ). შემდეგ (a = eq + r ) ზოგიერთი მთელი რიცხვისთვის (q ) და (r ), სადაც (0 leq r 0 ), მაშინ [r = a-eq = a- (როგორც ^ * + bt ^ *) q = a (1-s ^ * q) + b (-t ^ * q). nonumber ] ეს ხდის (r ) წრფივ კომბინაციას (a ) და (b ). მას შემდეგ, რაც (r> 0 ), ვხვდებით (r S ^ + ). რადგან (r

მოდით (f ) იყოს (a ) და (b ) ნებისმიერი საერთო გამყოფი. შემდეგ (f mid a ) და (f mid b ). აქედან გამომდინარეობს, რომ (f mid (ax + by) ) ნებისმიერი მთელი რიცხვისთვის (x ) და (y ). კერძოდ, (f mid (as ^ * + bt ^ *) = e ). აქედან გამომდინარე, (f leq e ). რადგან (e ) თავისთავად (a ) და (b ) - ის საერთო გამყოფია და ჩვენ ახლახანს დავამტკიცეთ, რომ (e ) უფრო დიდია, ვიდრე (a ) და ნებისმიერი სხვა საერთო გამყოფი. (b ), მთელი რიცხვი (e ) თავად უნდა იყოს უდიდესი საერთო გამყოფი. აქედან გამომდინარეობს, რომ (d = gcd (a, b) = e in S ^ + ). მტკიცებულება დასრულებულია.

დასკვნა ( PageIndex {2} )

ორი ნულოვანი მთელი რიცხვის (a ) და (b ) უდიდესი საერთო გამყოფი არის ყველაზე მცირე დადებითი მთელი რიცხვი მათ ხაზოვან კომბინაციებს შორის. სხვა სიტყვებით რომ ვთქვათ, ( gcd (a, b) ) არის ყველაზე პატარა დადებითი ელემენტი ( {as + bt mid s, t in mathbb {Z} } ).

დასკვნა ( PageIndex {3} )

ნებისმიერი ნულოვანი მთელი რიცხვისთვის (a ) და (b ), არსებობს მთელი რიცხვები (s ) და (t ) ისეთი, რომ ( gcd (a, b) = as + bt ).

მტკიცებულება

თეორემა 5.5.1 ამტკიცებს, რომ (a ) და (b ) ყველა წრფივი კომბინაციის სიმრავლე უდრის ( gcd (a, b) ) -ის ყველა გამრავლების სიმრავლეს. რადგან ( gcd (a, b) ) თავისთავად მრავლობითია, ის ტოლი უნდა იყოს ერთ-ერთი იმ ხაზოვანი კომბინაციისა. ამრიგად, ( gcd (a, b) = sa + tb ) ზოგიერთი მთელი რიცხვისთვის (s ) და (t ).

თეორემა ( PageIndex {4} )

ორი არა ნულოვანი მთელი რიცხვი (a ) და (b ) შედარებით მარტივი არის თუ მხოლოდ და მხოლოდ (როგორც + bt = 1 ) ზოგიერთი მთელი (s ) და (t ) რიცხვებისთვის.

მტკიცებულება

შედეგი არის პირდაპირი განსაზღვრა, რომ (a ) და (b ) ნათქვამია, რომ შედარებით პირველყოფილია, თუ ( gcd (a, b) = 1 ).

მაგალითი ( PageIndex {1} label {მაგ .: moregcd-01} )

ცხადია, რომ 5 და 7 შედარებით მარტივი არიან, ასე რომ, 14 და 27. იპოვნეთ ამ ორი წყვილი რიცხვის წრფივი კომბინაცია, რომელიც უდრის 1-ს.

გამოსავალი

შემოწმების გზით, ან გაფართოებული ევკლიდეს ალგორითმის გამოყენებით ვხვდებით (3 cdot5-2 cdot7 = 1 ) და (2 cdot14-1 cdot27 = 1 ).

პრაქტიკული სავარჯიშო ( PageIndex {1} label {he: moregcd-01} )

აჩვენეთ, რომ ( gcd (133,143) = 1 ) შესაბამისი წრფივი კომბინაციის მოძიებით.

პრაქტიკული სავარჯიშო ( PageIndex {2} label {he: moregcd-02} )

აჩვენეთ, რომ 757 და 1215 შედარებით სწორხაზოვანია შესაბამისი ხაზოვანი კომბინაციის გამოყენებით.

მაგალითი ( PageIndex {2} label {მაგ .: moregcd-02} )

ეს გამომდინარეობს [(- 1) cdot n + 1 cdot (n + 1) = 1 nonumber ] - დან, რომ ( gcd (n, n + 1) = 1 ). ამრიგად, თანმიმდევრული პოზიტიური მთელი რიცხვების ნებისმიერი წყვილი შედარებით პირველყოფილია.

თეორემა ( PageIndex {5} ) (ევკლიდეს ლემა)

მოდით (a, b, c in mathbb {Z} ). თუ ( gcd (a, c) = 1 ) და (c mid ab ), მაშინ (c mid b ).

დისკუსია

მოდით ჩამოვწეროთ რა ვიცით და რისი ჩვენებაც გვინდა (WTS): [ start {array} {ll} mbox {Know}: & as + ct = 1 mbox {მთელი რიცხვისთვის $ s $ და $ t $}, & ab = cx mbox {მთელი რიცხვისთვის $ x $}, mbox {WTS}: & b = cq mbox {მთელი რიცხვისთვის $ q $}. end {array} nonumber ] იმისთვის, რომ შეგვეძლოს აჩვენოს, რომ (b = cq ) მთელი მთელი რიცხვისთვის (q ), უნდა მოვიძიოთ გარკვეული ინფორმაცია (b ) - ს შესახებ. ეს ინფორმაცია უნდა მომდინარეობდეს ორი განტოლებიდან (როგორც + ct = 1 ) და (ab = cx ). მას შემდეგ, რაც (b = b cdot1 ), შეგვიძლია გავამრავლოთ (b ) ორივე მხარეს (როგორც + ct = 1 ). კონვენციის მიხედვით, ჩვენ არ შეგვიძლია დავწეროთ

((როგორც + ct = 1) cdot b ).

ეს აღნიშვნა დაუშვებელია! მიზეზი არის: არ შეიძლება განტოლება გავამრავლოთ რიცხვზე. უფრო მეტიც, ჩვენ უნდა გავამრავლოთ ორივე მხარე განტოლების რიცხვით: [b = 1 cdot b = (as + ct) cdot b = asb + ctb. nonumber ] ცხადია, (ctb ) არის (c ) - ის ჯერადი; ჩვენ ერთი ნაბიჯით მივუახლოვდით ჩვენს მიზანს. მას შემდეგ, რაც (asb = ab cdot s ), და ჩვენ ვიცით, რომ (ab ) ნამდვილად არის (c ) - ის ჯერადი, ამიტომ მტკიცებულება შეიძლება დასრულდეს. ახლა ჩვენ მზად ვართ დავაკავშიროთ ფხვიერი ბოლოები და გავაპრიალოთ მტკიცებულება.

მტკიცებულება

ვივარაუდოთ ( gcd (a, c) = 1 ) და (c mid ab ). არსებობს მთელი რიცხვები (s ) და (t ) ისეთი, რომ [as + ct = 1. nonumber ] ამას მივყავართ [b = 1 cdot b = (as + ct) cdot b = asb + ctb nonumber ] მას შემდეგ, რაც (c mid ab ), არსებობს მთელი რიცხვი (x ) ისეთი, რომ (ab = cx ). შემდეგ [b = ab cdot s + ctb = cx cdot s + ctb = c (xs + tb), nonumber ] სადაც (xc + tb in mathbb {Z} ). ამიტომ, (გ შუა ბ ).

დასკვნა ( PageIndex {6} )

თუ (a, b in mathbb {Z} ) და (p ) არის მარტივი ისეთი, რომ (p mid ab ), მაშინ ან (p mid a ), ან (p შუა ბ ).

მტკიცებულება

თუ (p შუა ა), ჩვენ დავამტკიცეთ დადასტურება. თუ (p n შუა a), მაშინ ( gcd (p, a) = 1 ), და ევკლიდეს ლემა ნიშნავს რომ (p mid b ).

ჩვენ არ შეგვიძლია გამოვიყენოთ დასკვნა, თუ (p ) კომპოზიტურია. მაგალითად, (6 შუა 4 cdot15 ), მაგრამ (6 n შუა 4 ) და (6 n შუა 15 ). მეორეს მხრივ, როდესაც (p mid ab ), სადაც (p ) არის უმთავრესი, შესაძლებელია გქონდეს ორივე (p mid a ) და (p mid b ). მაგალითად, (5 შუა 15 cdot 25 ), ჩვენ გვაქვს ორივე (5 შუა 15 ) და (5 შუა 25 ).

დასკვნა ( PageIndex {7} )

თუ (a_1, a_2, ldots, a_n in mathbb {Z} ) და (p ) არის მარტივი ისეთი, რომ (p mid a_1 a_2 cdots a_n ), მაშინ (p mid) a_i ) ზოგიერთისთვის (i ), სადაც (1 leq i leq n ). შესაბამისად, თუ პრემიერ (p ) იყოფა (n ) ფაქტორების პროდუქტს, მაშინ (p ) უნდა დაყოს ამ (n ) ფაქტორებიდან მინიმუმ ერთი.

მტკიცებულება

ჩვენ დავატოვებთ სავარჯიშოდ.

მაგალითი ( PageIndex {3} label {მაგ: moregcd-03} )

დაამტკიცეთ, რომ ( sqrt {2} ) არარაციონალურია.

შენიშვნა

ჩვენ ადრე დავამტკიცეთ, რომ პრაქტიკული სავარჯიშოების დროს ირაციონალურია ( sqrt {2} ). ჩვენს მიერ წარმოდგენილ გამოსავალს მცირე ნაკლი აქვს. ამ მტკიცებულების ძირითადი ნაბიჯი ამტკიცებს, რომ [ mbox {მთელი რიცხვი 2 იყოფა $ m ^ 2 $, შესაბამისად 2 იყოფა $ m $}. nonumber ] ეს პრეტენზია ზოგადად მცდარია. მაგალითად, 4 იყოფა (6 ^ 2 ), მაგრამ 4 არ იყოფა 6. ამიტომ, ჩვენ უნდა გავამართლოთ, თუ რატომ მოქმედებს ეს პრეტენზია 2-ისთვის.

გამოსავალი

დავუშვათ, რომ ( sqrt {2} ) რაციონალურია, მაშინ ჩვენ შეგვიძლია დავწეროთ [ sqrt {2} = frac {m} {n} nonumber ] რამდენიმე დადებითი მთელი რიცხვისთვის (m ) და (n) ), რომლებიც არ იზიარებენ რაიმე საერთო გამყოფს, გარდა 1. ორივე გვერდის კვადრატისა და ჯვარედინად გამრავლებისა იძლევა [2n ^ 2 = m ^ 2. nonumber ] ამრიგად, 2 იყოფა (მ ^ 2 ). მას შემდეგ, რაც 2 არის უმთავრესი, ევკლიდეს ლემა გულისხმობს, რომ 2 – მა ასევე უნდა გაყო (მ). შემდეგ ჩვენ შეგვიძლია დავწეროთ (m = 2s ) ზოგიერთი მთელი (s) - ისთვის. ზემოთ განტოლება ხდება [2n ^ 2 = m ^ 2 = (2s) ^ 2 = 4s ^ 2. nonumber ] მაშასადამე, [n ^ 2 = 2s ^ 2, nonumber ], რაც გულისხმობს, რომ 2 იყოფა (n ^ 2 ). კიდევ ერთხელ, ვინაიდან 2 არის უმთავრესი, ევკლიდეს ლემა გულისხმობს, რომ 2 ასევე ყოფს (n ). ჩვენ დავამტკიცეთ, რომ ორივე (მ ) და (n ) იყოფა 2-ზე. ეს ეწინააღმდეგება მოსაზრებას, რომ (მ ) და (n ) არ იზიარებენ საერთო გამყოფს. ამრიგად, ( sqrt {2} ) არარაციონალური უნდა იყოს.

პრაქტიკული სავარჯიშო ( PageIndex {3} label {he: moregcd-03} )

დაამტკიცეთ, რომ ( sqrt {7} ) არარაციონალურია.

ჩვენ ვხურავთ ამ განყოფილებას ნამდვილად მომხიბლავი შედეგით.

თეორემა ( PageIndex {8} )

ნებისმიერი დადებითი მთელი რიცხვისთვის (მ ) და (n ), ( gcd (F_m, F_n) = F _ { gcd (მ, n)} ).

დასკვნა ( PageIndex {9} )

ნებისმიერი დადებითი მთელი რიცხვისთვის (n ), (3 mid F_n Leftrightarrow 4 mid n ).

მტკიცებულება

( ( Rightarrow )) თუ (3 შუა F_n ), მაშინ, რადგან (F_3 = 4 ), გვაქვს [3 = gcd (3, F_n) = gcd (F_4, F_n) = F _ { gcd (4, n)}. nonumber ] აქედან გამომდინარეობს, რომ ( gcd (4, n) = 4 ), რაც თავის მხრივ გულისხმობს (4 შუა n ).

( ( Leftarrow )) თუ (4 შუა n ), მაშინ ( gcd (4, n) = 4 ) და [ gcd (3, F_n) = gcd (F_4, F_n ) = F _ { gcd (4, n)} = F_4 = 3; nonumber ] ამიტომ, (3 შუა F_n ).

რეზიუმე და მიმოხილვა

  • ორი ნულოვანი მთელი რიცხვის გათვალისწინებით, არსებობს მხოლოდ ერთი სპეციალური წრფივი კომბინაცია, რომელიც უდრის მათ უდიდეს საერთო გამყოფს.
  • ყველა სხვა ხაზოვანი კომბინაცია მხოლოდ მათი უდიდესი საერთო გამყოფი მრავლობითია.
  • თუ (a ) და (c ) შედარებით პირველყოფილია, მაშინ ევკლიდეს ლემა ამტკიცებს, რომ თუ (c ) იყოფა (ab ), მაშინ (c ) უნდა გაიყოს (b ).
  • კერძოდ, თუ (p ) არის პრემიერ, და თუ (p mid ab ), მაშინ ან (p mid a ) ან (p mid b ).

სავარჯიშო ( PageIndex {1} label {ex: moregcd-01} )

ნებისმიერი თვითნებური დადებითი მთელი რიცხვის გათვალისწინებით (n ), დაამტკიცეთ, რომ (2n + 1 ) და (3n + 2 ) შედარებით პირველყოფილია.

სავარჯიშო ( PageIndex {2} label {ex: moregcd-02} )

გამოიყენეთ ინდუქცია იმის დასამტკიცებლად, რომ ნებისმიერი მთელი რიცხვისთვის (n geq2 ), თუ (a_1, a_2, ldots, a_n in mathbb {Z} ) და (p ) უმნიშვნელოვანესია, რომ (p mid a_1 a_2 cdots a_n ), შემდეგ (p mid a_i ) ზოგიერთისთვის (i ), სადაც (1 leq i leq n ).

სავარჯიშო ( PageIndex {3} label {ex: moregcd-03} )

დაამტკიცეთ, რომ ( sqrt {p} ) ირაციონალურია ნებისმიერი მარტივი რიცხვისთვის (p ).

სავარჯიშო ( PageIndex {4} label {ex: moregcd-04} )

დაამტკიცეთ, რომ ( sqrt [3] {2} ) არარაციონალურია.

სავარჯიშო ( PageIndex {5} label {ex: moregcd-05} )

ნებისმიერი თვითნებური პოზიტიური მთელი რიცხვის გათვალისწინებით (a ), (b ) და (c ), აჩვენეთ, რომ თუ (a mid c ), (b mid c ) და ( gcd (a, b) = 1 ), შემდეგ (ab mid c ).

შენიშვნა. ეს შედეგი ძალიან მნიშვნელოვანია. Დაიმახსოვრე!

სავარჯიშო ( PageIndex {6} label {ex: moregcd-06} )

ნებისმიერი თვითნებური პოზიტიური მთლიანი რიცხვის გათვალისწინებით (a ), (b ) და (c ), აჩვენეთ, რომ თუ შუა cd ), სადაც (d = gcd (a, b) ).

სავარჯიშო ( PageIndex {7} label {ex: moregcd-07} )

გამოიყენეთ ინდუქცია იმის დასამტკიცებლად, რომ (3 mid (2 ^ {4n} -1) ) და (5 mid (2 ^ {4n} -1) ) ნებისმიერი მთელი რიცხვისთვის (n geq1 ). გამოიყენეთ ეს შედეგები იმის დასამტკიცებლად, რომ (15 mid (2 ^ {4n} -1) ) ნებისმიერი მთელი რიცხვისთვის (n geq1 ).

სავარჯიშო ( PageIndex {8} label {ex: moregcd-08} )

დაამტკიცეთ, რომ (2 შუა F_n Leftrightarrow 3 შუა n ) ნებისმიერი დადებითი მთელი რიცხვისთვის (n ).


Უყურე ვიდეოს: Python Tutorials - Program To Find out the GCD of Two Positive Numbers (დეკემბერი 2021).