ѕункт 3. ¬заЇмно прост≥ числа.
¬изначенн¤. ÷≥л≥ числа a ≥ b називаютьс¤ взаЇмно простими, ¤кщо ( a , b ) = 1.
«гадуючи властив≥сть 1 з попереднього пункту, легко пом≥тити, що два числа a ≥ b Ї взаЇмно простими тод≥ ≥ т≥льки тод≥, коли знайдутьс¤ ц≥л≥ числа u ≥ v так≥, що au + bv = 1.
«давалос¤ б, що особливого можна сказати про взаЇмно прост≥ числа? Ќу немаЇ в них сп≥льних д≥льник≥в, в≥дм≥нних в≥д 1 ≥ -1, ≥ все. ќднак, задамос¤ питанн¤м: "як часто зустр≥чаютьс¤ пари взаЇмно простих чисел?", ≥ постараЇмос¤ в≥дпов≥сти на нього у терм≥нах теор≥њ ≥мов≥рностей.
Ќехай X = { x n | n = 1, 2,...} - дов≥льна строго зростаюча посл≥довн≥сть натуральних чисел (або X - дов≥льна п≥дмножина натуральних чисел, упор¤дкована звичайним чином). ѕозначимо через x ( N ; X ) число член≥в посл≥довност≥ X , що не перевищують N.
¬изначенн¤. „исло
називаЇтьс¤ (верхньою асимптотичною) густиною посл≥довност≥ X = { x n | n = 1, 2,...} у множин≥ N.
ѕриклад 1. Ќехай xn = 2 n , де n належить N, - посл≥довн≥сть ус≥х парних чисел. ќчевидно, що
ћ≥ж ≥ншим, це добре узгоджуЇтьс¤ з нашими ≥нтуњтивними представленн¤ми про те, що парних чисел - половина.
ѕриклад 2. Ќехай xn=2n, де n належить N, - геометрична прогрес≥¤. ≤нтуњтивно ¤сно, що таких чисел у натуральному р¤д≥ мало, тому що чим дал≥ в натуральному р¤д≥, тим р≥дше зустр≥чаЇтьс¤ ступ≥нь дв≥йки. ѕон¤тт¤ густини п≥дтверджуЇ це в≥дчутт¤: x (2k ; { xn }) = k , ≥, легко перев≥рити, що
–езонно вважати, що густина - це ≥мов≥рн≥сть навманн¤ вит¤гти з натурального р¤ду число, що належить задан≥й посл≥довност≥. (ѕогодьтес¤, що ви завжди так ≥ думали. ≤мов≥рн≥сть д≥стати парне число Ї 1/2, а ≥мов≥рн≥сть напоротис¤ на ступ≥нь дв≥йки, особливо серед великих чисел, узагал≥ говор¤чи, м≥зерно мала).
јналог≥чно визначенню густини посл≥довност≥, можна дати визначенн¤ густини множини пар натуральних чисел. Ќехай маЇтьс¤ дов≥льна множина ’ упор¤дкованих пар натуральних чисел. ѕозначимо через x ( N ; X ) число пар з множини ’ , кожна компонента ¤ких не перевищуЇ N. орисно у¤вити соб≥ пари чисел з множини ’ ¤к координати точок на координатн≥й площин≥, тод≥ x ( N ; X ) Ї числом точок множини ’, що потрапили в квадрат {( x , y ) | 0 < x £ N ; 0 < y £ N }.
¬изначенн¤. „исло
називаЇтьс¤ (верхньою асимптотичною) густиною множини пар ’ в множин≥ N2.
ѕриклад 3. Ќехай ’ - множина ус≥х пар натуральних чисел, у ¤ких перший компонент строго б≥льший за другий. ћножин≥ ’ в≥дпов≥дають точки першоњ чверт≥ координатноњ площини, що лежать п≥д б≥сектрисою y = x . √устина такоњ множини становить:
що, узгоджуЇтьс¤ з нашим ≥нтуњтивним представленн¤м про те, що упор¤дкованих пар, у ¤ких перший компонент перевершуЇ другу приблизно половина в≥д загальноњ к≥лькост≥ вс≥х пар натуральних чисел.
Ќехай X - множина вс≥х упор¤дкованих пар ( u , v ) натуральних чисел таких, що ( u, v ) = 1, тобто множина ус≥х пар взаЇмно простих чисел. ¬≥дпов≥дь на питанн¤ про частоту по¤ви пари взаЇмно простих чисел даЇ теорема, в≥дкрита в 1881 роц≥ ≥тал≥йцем Ё.„езаро.
“еорема („езаро). ≤мов≥рн≥сть вибрати з N пар взаЇмно простих чисел дор≥внюЇ 6/ p 2 , точн≥ше
“аким чином, густина взаЇмно простих чисел у множин≥ N2 ви¤вл¤Їтьс¤ ≥снуЇ ≥ дор≥внюЇ 6/ p 2 ї 0, 607... ѕриблизно в 60% випадк≥в ви вит¤гнете з натурального р¤ду пари взаЇмно простих. ≤ ще дивно - у теорем≥ „езаро виникло число p , загадкове ≥ всюдисуще!
ƒоказ. —трогий доказ теореми „езаро досить складний ≥ гром≥здкий. Ќаведемо зам≥сть строгого доказу де¤к≥ евристичн≥ м≥ркуванн¤, що мають переконують в тому, що ц¤ теорема Ї правдопод≥бною.
«абудемо, що ≥снуванн¤ ≥мов≥рност≥ (верхньоњ меж≥) потр≥бно коп≥тко доводити. ѕрипустимо в≥дразу, що ≥снуЇ ≥мов≥рн≥сть p того, що випадково обран≥ натуральн≥ числа а ≥ b взаЇмно прост≥.
Ќехай
d Î N . „ерез P { S } позначимо ≥мов≥рн≥сть под≥њ S . ћ≥ркуЇмо: – {( a , b )
= d } = P{d | a}}
P{d | b} P
ѕросумувавши ц≥ ≥мов≥рност≥ по вс≥х можливих значенн¤х d , ми повинн≥ одержати одиницю:
†††
а сума р¤ду 
в≥дома ≥ дор≥внюЇ p 2/6 (див., напр., зб≥рник задач ƒемидовича з матанал≥зу, розд≥л "–¤ди ‘ур'Ї"). ќтже,
1=
отже, p = 6/ p 2 .
ѕункт 4. јлгоритм ≈вкл≥да.
—лово "алгоритм" Ї рос≥йською транскрипц≥Їю латин≥зованого ≥мен≥ видатного арабського математика ал-’орезми јбу јбдули ћухаммеда ≥бн ал-ћаджус≥ (787 - 850) ≥ означаЇ в сучасному смисл≥ де¤к≥ правила, список ≥нструкц≥й чи команд, виконуючи ¤к≥, хтось дос¤гне необх≥дного результату. јлгоритм, що дозвол¤Ї за заданими натуральними числами a ≥ b знаходити њхн≥й найб≥льший сп≥льний д≥льник, вважаЇтьс¤ придумав самий впливовий математик ус≥х час≥в ≥ народ≥в - ≈вкл≥д, в≥н викладений у IX книз≥ його знаменитих "ѕочатк≥в".
¬≥дступ "ѕанег≥рик ≈вкл≥ду"
ѕро житт¤ ≈вкл≥да ми не маЇмо н≥¤ких достов≥рних зведень, можливо, що в≥н не був реальною ≥сторичною особист≥стю, а був колективним псевдон≥мом де¤коњ групи ќлександр≥йських математик≥в, типу Ќ≥кол¤ Ѕурбаки. якщо в≥н жив, то в≥н жив за час≥в ѕтолеме¤ ѕершого (306 - 283), ¤кому, в≥дпов≥дно до переказу, в≥н сказав "ƒо геометр≥њ немаЇ царськоњ дороги". јле ѕтолемењ св≥домо культивували науку ≥ культуру в ќлександр≥њ, тому не звертали уваги на так≥ слова своњх учених.
Ќайб≥льш знаменитий тв≥р ≈вкл≥да - тринадц¤ть книг його "Ќачал", але Ї ще й ≥нш≥ др≥бн≥ опуси. ћи не знаЇмо, ¤ка частина цих праць належить самому ≈вкл≥ду ≥ ¤к≥ частини складають комп≥л¤ц≥њ, але в цих прац¤х ви¤вл¤Їтьс¤ разюча прониклив≥сть ≥ далекогл¤дн≥сть. ÷е перш≥ математичн≥ прац≥, що д≥йшли до нас в≥д древн≥х грек≥в ц≥лком. ¬ ≥стор≥њ «ах≥дного св≥ту "Ќачала", п≥сл¤ Ѕ≥бл≥њ, - книга, що найб≥льше число раз видана ≥ найб≥льш вивчена. ¬елика частина нашоњ шк≥льноњ геометр≥њ запозичена буквально з перших шести книг "Ќачал", традиц≥¤ ≈вкл≥да дотепер т¤ж≥Ї над нашим елементарним навчанн¤м. ƒл¤ профес≥йного математика ц≥ книги усе ще мають непереборне зачаруванн¤, а њх лог≥чна дедуктивна побудова вплинула на сам спос≥б наукового мисленн¤ б≥льше, н≥ж ≥нший здобуток.
ѕанег≥рик к≥нчений.
Ќехай дан≥ два числа a ≥ b ; a ³ 0, b ³ 0, вважаЇмо, що a > b . —имволом := у запис≥ алгоритму позначаЇмо присвоюванн¤. јлгоритм:
1. ¬вести a ≥ b .
2. якщо b = 0 , то ¬≥дпов≥дь: а . ≥нець .
3. «ам≥нити r := "залишок в≥д д≥ленн¤ а на b ", а := b , b := r .
4. …ти на 2.
|
рис.3. |
як ≥ чому виконанн¤ цього коротенького набору ≥нструкц≥й приводить до знаходженн¤ найб≥льшого сп≥льного д≥льника ми з'¤суЇмо трохи п≥зн≥ше, зараз же хочетьс¤ сказати к≥лька сл≥в про сам алгоритм. ѕокрокове виконанн¤ алгоритму ≈вкл≥да переконують у його простот≥ без строкатост≥. ѕро≥люструЇмо роботу алгоритму на грецький лад мал. 3:
” сучасному буквеному запис≥, що кочуЇ з одного п≥дручника в ≥нш≥й, алгоритм ≈вкл≥да вигл¤даЇ так: a > b; a, b Î Z .
|
a = bq 1 + r 1 |
0 £ r 1 < b |
† |
|
Ј Ј Ј Ј Ј Ј Ј Ј Ј |
|
|
|
r n -3 = r n -2 q n -1 + r n -1 |
0 £ r n -1 < r n -2 |
|
ћаЇмо: b > r 1 > r 2 >... > r n > 0, отже процес об≥рветьс¤ максимум через b крок≥в. ƒуже ц≥кавий ≥ практично важливе питанн¤ в тому, коли алгоритм ≈вкл≥да працюЇ особливо довго, а коли швидко, ми розгл¤немо трохи п≥зн≥ше. ѕокажемо зараз, що r n = ( a , b ). ѕерегл¤немо посл≥довно р≥вност≥ зверху вниз: ус¤кий д≥льник а ≥ b д≥литьс¤ на r1 , r2 ,..., rn . якщо ж перегл¤дати цей ланцюжок р≥вностей в≥д останнього до першого, то видно, що rn | rn -1 , rn | rn -2 , ≥ т.д., тобто rn д≥литьс¤ на а ≥ b . “ому rn - найб≥льший сп≥льний д≥льник чисел а ≥ b .
« його розгл¤ду алгоритму ≈вкл≥да зрозум≥ло, що сукупн≥сть д≥льник≥в а ≥ b зб≥гаЇтьс¤ ≥з сукупн≥стю д≥льник≥в ( a , b ). ўе в≥н даЇ практичний спос≥б одержанн¤ чисел u ≥ v з Z (чи, ¤кщо завгодно, з теореми пункту 2) таких, що r n = au + bv = ( a, b ).
ƒ≥йсно, з ланцюжка р≥вностей маЇмо:
r n = r n -2 - r n -1 q n = r n -2 - ( r n -3 - r n -2 q n -1 ) q n = ...
(йдемо по ланцюжку р≥вностей знизу нагору, виражаючи з кожноњ наступноњ р≥вност≥ залишок ≥ п≥дставл¤ючи його у вираз, що одержаний вже до цього моменту)
... = au + bv = ( a , b ).
ѕриклад. Ќехай а = 525, b = 231. ¬≥ддамо ц≥ числа на розтерзанн¤ алгоритму ≈вкл≥да: (нижче приводитьс¤ запис д≥ленн¤ куточком, ≥ †кожен раз те, що було в куточку, а саме д≥льник, дописуЇтьс¤ до залишку д≥ленн¤ з л≥воњ сторони, а залишок, ¤к новий д≥льник, беретьс¤ в куточок)
|
|
|
_ |
525| |
231 |
«апис того самого у вигл¤д≥ ланцюжка р≥вностей:
525 = 231 Ј 2 + 63 231 = 63 Ј 3 + 42 63 = 42 Ј 1 + 21 42 = 21 Ј 2
“аким чином, (525, 231) = 21. Ћ≥н≥йне представленн¤ найб≥льшого сп≥льного д≥льника:
21 = 63 - 42 Ј 1 = 63 - (231 - 63 Ј 3) Ј 1 = 525 - 231 Ј 2 - (231 - (525 - 231 Ј 2) Ј 3) = 525 Ј 4 - 231 Ј 9,
≥ наш≥ горезв≥сн≥ u ≥ v з Z р≥вн≥, в≥дпов≥дно, 4 ≥ - 9.
