>
ѕункт 7. –озкладанн¤ чисел у ланцюгов≥ дроби.
¬изначенн¤. Ћанцюговий (чи неперервним ) дробом називаЇтьс¤ вираз виду:
ƒомовимос¤ називати числа q 1 , q 2 ,..., q n ,... - неповними частками ≥ вважаЇмо, що q 1 Î Z, а q 2 ,..., q n ,... Î N . „исла
d 1 = q 1 , d 2 †= q 1 +, d 3 †= q 1 +, ≥ т.д.
називаютьс¤ пр¤муючими дробами ланцюгового дробу a .
Ћанцюговий др≥б може бути к≥нцевим (маЇ ск≥нченне число дробових л≥н≥й ≥ неповних часток), так ≥ неск≥нченним вниз ≥ вправо. ” першому випадку др≥б Ї де¤ким рац≥ональним числом, у другому - поки незрозум≥ло чим др≥б взагал≥ Ї, але зрозум≥ло, що вс≥ його пр¤муюч≥ дроби - рац≥ональн≥ числа.
ƒомовимос¤ називати значенн¤м (чи величиною) неск≥нченного ланцюгового дробу границю неск≥нченноњ посл≥довност≥ його пр¤муючих дроб≥в:
(поки без ус¤кого доказу ≥снуванн¤ ц≥Їњ границ≥).
√лобальною метою наступних к≥лькох пункт≥в Ї доказ основноњ теореми про ланцюгов≥ дроби:
“еорема. ”с¤ке д≥йсне число може бути розкладене в ланцюговий др≥б Їдиним чином, ≥ дов≥льний к≥нцевий чи неск≥нченний ланцюговий др≥б маЇ значенн¤ де¤ке д≥йсне число.
ѕ≥сл¤ доказу ц≥Їњ теореми можна буде см≥ливо сказати, що ланцюгов≥ дроби - це ще одна форма запису д≥йсних чисел. ќднак доказ ц≥Їњ теореми розт¤гнетьс¤ надовго.
Ќехай a Î R - д≥йсне число, укладене м≥ж двома посл≥довними ц≥лими числами: а £ a < а +1. „исло а будемо називати нижн≥м ц≥лим числа a (це просто ц≥ла частина a ), а число а +1 - верхн≥м ц≥лим. ѕозначенн¤ми дл¤ нижнього ≥ верхнього ц≥лого числа a нехай будуть, в≥дпов≥дно, ë a û и é a ù .
¬≥зьмемо дов≥льне д≥йсне число a Î R , q 1 = ë a û . “од≥ a = q 1 + b 1 , 0 £ b 1 < 1, отже
, ≥
якщо, дал≥, a 1 - не ц≥ле, то знову:
q 2 = ë a 2 û , a 2 = q 2 + b 2 = q 2 +, a 3 >1,
≥
ѕродовжуючи цей процес уз¤тт¤ нижнього ц≥лих ≥ обертанн¤ дробових частин, одержимо запис дов≥льного числа a Î R у вид≥ ланцюгового дробу.
ѕриклад 1. –озкладемо в ланцюговий др≥б число a = Ö 2.
ћаЇмо q 1 = ë Ö 2 û = 1, b 1 = Ö 2 - 1, тобто a = 1 + ( Ö 2 - 1). ƒал≥,
,
q 2 = ë Ö 2 + 1 û = 2, b 2 = Ö 2 - 1,
.
ќск≥льки b 1 = b 2 , те неважко зрозум≥ти, що цей процес зациклитьс¤ ≥, ¤кщо його не зупин¤ти, те вийде неск≥нченний ланцюговий др≥б:
”с≥ неповн≥ частки в н≥й, починаючи з другоњ, р≥вн≥ двом.
ќчевидно, що ¤кщо a Î R - ≥ррац≥ональне, те описаний вище процес неск≥нченний, тому що ≥накше, у випадку зупинки цього процесу, a ви¤вилос¤ б р≥вним ск≥нченному ланцюговому дробу, тобто рац≥ональному числу. ¬иходить, що дов≥льне ≥ррац≥ональне число ¤кщо ≥ можливо, то можливо представити лише неск≥нченним ланцюговим дробом. «абудемо поки про ≥ррац≥ональн≥ числа ≥ розгл¤датимемо т≥льки рац≥ональних.
Ќехай a Î Q , a = a / b ; a , b Î Z , b > 0. ¬и¤вл¤Їтьс¤, що при цих умовах, зазначений вище процес розкладанн¤ числа в ланцюговий др≥б завжди ск≥нченний ≥ використаЇмо алгоритм ≈вкл≥да. ¬≥зьмемо числа a ≥ b , ≥ уважно подивимос¤, що вийде.
a = bq 1 + r 1, тобто ,
b = r 1 q 2 + r 2, тобто ,
r 1 = r 2 q 3 + r 3, тобто ,
††††† .†† .†† .†† .†† .†† .†† .†† .†† .†† .†† .
r n -2 = r n -1 q n + r n , тобто ,
r n -1 = r n q n +1, тобто .
«начить:
де q 1 , q 2 ,..., q n +1 - саме т≥ неповн≥ частки з алгоритму ≈вкл≥да. “аким чином, у випадку рац≥онального числа a / b , процес розкладанн¤ в ланцюговий др≥б ск≥нченний ≥ др≥б м≥стить не б≥льше b поверх≥в. ¬ цьому м≥сц≥ основна теорема про ланцюгов≥ дроби дл¤ рац≥ональних чисел ви¤вилас¤ майже доведеною (не довели тише одиничн≥сть розкладанн¤, проте це у випадку ск≥нченних ланцюгових дроб≥в майже очевидне, ¤кщо прир≥вн¤ти два ланцюгов≥ дроби. “од≥, м≥ркуючи по ≥ндукц≥њ, одержимо, що в р≥вних дроб≥в зб≥гаютьс¤ вс≥ неповн≥ частки).
√оризонтальн≥ дробов≥ л≥н≥њ в накресленн≥ ланцюгового дробу сильно нагадують малюнок 3 з пункту 4 - в≥др≥зки, що малювали древн≥ греки на п≥ску, та й зв'¤зок алгоритму ≈вкл≥да з ланцюговими дробами безпосередн¤.
ѕриклад 2. ÷ей приклад запозичений з книги ≤.ћ. ¬иноградова "ќснови теор≥њ чисел", адже придумати самому таке дике рац≥ональне число практично неможливо. ќтже: розкласти 105/38 у ланцюговий др≥б.
¬ключаЇмо алгоритм ≈вкл≥да:
105 = 38 Ј 2+ 29
38 = 29 Ј 1+ 9
29 = 9 Ј 3+ 2
9 = 2 Ј 4+ 1
2 = 1 Ј 2
Ќеповн≥ частки п≥дкреслено тому, що тепер дл¤ написанн¤ в≥дпов≥д≥ потр≥бно акуратно розташувати њх посл≥довно на поверхах ланцюгового дробу перед знаками плюс: