\input style \chapter{ГЮЛЕВЮМХЪ НА СОПЮФМЕМХЪУ} Сопюфмемхъ, онлеыеммше б ймхцюу мюярнъыеи яепхх, опедмюгмювемш йюй дкъ яюлнярнърекэмни опнпюанрйх, рюй х дкъ яелхмюпяйху гюмърхи. Рпсдмн, еякх ме мебнглнфмн хгсвхрэ опедлер, рнкэйн вхрюъ ренпхч х ме опхлемъъ онксвеммсч хмтнплюжхч дкъ пеьемхъ яоежхюкэмшу гюдюв х рел яюлшл ме гюярюбкъъ яеаъ надслшбюрэ рн, врн ашкн опнвхрюмн. Йпнле рнцн, лш ксвье бяецн гюсвхбюел рн, врн яюлх нрйпшбюел дкъ яеаъ. Онщрнлс сопюфмемхъ напюгсчр бюфмсч вюярэ дюммни пюанрш; ашкх опедопхмърш нопедекеммше оношрйх, врнаш нрнапюрэ сопюфмемхъ, б йнрнпшу аш яндепфюкняэ йюй лнфмн анкэье хмтнплюжхх х йнрнпше ашкн аш хмрепеямн пеьюрэ. Бн лмнцху ймхцюу кецйхе сопюфмемхъ дючряъ боепелеьйс я хяйкчвхрекэмн рпсдмшлх. Гювюярсч щрн нвемэ месднамн, рюй йюй оепед рел, йюй опхярсоюрэ й пеьемхч гюдювх, вхрюрекэ наъгюрекэмн днкфем опедярюбкърэ яеае, яйнкэйн бпелемх сидер с мецн мю щрн пеьемхе (хмюве нм лнфер пюгбе рнкэйн опнялнрперэ бяе гюдювх). Йкюяяхвеяйхл опхлепнл гдеяэ ъбкъеряъ ймхцю Пхвюпдю Аекклюмю "Дхмюлхвеяйне опнцпюллхпнбюмхе"; щрн бюфмюъ охнмепяйюъ пюанрю, б йнрнпни б йнмже йюфдни цкюбш онд псапхйни "Сопюфмемхъ х хяякеднбюрекэяйхе опнакелш" дюеряъ жекши пъд гюдюв, цде мюпъдс я цксанйхлх еые мепеьеммшлх опнакелюлх бярпевючряъ хяйкчвхрекэмн рпхбхюкэмше бнопняш. Цнбнпър, врн ндмюфдш йрн-рн яопняхк д-пю Аекклюмю, йюй нркхвхрэ сопюфмемхъ нр хяякеднбюрекэяйху опнакел, х рнр нрберхк: "Еякх бш лнфере пеьхрэ гюдювс, щрн---сопюфмемхе; б опнрхбмнл яксвюе щрн---опнакелю". Лнфмн опхбеярх лмнцн днбнднб б онкэгс рнцн, врн б ймхце рхою щрни днкфмш ашрэ йюй хяякеднбюрекэяйхе опнакелш, рюй х нвемэ опнярше сопюфмемхъ, х дкъ рнцн врнаш вхрюрекч ме опхундхкняэ кнлюрэ цнкнбс мюд рел, йюйюъ гюдювю кецйюъ, ю йюйюъ рпсдмюъ, лш ббекх "нжемйх", йнрнпше сйюгшбючр яреоемэ рпсдмнярх йюфднцн сопюфмемхъ. Щрх нжемйх хлечр якедсчыее гмювемхе: \descrtable{ \bf Нжемйю & \bf На╝ъямемхе \cr 00 & Впегбшвюимн кецйне сопюфмемхе, мю йнрнпне лнфмн нрберхрэ япюгс фе, еякх онмър люрепхюк рейярю, х йнрнпне онврх бяецдю лнфмн пеьхрэ "б сле".\cr %% 11 10 & Опнярюъ гюдювю, йнрнпюъ гюярюбкъер гюдслюрэяъ мюд опнвхрюммшл люрепхюкнл, мн ме опедярюбкъер мхйюйху нянашу рпсдмняреи. Мю пеьемхе рюйни гюдювх рпеасеряъ ме анкэье ндмни лхмсрш; б опнжеяяе пеьемхъ лнцср онмюднахрэяъ йюпюмдюь х аслюцю. \cr 20 & Гюдювю япедмеи рпсдмнярх, онгбнкъчыюъ опнбепхрэ, мюяйнкэйн унпньн онмър рейяр. Мю рн врнаш дюрэ хявепошбючыхи нрбер, рпеасеряъ опхлепмн 15--20~лхмср. \cr 30 & Гюдювю слепеммни рпсдмнярх х/хкх якнфмнярх, дкъ сднбкербнпхрекэмнцн пеьемхъ йнрнпни рпеасеряъ анкэье дбсу вюянб. \cr 40 & Нвемэ рпсдмюъ хкх рпсднелйюъ гюдювю, йнрнпсч, бепнърмн, якедсер бйкчвхрэ б окюм опюйрхвеяйху гюмърхи. Опедонкюцюеряъ, врн ярсдемр лнфер пеьхрэ рюйсч гюдювс, мн дкъ щрнцн елс онрпеасеряъ гмювхрекэмши нрпегнй бпелемх; гюдювю пеьюеряъ мерпхбхюкэмшл напюгнл. \cr 50 & Хяякеднбюрекэяйюъ опнакелю, йнрнпюъ (мюяйнкэйн щрн ашкн хгбеярмн юбрнпс б лнлемр мюохяюмхъ) еые ме онксвхкю сднбкербнпхрекэмнцн пеьемхъ. Еякх вхрюрекэ мюидер пеьемхе щрни гюдювх, ецн мюярнърекэмн опняър носакхйнбюрэ ецн; йпнле рнцн, юбрнп дюммни ймхцх асдер нвемэ опхгмюрекем, еякх елс яннаыюр пеьемхе, йюй лнфмн ашярпее (опх сякнбхх, врн нмн опюбхкэмн). \cr } Хмрепонкхпсъ он щрни "кнцюпхтлхвеяйни" ьйюке, лнфмн опхйхмсрэ, врн нгмювюер кчаюъ опнлефсрнвмюъ нжемйю. Мюопхлеп, нжемйю~17 цнбнпхр н рнл, врн дюммне сопюфмемхе всрэ кецве, вел сопюфмемхе япедмеи рпсдмнярх. Гюдювю я нжемйни~50, еякх нмю асдер пеьемю йюйхл-кхан вхрюрекел, б якедсчыху хгдюмхъу дюммни ймхцх лнфер хлерэ сфе нжемйс~45. Юбрнп веярмн ярюпюкяъ дюбюрэ на╝ейрхбмше нжемйх, мн рнлс, йрн янярюбкъер гюдювх, рпсдмн опедбхдерэ, мюяйнкэйн рпсдмшлх щрх гюдювх нйюфсряъ дкъ йнцн-рн дпсцнцн; й рнлс фе с йюфднцн векнбейю ясыеярбсер нопедекеммши рхо гюдюв, йнрнпше нм пеьюер ашярпее. Мюдечяэ, врн бшярюбкеммше лмни нжемйх дючр опюбхкэмне опедярюбкемхе н яреоемх рпсдмнярх гюдюв, мн б наыел ху мсфмн бняопхмхлюрэ йюй нпхемрхпнбнвмше, ю ме юаянкчрмше. Щрю ймхцю мюохяюмю дкъ вхрюрекеи яюлшу пюгмшу яреоемеи люрелюрхвеяйни ондцнрнбйх х хяйсьеммнярх, онщрнлс мейнрнпше сопюфмемхъ опедмюгмювемш рнкэйн дкъ вхрюрекеи я люрелюрхвеяйхл сйкнмнл. Еякх б йюйнл-кхан сопюфмемхх люрелюрхвеяйхе онмърхъ хкх пегскэрюрш хяонкэгсчряъ анкее ьхпнйн, вел щрн менаундхлн дкъ реу, йнцн б оепбсч нвепедэ хмрепеясер опнцпюллхпнбюмхе юкцнпхрлнб, рн оепед нжемйни рюйнцн сопюфмемхъ ярюбхряъ асйбю "\emph{Л}". Еякх дкъ пеьемхъ сопюфмемхъ рпеасеряъ гмюмхе бшяьеи люрелюрхйх б анкэьел на╝еле, вел щрн дюмн б мюярнъыеи %% 12 ймхце, рн ярюбъряъ асйбш~"\emph{БЛ}". Онлерйю~"\emph{БЛ}" нрмчдэ ме ъбкъеряъ ябхдерекэярбнл рнцн, врн дюммне сопюфмемхе рпсдмне. Оепед мейнрнпшлх сопюфмемхълх ярнхр ярпекйю~"$\btr$"; щрн нгмювюер, врн дюммне сопюфмемхе нянаеммн онсвхрекэмн х ецн пейнлемдсеряъ наъгюрекэмн бшонкмхрэ. Яюлн янани пюгслееряъ, мхйрн ме нфхдюер, врн вхрюрекэ (хкх ярсдемр) асдер пеьюрэ бяе гюдювх, онрнлс-рн мюханкее онкегмше хг мху х бшдекемш. Щрн янбяел ме гмювхр, врн дпсцхе гюдювх ме ярнхр пеьюрэ! Йюфдши вхрюрекэ днкфем он йпюимеи лепе оношрюрэяъ пеьхрэ бяе гюдювх я нжемйни~10 х мхфе; ярпекйх фе онлнцср бшапюрэ, йюйхе гюдювх я анкее бшянйхлх нжемйюлх якедсер пеьхрэ б оепбсч нвепедэ. Й анкэьхмярбс сопюфмемхи опхбедемш нрберш; нмх онлеыемш б яоежхюкэмнл пюгдеке б йнмже ймхцх. Онкэгсиреяэ хлх лсдпн; б нрбер ялнрпхре рнкэйн оняке рнцн, йюй бш опхкнфхкх днярюрнвмн сяхкхи, врнаш пеьхрэ гюдювс яюлнярнърекэмн, хкх фе еякх дкъ пеьемхъ дюммни гюдювх с бюя мер бпелемх. Еякх онксвем янаярбеммши нрбер, кхан еякх бш деиярбхрекэмн ошрюкхяэ пеьхрэ гюдювс, рнкэйн б щрнл яксвюе нрбер, онлеыеммши б ймхце, асдер онсвхрекэмшл х онкегмшл. Йюй опюбхкн, нрберш й гюдювюл хгкюцючряъ нвемэ йпюрйн, яуелюрхвмн, рюй йюй опедонкюцюеряъ, врн вхрюрекэ сфе веярмн ошрюкяъ пеьхрэ гюдювс янаярбеммшлх яхкюлх. Хмнцдю б опхбедеммнл пеьемхх дюеряъ лемэье хмтнплюжхх, вел яопюьхбюкняэ, вюые---мюнанпнр. Бонкме бнглнфмн, врн онксвеммши бюлх нрбер нйюферяъ ксвье нрберю, онлеыеммнцн б ймхце, хкх бш мюидере ньхайс б щрнл нрбере; б рюйнл яксвюе юбрнп ашк аш нвемэ наъгюм, еякх аш бш йюй лнфмн яйнпее ондпнамн яннаыхкх елс на щрнл. Б онякедсчыху хгдюмхъу мюярнъыеи ймхцх асдер онлеыемн сфе хяопюбкеммне пеьемхе блеяре я хлемел ецн юбрнпю. \bigskip \centerline{\bf Ябндйю сякнбмшу нангмювемхи} \ctable{ \emph{#}\bskip\hfil&\bskip#\hfil\cr $\btr$ & Пейнлемдсеряъ \cr Л & Я люрелюрхвеяйхл сйкнмнл \cr БЛ & Рпеасер гмюмхъ "бшяьеи люрелюрхйх" \cr 00 & Рпеасер меледкеммнцн нрберю \cr 10 & Опнярне (мю ндмс лхмсрс) \cr 20 & Япедмеи рпсдмнярх (мю вербепрэ вюяю) \cr 30 & Онбшьеммни рпсдмнярх \cr 40 & Дкъ "люропюйрхйслю" \cr 50 & Хяякеднбюрекэяйюъ опнакелю \cr } \excercises \ex[00] Врн нгмювюер онлерйю~"\emph{Л20}"? \ex[10] Йюйне гмювемхе дкъ вхрюрекъ хлечр сопюфмемхъ, онлеыюелше б свеамхйюу? \ex[Л50] Днйюфхре, врн еякх~$n$---жекне вхякн, $n>2$, рн спюбмемхе~$x^n+y^n=z^n$ мепюгпеьхлн б жекшу онкнфхрекэмшу вхякюу~$x$, $y$, $z$. %% 13 \chapno=2\chapnotrue\chapter{Яксвюимше вхякю} % 3 \epigraph Бяъйхи, йрн охрюер якюанярэ й юпхтлерхвеяйхл лерндюл онксвемхъ яксвюимшу вхяек, цпеьем бме бяъйху янлмемхи. \signed Дфнм тнм Меилюм (1951) \epigraph Йпсцкше вхякю бяецдю тюкэьхбш. \signed Ящлчщкэ Дфнмянм (нйнкн 1750) \epigraph Lest men suspect your tale untrue, \goodbreak Keep probability in view% \note{1}% {Врнаш кчдх онбепхкх бюьхл пняяйюгмъл, онлмхре н бепнърмнярх.---{\sl Опхл. оепеб.\/} }. \signed Дфнм Цщи (1727) \subchap{ББЕДЕМХЕ} % 3.1 "Яксвюимн бшапюммше" вхякю нйюгшбючряъ онкегмшлх дкъ яюлшу пюгкхвмшу жекеи. Бнр мейнрнпше опхлепш: \medskip a)~\emph{Лндекхпнбюмхе.} Йнцдю я онлныэч бшвхякхрекэмни люьхмш лндекхпсчряъ опхпндмше ъбкемхъ, яксвюимше вхякю онгбнкъчр опхакхгхрэ лндекэ й пеюкэмнярх. Лндекхпнбюмхе опхлемъеряъ бн лмнцху накюяръу: нр ъдепмни тхгхйх (вюярхжш хяошршбючр яксвюимше янсдюпемхъ) дн яхярелмнцн юмюкхгю (яйюфел, кчдх бундър б аюмй вепег яксвюимше хмрепбюкш бпелемх). b)~\emph{Бшанпйю.} Вюярн ашбюер, врн опнбепйю бяеу бнглнфмшу бюпхюмрнб опюйрхвеяйх менясыеярбхлю. Рнцдю мю мейнрнпше бнопняш онгбнкъер онксвхрэ нрберш яксвюимюъ бшанпйю. c)~\emph{Вхякеммши юмюкхг.} Дкъ пеьемхъ якнфмшу гюдюв бшвхякхрекэмни люрелюрхйх ашкю пюгпюанрюмю нярпнслмюъ реумхйю, хяонкэгсчыюъ яксвюимше вхякю. На щрнл мюохяюм пъд ймхц. d)~\emph{Опнцпюллхпнбюмхе дкъ бшвхякхрекэмшу люьхм.} Яксвюимше гмювемхъ яксфюр унпньхл хярнвмхйнл дюммшу опх хяошрюмхх щттейрхбмнярх пюгкхвмшу юкцнпхрлнб дкъ бшвхякхрекэмшу люьхм. Б щрни ймхце мюя асдер б нямнбмнл хмрепеянбюрэ хлеммн рюйне хяонкэгнбюмхе яксвюимшу вхяек. Онщрнлс опефде вел онидер певэ н дпсцху юкцнпхрлюу, гдеяэ, б рперэеи цкюбе, асдср пюяялнрпемш яксвюимше вхякю. e)~\emph{Опхмърхе пеьемхи.} Цнбнпър, врн лмнцхе псйнбндхрекх опхмхлючр пеьемхъ, апняюъ лнмерйс хкх йнярх. Ундър дюфе %% 14 яксух, врн мейнрнпше опнтеяянпю б йнккедфюу днахбючряъ сяоеую хлеммн рюйхл напюгнл. Хмнцдю ашбюер бюфмн опхмхлюрэ янбепьеммн меопедбгърше пеьемхъ. Онкегмн опедсялнрперэ рюйсч бнглнфмнярэ дкъ юкцнпхрлнб, опхлемъелшу б бшвхякхрекэмшу люьхмюу, мюопхлеп б яксвюъу, йнцдю опхмърхе дереплхмхпнбюммнцн пеьемхъ лнфер опхбеярх й гюледкемхч яверю. Яксвюимнярэ, йпнле рнцн,---ясыеярбеммюъ вюярэ норхлюкэмшу ярпюрецхи б ренпхх хцп. f)~\emph{Пюгбкевемхъ.} Лмнцхе опнбндър бпелъ, рюясъ йюпрш, апняюъ йнярх хкх мюакчдюъ гю йнкеянл пскерйх, х мюундър б щрнл мехг╝ъямхлне сднбнкэярбхе. Рюйхл рпюдхжхнммшл хяонкэгнбюмхел яксвюимшу вхяек на╝ъямъеряъ, онвелс реплхм "Лнмре-Йюпкн" яксфхр наыхл мюхлемнбюмхел дкъ бяеу юкцнпхрлнб, б йнрнпшу опхлемъчр яксвюимше вхякю. \medskip Ярюкн нашвмшл б щрнл леяре онябъыюрэ меяйнкэйн юагюжеб тхкнянтяйнлс наясфдемхч рнцн, врн фе рюйне "яксвюимнярэ". Б мейнрнпнл ялшяке рюйнцн на╝ейрю, йюй яксвюимне вхякн, опнярн мер. Яйюфел, дбнийю---щрн яксвюимне вхякн? Яйнпее лш цнбнпхл н \emph{онякеднбюрекэмнярх мегюбхяхлшу} яксвюимшу вхяек я нопедекеммшл \emph{гюйнмнл пюяопедекемхъ,} х щрн нгмювюер, цпсан цнбнпъ, врн йюфдне вхякн ашкн онксвемн яюлшл опнхгбнкэмшл напюгнл, аег бяъйни ябъгх я дпсцхлх вкемюлх онякеднбюрекэмнярх, х врн с мецн еярэ нопедекеммюъ бепнърмнярэ нйюгюрэяъ б кчанл гюдюммнл хмрепбюке. \dfn{Пюбмнлепмшл} мюгшбюеряъ рюйне пюяопедекемхе, опх йнрнпнл йюфдне бнглнфмне вхякн пюбмнбепнърмн. Нашвмн, еякх яоежхюкэмн ме нцнбнпемн врн-кхан хмне, хлечр б бхдс пюбмнлепмше пюяопедекемхъ. Йюфдюъ хг деяърх жхтп нр~$0$ дн~$9$ янярюбкъер опхлепмн ндмс деяърсч вюярэ бяеу жхтп бн бяъйни яксвюимни (пюбмнлепмни) онякеднбюрекэмнярх жхтп. Кчаюъ гюдюммюъ оюпю дбсу яняедмху жхтп днкфмю янярюбкърэ опхлепмн $\frac1/{100}$~вюярэ бяеу оюп, бярпевючыхуяъ б онякеднбюрекэмнярх, х~р.~д. Рел ме лемее, еякх лш пюяялнрпхл йюйсч-мхасдэ йнмйпермсч яксвюимсч онякеднбюрекэмнярэ хг лхккхнмю жхтп, б меи янбяел ме наъгюрекэмн нйюферяъ пнбмн $100\,000$~мскеи, $100\,000$~едхмхж х~р.~д. Б деиярбхрекэмнярх бепнърмнярэ рюйнцн янашрхъ нвемэ люкю. Гюйнмнлепмнярэ фе бшонкмъеряъ б япедмел дкъ \emph{онякеднбюрекэмнярх} рюйху онякеднбюрекэмняреи. Кчаюъ гюдюммюъ онякеднбюрекэмнярэ ярнкэ фе бепнърмю, йюй х онякеднбюрекэмнярэ, янярнъыюъ хг ндмху \emph{мскеи.} Анкее рнцн, дносярхл, врн лш бшахпюел яксвюимшл напюгнл онякеднбюрекэмнярэ хг лхккхнмю жхтп. Осярэ нйюгюкняэ, врн оепбше $999\,999$ %% 15 хг мху пюбмш мскч. Х б щрнл яксвюе бепнърмнярэ рнцн, врн онякедмъъ жхтпю асдер мскел, бяе еые б рнвмнярх пюбмю~$\frac 1/{10}$, еякх бшанпйю деиярбхрекэмн яксвюимюъ. Дкъ лмнцху щрх србепфдемхъ гбсвюр йюй оюпюднйя, мн мю яюлнл деке б мху мер опнрхбнпевхъ. Ясыеярбсер меяйнкэйн яонянанб ятнплскхпнбюрэ унпньее юаярпюйрмне нопедекемхе яксвюимни онякеднбюрекэмнярх. Лш еые бепмеляъ й щрнлс хмрепеямнлс бнопняс б~\S~3.5. Онйю фе днярюрнвмн хмрсхрхбмн онмърэ хдеч. Пюмэье свемше, мсфдюбьхеяъ дкъ ябнеи пюанрш б яксвюимшу вхякюу, пюяйкюдшбюкх йюпрш, апняюкх йнярх хкх бшрюяйхбюкх ьюпш хг спмш, йнрнпсч опедбюпхрекэмн "йюй якедсер рпъякх". Б 1927~ц.\ К.~Рхооерр носакхйнбюк рюакхжш, яндепфюыхе ябшье $40\,000$~яксвюимшу жхтп, "опнхгбнкэмн бгършу хг нрвернб н оепеохях". Онгфе ашкх яйнмярпсхпнбюмш яоежхюкэмше люьхмш, леуюмхвеяйх бшпюаюршбючыхе яксвюимше вхякю. Оепбсч рюйсч люьхмс б 1939~ц.\ хяонкэгнбюкх Л.~Дф.~Йемдюкк х~А.~Ащахмцрнм-Ялхр опх янгдюмхх рюакхж, бйкчвючыху 100~ршяъв яксвюимшу жхтп. Б 1955~ц.\ йнлоюмхъ RAND Corporation носакхйнбюкю унпньн хгбеярмше рюакхжш я лхккхнмнл яксвюимшу жхтп, онксвеммшу дпсцни рюйни люьхмни. Хгбеярмюъ люьхмю ERNIE, бшпюаюршбючыюъ яксвюимше вхякю, нопедекъер бшхцпюбьхе мнлепю б Апхрюмяйни кнрепее. [Ял.\ ярюрэх Йемдюккю х Ащахмцрнм-Ялхрю б {\sl Journal of the Royal Statistical Society,\/} Series~A, {\bf 101} (1938), 147--166, х Series~Б, {\bf 6} (1939), 51--61, ю рюйфе нагнп б~{\sl Math.\ Comp.,\/} {\bf 10} (1956), 39--43.] Бяйнпе оняке янгдюмхъ бшвхякхрекэмшу люьхм мювюкхяэ онхяйх щттейрхбмшу лернднб онксвемхъ яксвюимшу вхяек, опхцндмшу дкъ хяонкэгнбюмхъ б опнцпюллюу. Б опхмжхое лнфмн пюанрюрэ х я рюакхжюлх, ндмюйн, щрнр лернд хлеер нцпюмхвемхъ, ябъгюммше я йнмевмшл на╝елнл оюлърх люьхм х гюрпюрюлх бпелемх дкъ ббндю вхяек б люьхмс б рнл яксвюе, йнцдю рюакхжю нйюгшбюеряъ якхьйнл йнпнрйни. Йпнле рнцн, днбнкэмн меопхърмн цнрнбхрэ рюакхжш гюпюмее, дю х бннаые хлерэ я мхлх декн. Лнфмн опхянедхмхрэ й ЩБЛ люьхмс рхою ERNIE, мн х щрнр осрэ нйюгшбюеряъ месднбкербнпхрекэмшл, онрнлс врн опх нркюдйе опнцпюллш мебнглнфмн бняопнхгбеярх брнпхвмн бшвхякемхъ, ядекюммше пюмее. Меянбепьемярбн бяеу щрху лернднб опнасдхкн хмрепея й онксвемхч яксвюимшу вхяек я онлныэч юпхтлерхвеяйху ноепюжхи бшвхякхрекэмни люьхмш. Оепбшл рюйни ондунд б 1946~ц.\ опедкнфхк Дфнм тнм Меилюм, хяонкэгнбюбьхи лернд "яепедхмш йбюдпюрю". Хдеъ гюйкчвюеряъ б рнл, врн опедшдсыее яксвюимне вхякн бнгбндхряъ б йбюдпюр, ю гюрел хг пегскэрюрю хгбкейючряъ япедмхе жхтпш. Осярэ, мюопхлеп, лш бшпюаюршбюел деяърхгмювмше вхякю х дносярхл, врн опедшдсыее вхякн ашкн пюбмн~$5772156649$; %% 16 бнгбедъ ецн б йбюдпюр, онксвхл $$ 33317792380594909201, $$ х онщрнлс якедсчыее вхякн пюбмн~$7923805949$. Лернд бшгшбюер днбнкэмн нвебхдмне бнгпюфемхе. Йюй лнфер ашрэ яксвюимни бшпюанрюммюъ рюйхл яонянанл онякеднбюрекэмнярэ, еякх йюфдши ее вкем онкмнярэч нопедекем ябнхл опедьеярбеммхйнл? Нрбер гюйкчвюеряъ б рнл, врн щрю онякеднбюрекэмнярэ \emph{ме} яксвюимю мн \emph{бшцкъдхр} йюй яксвюимюъ. Б рхохвмшу опхкнфемхъу нашвмн ме хлеер гмювемхъ, йюй ябъгюмш дпсц я дпсцнл дбю онякедсчыху вхякю онякеднбюрекэмнярх; рюйхл напюгнл, меяксвюимши уюпюйреп онякеднбюрекэмнярх ме ъбкъеряъ мефекюрекэмшл. Хмрсхрхбмн лернд яепедхмш йбюдпюрю днкфем днбнкэмн унпньн "оепелеьхбюрэ" опедшдсыее вхякн. Б мюсвмн-реумхвеяйни кхрепюрспе онякеднбюрекэмнярх, бшпюаюршбюелше дереплхмхяряйхлх яонянаюлх, мюгшбючряъ \emph{ояебдняксвюимшлх} хкх \emph{йбюгхяксвюимшлх.} Гдеяэ фе лш асдел мюгшбюрэ ху опнярн яксвюимшлх онякеднбюрекэмнярълх, онмхлюъ, врн нмх рнкэйн \emph{опнхгбндър боевюркемхе} яксвюимшу. Мюбепмне, бяе, врн лнфмн яйюгюрэ н яксвюимни онякеднбюрекэмнярх, щрн рн, врн нмю "он бмеьмелс бхдс яксвюимюъ". Рнвмше люрелюрхвеяйхе нопедекемхъ яксвюимнярх дючряъ б~\S~3.5. Бшпюанрюммше дереплхмхяряйхлх лерндюлх яксвюимше вхякю нйюгюкхяэ опхцндмшлх онврх дкъ бяеу опхкнфемхи (унръ, йнмевмн, нмх ме лнцср гюлемхрэ ERNIE б кнрепеъу). Ндмюйн оепбнмювюкэмши "лернд яепедхмш йбюдпюрю" тнм Меилюмю нйюгюкяъ япюбмхрекэмн яйсдмшл хярнвмхйнл яксвюимшу вхяек. Меднярюрнй ецн гюйкчвюеряъ б рнл, врн онякеднбюрекэмнярх хлечр ремдемжхч опебпюыюрэяъ б йнпнрйхе жхйкш онбрнпъчыхуяъ щкелемрнб. Мюопхлеп, еякх йюйни-мхасдэ вкем онякеднбюрекэмнярх нйюферяъ пюбмшл мскч, бяе онякедсчыхе вкемш рюйфе асдср мскълх. Б мювюке оърхдеяършу цнднб мейнрнпше свемше опнбндхкх щйяоепхлемрш я лернднл яепедхмш йбюдпюрю. Дф.~Щ.~Тнпяюир, пюанрюбьхи я вершпеугмювмшлх (ю ме я деяърхгмювмшлх) вхякюлх, опнбепхк 16~вхяек б йювеярбе мювюкэмшу гмювемхи онякеднбюрекэмняреи Нйюгюкняэ, врн~12 хг мху онпнфдюкх онякеднбюрекэмнярх, нйюмвхбючыхеяъ жхйкнл~$6100$, $2100$, $4100$, $8100$, $6100$,~\dots, ю дбе онякеднбюрекэмнярх бшпндхкхяэ б мскэ. Наьхпмше щйяоепхлемрш он хяякеднбюмхч лерндю яепедхмш йбюдпюрю опнбек М.~Лерпнонкхя, ноепхпнбюбьхи цкюбмшл напюгнл дбнхвмшлх вхякюлх. Пюанрюъ я 20-пюгпъдмшлх вхякюлх, нм онйюгюк, врн ясыеярбсер рпхмюджюрэ пюгкхвмшу жхйкнб, б йнрнпше лнцср бшпндхрэяъ онякеднбюрекэмнярх; дкхмю оепхндю яюлнцн анкэьнцн хг мху пюбмю~$142$. Йюй рнкэйн онякеднбюрекэмнярэ бшпнфдюеряъ б мскэ, днбнкэмн кецйн мювюрэ бшпюанрйс яксвюимшу вхяек гюмнбн. Цнпюгдн рпсдмеи анпнрэяъ %% 17 я дкхммшлх жхйкюлх. Бяе фе П.~Ткнид (ял.~соп.~7) опедкнфхк нярпнслмши лернд, онгбнкъчыхи гюпецхярпхпнбюрэ бнгмхймнбемхе жхйкю б онякеднбюрекэмнярх. Лернд Ткнидю рпеасер меанкэьни оюлърх люьхмш, сбекхвхбюер бпелъ бшпюанрйх яксвюимнцн вхякю бяецн б рпх пюгю х япюгс фе яхцмюкхгхпсер, йюй рнкэйн б онякеднбюрекэмнярх онъбкъеряъ бярпевюбьееяъ пюмее вхякн. Ренперхвеяйхе меднярюрйх лерндю яепедхмш йбюдпюрю наясфдючряъ б соп.~9 х~10. Я дпсцни ярнпнмш, нрлерхл, врн, пюанрюъ я 38-пюгпъдмшлх дбнхвмшлх вхякюлх, М.~Лерпнонкхя намюпсфхк онякеднбюрекэмнярэ, янярнъысч хг $750\,000$~вкемнб, нркхвючыхуяъ дпсц нр дпсцю. Ярюрхярхвеяйхе реярш ондрбепдхкх яксвюимши уюпюйреп онксвеммни онякеднбюрекэмнярх хг $750000 \times 38$~ахрнб. Щрн ондрбепфдюер, врн, опхлемъъ лернд яепедхмш йбюдпюрю, \emph{лнфмн} онксвхрэ онкегмше пегскэрюрш. Рел ме лемее аег опедбюпхрекэмшу рпсднелйху бшвхякемхи елс ме ярнхр хгкхьме днбепърэ. Лмнцхе дюрвхйх яксвюимшу вхяек, оноскъпмше яеивюя, меднярюрнвмн унпньх. Япедх онкэгнбюрекеи мюлерхкюяэ ремдемжхъ хгаецюрэ ху хгсвемхъ. Днбнкэмн вюярн йюйни-мхасдэ ярюпши япюбмхрекэмн месднбкербнпхрекэмши лернд оепедюеряъ нр ндмнцн опнцпюллхярю й дпсцнлс бякеосч, х яецндмъьмхи онкэгнбюрекэ сфе мхвецн ме гмюер на ецн меднярюрйюу. Б щрни цкюбе лш саедхляъ, врн мерпсдмн хгсвхрэ яюлше бюфмше ябниярбю дюрвхйнб яксвюимшу вхяек х мюсвхрэяъ опхлемърэ щрх гмюмхъ. Хгнапеярх опнярни дюрвхй яксвюимшу вхяек ме рюй кецйн. Меяйнкэйн кер мюгюд щрнр тюйр опнхгбек мю юбрнпю анкэьне боевюркемхе. Нм рнцдю ошрюкяъ янгдюрэ тюмрюярхвеяйх унпньхи дюрвхй яксвюимшу вхяек мю нямнбе якедсчыецн ябненапюгмнцн лерндю. \alg K.(Дюрвхй "ябепуяксвюимшу" вхяек.) Я онлныэч щрнцн юкцнпхрлю дюммне деяърхгмювмне деяърхвмне вхякн~$X$ лнфмн опенапюгнбюрэ б дпсцне вхякн, йнрнпне, йюй опедонкюцюеряъ, ъбкъеряъ якедсчыхл вкемнл яксвюимни онякеднбюрекэмнярх. Йюгюкняэ аш, юкцнпхрл онгбнкъер бшпюанрюрэ днярюрнвмн яксвюимсч онякеднбюрекэмнярэ, мн бшъямхкняэ, врн щрн янбяел ме рюй. Опхвхмш месдювх пюгахпючряъ мхфе. (Вхрюрекч мер мсфдш якхьйнл бмхйюрэ б дерюкх. Днярюрнвмн саедхрэяъ б анкэьни якнфмнярх юкцнпхрлю.) \st[Бшапюрэ вхякн хрепюжхи.] Сярюмнбхрэ~$Y\asg\floor{X/10^9}$, гюдюб ецн пюбмшл ярюпьеи жхтпе вхякю~$X$. (Лш онбрнпхл $Y+1$~пюг ьюцх я~\stp{2} он~\stp{13} бйкчвхрекэмн. Дпсцхлх якнбюлх, яксвюимне вхякн асдер бшвхякърэяъ \emph{яксвюимне} вхякн пюг.) \st[Бшапюрэ яксвюимши ьюц.] Сярюмнбхрэ~$Z\asg\floor{X/10^8}\bmod 10$, р.~е.~опхябнхрэ~$Z$ гмювемхе, пюбмне брнпни он ярюпьхмярбс жхтпе вхякю~$X$. Оепеирх й бшонкмемхч ьюцю~\stp{$(3+Z)$}. %% 18 (Дпсцхлх якнбюлх, дюкее лш бшонкмъел \emph{яксвюимн} бшапюммши ьюц опнцпюллш!) \st[Наеяоевхрэ~$X\ge 5\cdot 10^9$.] Еякх~$X<5\cdot 10^9$, рн сярюмнбхрэ~$X\asg X+5\cdot 10^9$. \st[Яепедхмю йбюдпюрю.] Гюлемхрэ~$X$ вхякнл~$\floor{X^2/10^5}\bmod 10^{10}$, р.~е.\ яепедхмни йбюдпюрю вхякю~$X$. \st[Слмнфхрэ.] Гюлемхрэ~$X$ мю~$(1001001001 X) \bmod 10^{10}$. \st[Ояебднднонкмемхе.] Еякх~$X<10^8$, рн сярюмнбхрэ~$X\asg X+9814055677$, б опнрхбмнл яксвюе~$X\asg 10^{10}-X$. \st[Оепеярюбхрэ онкнбхмйх.] Онлемърэ леярюлх $5$~ярюпьху х $5$~лкюдьху жхтп, р.~е.\ сярюмнбхрэ~$X\asg 10^5 \floor{X \bmod 10^5}+\floor{X/10^5}$, хкх, он-дпсцнлс, бгърэ япедмхе $10$~жхтп вхякю~$(10^{10}+1)X$. \st[Слмнфхрэ.] (Ял.~ьюц~\stp{5}.) \st[Слемэьхрэ жхтпш.] Слемэьхрэ мю едхмхжс йюфдсч нркхвмсч нр мскъ жхтпс вхякю~$X$ (б деяърхвмнл опедярюбкемхх). \st[Лндхтхжхпнбюрэ мю~$99999$.] Еякх~$X<10^5$, рн сярюмнбхрэ~$X\asg X^2+99999$, б опнрхбмнл яксвюе~$X\asg X-99999$. \st[Мнплюкхгнбюрэ.] (Гдеяэ~$X$ ме лнфер ашрэ пюбмшл мскч.) Еякх~$X<10^9$, рн сярюмнбхрэ~$X\asg 10X$ х онбрнпхрэ щрнр ьюц. \st[Лндхтхжхпнбюммюъ яепедхмю йбюдпюрю.] Гюлемхрэ~$X$ мю~$\floor{X(X-1)/10^5}\bmod 10^{10}$, р.~е.\ бгърэ япедмхе 10~жхтп вхякю~$X(X-1)$. \st[Онбрнпхрэ?] Еякх~$Y>0$, рн слемэьхрэ~$Y$ мю~$1$ х бепмсрэяъ мю ьюц~\stp{2}. Еякх~$Y=0$, юкцнпхрл гюбепьем, опхвел рейсыее гмювемхе~$X$ явхрюеряъ хяйнлшл яксвюимшл вхякнл. \algend (Унрекняэ мюохяюрэ мюярнкэйн якнфмсч опнцпюллс, пеюкхгсчысч нохяюммши бшье юкцнпхрл, врнаш векнбей, вхрючыхи ее рейяр, ме лнц аш аег на╝ъямемхи днцюдюрэяъ, врн фе б меи декюеряъ.) Свхршбюъ бяе лепш опеднярнпнфмнярх, опхмърше б юкцнпхрле~K, ме йюферяъ кх бонкме опюбднонднамшл, врн я ецн онлныэч лнфмн онксвхрэ аеяйнмевмне лмнфеярбн юаянкчрмн яксвюимшу вхяек? Мер! Б деиярбхрекэмнярх, йюй рнкэйн щрнр юкцнпхрл ашк пеюкхгнбюм мю ЩБЛ, онврх япюгс фе хрепюжхх янькхяэ й вхякс~$6065038420$, йнрнпне, б пегскэрюре мебепнърмнцн янбоюдемхъ, опенапюгсеряъ яюлн б яеаъ (ял.~рюак.~1). Опх дпсцнл мювюкэмнл гмювемхх онякеднбюрекэмнярэ, мювхмюъ я вкемю я мнлепнл~$7401$, онбрнпъеряъ я дкхмни оепхндю~$3178$. Лнпюкэ щрни хярнпхх гюйкчвюеряъ б рнл, врн \emph{яксвюимше вхякю мекэгъ бшпюаюршбюрэ я онлныэч яксвюимн бшапюммнцн юкцнпхрлю.} Мсфмю йюйюъ-мхасдэ ренпхъ. Б щрни цкюбе лш пюяялнрпхл лерндш бшпюанрйх яксвюимшу вхяек, опебняундъыхе лернд яепедхмш йбюдпюрю х юкцнпхрл~K б рнл нрмньемхх, врн дкъ мху лнфмн ренперхвеяйх цюпюмрхпнбюрэ %% 19 \htable{Рюакхжю~1}% {Йнкняяюкэмне янбоюдемхе: вхякн 6065038420 опенапюгсеряъ б яеаъ я онлныэч юкцнпхрлю~K}% {\strut #\bskip\hfil&\bskip$#$\hfil\bskip&\bskip$#$\hfil\bskip&\vrule\bskip#\hfil&\bskip$#$\hfil\bskip&\bskip$#$\hfil\bskip\cr Ьюц & \hbox{$X$ (б йнмже ьюцю)} \span & Ьюц & \hbox{$X$ (б йнмже ьюцю)}\span \cr K1 & 6065038420 & & K9 & 1107855700 \cr K3 & 6065038420 & & K10 & 1107755701 \cr K4 & 6910360760 & & K11 & 1107755701 \cr K5 & 8031120760 & & K12 & 1226919902 & Y=3\cr K6 & 1968879240 & & K5 & 0048821902 \cr K7 & 7924019688 & & K6 & 9862877579 \cr K8 & 9631707688 & & K7 & 7757998628 \cr K9 & 8520606577 & & K8 & 2384626628 \cr K10 & 8520506578 & & K9 & 1273515517 \cr K11 & 8520506578 & & K10 & 1273415518 \cr K12 & 0323372207 & Y=6 & K11 & 1273415518 \cr K6 & 9676627793 & & K12 & 5870802097 & Y=2\cr K7 & 2779396766 & & K11 & 5870802097 \cr K8 & 4942162766 & & K12 & 3172562687 & Y=1\cr K9 & 3831051655 & & K4 & 1540029446 \cr K10 & 3830951656 & & K5 & 7015475446 \cr K11 & 3830951656 & & K6 & 2984524554 \cr K12 & 1905867781 & Y=5 & K7 & 2455429845 \cr K12 & 3319967479 & Y=4 & K8 & 2730274845 \cr Kа & 6680032521 & & K9 & 1620163734 \cr K7 & 3252166800 & & K10 & 1620063735 \cr K8 & 2218966800 & & K11 & 1620063735 \cr & & & K12 & 6065038420 & Y=0 \cr } бшонкмемхе нопедекеммшу ябниярб яксвюимни онякеднбюрекэмнярх х нрясрярбхе бшпнфдемхъ. Асдср хгкнфемш мейнрнпше дерюкх, наеяоевхбючыхе рюйне яксвюимне онбедемхе, х сдекемн бмхлюмхе реумхйе опхлемемхъ яксвюимшу вхяек. Б вюярмнярх, мюопхлеп, асдер онйюгюмн, йюй рюянбюрэ йюпрш я онлныэч опнцпюллш дкъ~ЩБЛ. \excercises \rex[20] Опедонкнфхл, бш унрхре, ме хяонкэгсъ ЩБЛ, онксвхрэ яксвюимсч деяърхвмсч жхтпс. Йюйни хг оепевхякеммшу мхфе лернднб бш опедонврере? a)~Нрйпнире рекетнммши яопюбнвмхй б опнхгбнкэмнл леяре (р.~е.\ рймхре оюкэжел йсдю сцндмн) х бнгэлхре лкюдьсч жхтпс оепбнцн оноюбьецняъ мнлепю мю бшапюммни бюлх ярпюмхже. b)~Ядекюире рн фе яюлне, мн бняонкэгсиреяэ лкюдьеи жхтпни мнлепю \emph{ярпюмхжш.} %% 20 c)~Апняэре йнярэ б тнпле опюбхкэмнцн хйняющдпю, йюфдюъ хг дбюджюрх цпюмеи йнрнпнцн онлевемю жхтпюлх~$0$, $0$, $1$, $1$,~\dots, $9$, $9$. Гюохьхре жхтпс, йнрнпни асдер онлевемю бепумъъ цпюмэ нярюмнбхбьеияъ йнярх. (Дкъ щйяоепхлемрю пейнлемдсеряъ онкэгнбюрэяъ ярнкнл я рбепдни нахрни ясймнл онбепумнярэч.) d)~Онярюбэре мю лхмсрс пъднл я хярнвмхйнл пюдхнюйрхбмнцн хгксвемхъ явервхй Цеицепю (опхлхре лепш опеднярнпнфмнярх). Бняонкэгсиреяэ лкюдьеи жхтпни вхякю нрявернб, онйюгюммнцн явервхйнл. (Опедонкюцюеряъ, врн цеицепнбяйхи явервхй онйюгшбюер вхякн нрявернб б деяърхвмнл бхде х оепед мювюкнл щйяоепхлемрю нм ашк сярюмнбкем мю мскэ.) e)~Бгцкъмхре мю ябнх вюяш х, еякх яейсмдмюъ ярпекйю мюундхряъ лефдс вхякюлх~$6n$ х~$6(n+1)$, бшаепхре жхтпс~$n$. f)~Онопняхре опхърекъ гюдслюрэ яксвюимсч жхтпс х осярэ нм бюл ее мюгнбер. g)~Осярэ рн фе яюлне ядекюер бюь медпсц. h)~Опедонкнфхл, врн б гюаеце свюярбсер $10$~юаянкчрмн мехгбеярмшу бюл кньюдеи. Янбепьеммн опнхгбнкэмн опнмслепсире ху жхтпюлх нр~$0$ дн~$9$. Бняонкэгсиреяэ мнлепнл онаедхрекъ гюаецю. \ex[Л22] Йюйнбю бепнърмнярэ намюпсфхрэ пнбмн $100\,000$~щйгелокъпнб кчани гюдюммни гюпюмее жхтпш б яксвюимни онякеднбюрекэмнярх, янярнъыеи хг $1\,000\,000$~деяърхвмшу жхтп? \ex[10] Йюйне вхякн онксвхряъ оняке опхлемемхъ лерндю яепедхмш йбюдпюрю й вхякс~$1010101010$? \ex[10] Онвелс опх бшонкмемхх ьюцю~K11 юкцнпхрлю~K гмювемхе~$X$ ме лнфер ашрэ пюбмшл мскч? Врн опнхгнькн аш я юкцнпхрлнл, еякх аш~$У$ лнцкн ашрэ мскел? \ex[15] На╝ъямхре, онвелс б кчанл яксвюе мекэгъ нфхдюрэ онксвемхъ "аеяйнмевмнцн лмнфеярбю" яксвюимшу вхяек я онлныэч юкцнпхрлю~K (дюфе еякх аш ме опнхгнькн янбоюдемхъ, опхбедеммнцн б рюак.~1), явхрюъ гюпюмее хгбеярмшл рнр тюйр, врн кчаюъ онякеднбюрекэмнярэ, бшпюанрюммюъ я хяонкэгнбюмхел щрнцн юкцнпхрлю, б йнмже йнмжнб ярюмер оепхндхвеяйни? \rex[Л20] Опедонкнфхл, врн лш унрхл бшпюанрюрэ онякеднбюрекэмнярэ жекшу вхяек~$X_0$, $X_1$, $X_2$,~\dots{} б хмрепбюке~$0\le X_n < m$. Осярэ~$f(x)$---кчаюъ тсмйжхъ, рюйюъ, врн еякх~$0 \le x < m$, рн~$0\le f(x)0$, рюйне, врн~$X_n=X_{2n}$; мюхлемэьее гмювемхе щрнцн~$n$ кефхр б хмрепбюке~$\mu \le n \le \mu+\lambda$. Гмювемхе~$X_n$ ъбкъеряъ едхмярбеммшл б рнл ялшяке, врн еякх~$X_n=X_{2n}$ х~$X_r=X_{2r}$, рн~$X_r=X_n$ (якеднбюрекэмн, $r-n$ йпюрмн~$\lambda$). \rex[20] Опхлемхре пегскэрюрш опедшдсыецн сопюфмемхъ, врнаш онярпнхрэ опюйрхвмши юкцнпхрл бшпюанрйх яксвюимшу вхяек, днонкмъчыхи дюрвхй рхою~$X_{n+1}=f(X_n)$. Бюь юкцнпхрл днкфем: a)~накюдюрэ ябниярбнл опхнярюмюбкхбюрэ бшпюанрйс яксвюимшу вхяек онякеднбюрекэмнярх, йюй рнкэйн онбрнпъеряъ пюмее бярпевюбьееяъ вхякн, b)~бшпюанрюрэ он лемэьеи лепе~$\lambda$ щкелемрнб оепед нярюмнбйни, унръ гмювемхе~$\lambda$ гюпюмее мехгбеярмн, х~c)~хяонкэгнбюрэ меанкэьсч оюлъцэ (р.~е.\ ме пюгпеьюеряъ. опнярн гюонлхмюрэ бяе бшвхякеммше онякеднбюрекэмше гмювемхъ). \ex[28] Онкмнярэч опнбепэре лернд яепедхмш йбюдпюрю дкъ яксвюъ дбсгмювмшу вхяек. a)~Лш лнфел мювюрэ я кчанцн хг 100~бнглнфмшу гмювемхи~$00$, $01$,~\dots, $99$. Б яйнкэйху яксвюъу лш б йнмже йнмжнб опхдел й онбрнпемхч жхйкю~$00$, $00$,~\dots? [\emph{Опхлеп.} Мювюб я~$43$, лш онксвхл онякеднбюрекэмнярэ~$43$, $84$, $05$, $02$, $00$, $00$, $00$,~$\ldots\,$.] b)~Яйнкэйн лнфер онксвхрэяъ пюгкхвмшу жхйкнб? Йюйнбю дкхмю оепхндю яюлнцн дкхммнцн жхйкю? c)~Йюйне мювюкэмне гмювемхе %% 21 онгбнкъер онксвхрэ яюлсч дкхммсч онякеднбюрекэмнярэ меонбрнпъчыхуяъ щкелемрнб? \ex[Л14] Днйюфхре, врн лернд яепедхмш йбюдпюрю, хяонкэгсчыхи $2n\hbox{-гмювмше}$ вхякю я нямнбюмхел~$b$, хлеер якедсчыхи меднярюрнй: мювхмюъ я вхякю~$X$, с йнрнпнцн ярюпьхе $n$~жхтп пюбмш мскч, бяе онякедсчыхе щкелемрш онякеднбюрекэмнярх ярюмнбъряъ бяе лемэье х лемэье, онйю ме напюръряъ б мскэ. \ex[Л16] Янупюмхб опедонкнфемхъ опедшдсыецн сопюфмемхъ, врн лнфмн яйюгюрэ н онякеднбюрекэмнярх щкелемрнб, якедсчыху гю вхякнл~$X$, с йнрнпнцн \emph{яюлше лкюдьхе} $n$~жхтп пюбмш мскч? Врн, еякх лкюдьхе $(n+1)$~жхтп пюбмш мскч? \rex[Л26] Пюяялнрпхл яксвюимше онякеднбюрекэмнярх, бшпюаюршбюелше дюрвхйюлх рхою нохяюммнцн б соп.~6. Еякх лш бшахпюел~$f(x)$ х~$X_0$ яксвюимн х опедонкюцюел, врн кчаше хг $m^m$~бнглнфмшу тсмйжхи~$f(x)$ х $m$~мювюкэмшу гмювемхи~$X_0$ пюбмнбепнърмш, рн йюйнбю бепнърмнярэ рнцн, врн б йнмже йнмжнб онякеднбюрекэмнярэ бшпндхряъ, напюгсъ жхйк я дкхмни оепхндю~$\lambda=1$? [\emph{Гюлевюмхе.} Опедонкнфемхъ, опхмърше б щрни гюдюве, дючр бнглнфмнярэ бонкме еяреярбеммшл напюгнл гюдслюрэяъ н "яксвюимнл" дюрвхйе яксвюимшу вхяек онднамнцн рхою. Лнфмн нфхдюрэ, врн лернд, онднамши юкцнпхрлс~K, днкфем ашрэ онунфхл мю япедмхи дюрвхй, пюяялнрпеммши гдеяэ. Пеьемхе гюдювх дюер лепс рнцн, мюяйнкэйн "йнкняяюкэмн" мю яюлнл деке янбоюдемхе, опхбедеммне б рюак.~1.] \rex[Л31] Хяонкэгсъ опедонкнфемхъ опедшдсыецн сопюфмемхъ, мюидхре япедмчч дкхмс жхйкю, йнрнпши напюгсеряъ б онякеднбюрекэмняръу. Йюйни япедмеи дкхмш днярхцюер онякеднбюрекэмнярэ, опефде вел мювюрэ жхйкхрэяъ? (Б нангмювемхъу соп.~6 лш унрхл нопедекхрэ япедмхе гмювемхъ~$\lambda$ х~$\mu+\lambda$.) \ex[Л42] Еякх~$f(x)$ бшахпюеряъ яксвюимн б ялшяке соп.~11, йюйнбю япедмъъ дкхмю \emph{яюлнцн дкхммнцн} жхйкю, онксвеммнцн б пегскэрюре хглемемхъ мювюкэмнцн гмювемхъ~$X_0$? [\emph{Гюлевюмхе.} Нрбер хгбеярем дкъ яоежхюкэмнцн яксвюъ, йнцдю б йювеярбе тсмйжхх~$f(x)$ пюяялюрпхбюеряъ оепеярюмнбйю; ял. соп.~1.3.3-23.] \ex[Л38] Еякх~$f(x)$ бшахпюеряъ яксвюимн б ялшяке соп.~11, йюйнбн япедмее вхякн пюгкхвмшу жхйкнб, онксвюелшу б пегскэрюре хглемемхъ мювюкэмнцн гмювемхъ? (Яп.~я~соп.~8(b).) \ex[Л15] Еякх~$f(x)$ бшахпюеряъ яксвюимн б ялшяке соп.~11, йюйнбю бепнърмнярэ рнцн, врн мх ндхм хг жхйкнб ме хлеер дкхмш~$1$, аегнрмняхрекэмн й бшанпс~$X_0$? \ex[15] Онякеднбюрекэмнярэ, бшпюаюршбюелюъ я онлныэч лерндю, нохяюммнцн б соп.~6, днкфмю мювюрэ онбрнпърэяъ яюлне онгдмее оняке бшпюанрйх $m$~гмювемхи. Опедонкнфхл, врн лш нанаыхкх лернд рюй, врн $X_{n+1}$~реоепэ гюбхяхр ме рнкэйн нр~$X_n$, мн х нр~$X_{n-1}$. Тнплюкэмн осярэ~$f(x, y)$ асдер рюйюъ тсмйжхъ, врн еякх~$0\le x$, $y0$.} $$ Йюйсч люйяхлюкэмсч дкхмс оепхндю лнфмн онксвхрэ б щрнл яксвюе? \ex[10] Нанаыхре хдеч опедшдсыецн сопюфмемхъ рюй, врнаш $X_{n+1}$~гюбхяекн нр $k$~опедшдсыху гмювемхи щкелемрнб онякеднбюрекэмнярх. \ex[Л22] Опхдслюире лернд, юмюкнцхвмши опедкнфеммнлс б соп.~7, дкъ намюпсфемхъ жхйкю дюрвхйю яксвюимшу вхяек наыецн бхдю, пюяялнрпеммнцн б опедшдсыел сопюфмемхх. \ex[Л50] Пеьхре гюдювх, онярюбкеммше б соп.~11--15, дкъ анкее наыецн яксвюъ, йнцдю $X_{n+1}$~гюбхяхр нр опедшдсыху $k$~щкелемрнб онякеднбюрекэмнярх. Йюфдюъ хг~$m^{m^k}$ тсмйжхи~$f(x_1, x_2,~\ldots, x_k)$ днкфмю пюяялюрпхбюрэяъ йюй пюбмнбепнърмюъ. [\emph{Гюлевюмхе.} Йнкхвеярбн тсмйжхи, дючыху \emph{люйяхлюкэмши} оепхнд, опхбндхряъ б соп.~2.3.4.2-23.] %% 22 \subchap{БШПЮАНРЙЮ ПЮБМНЛЕПМН ПЮЯОПЕДЕКЕММШУ ЯКСВЮИМШУ ВХЯЕК} % 3.2 Б щрнл оюпюцпюте лш пюяялнрпхл лерндш онксвемхъ онякеднбюрекэмнярх яксвюимшу дпнаеи, р.~е.\ яксвюимшу \emph{деиярбхрекэмшу вхяек~$U_n$, пюбмнлепмн пюяопедекеммшу лефдс мскел х едхмхжеи.} Рюй йюй б бшвхякхрекэмни люьхме деиярбхрекэмне вхякн бяецдю опедярюбкъеряъ я нцпюмхвеммни рнвмнярэч, тюйрхвеяйх лш асдел цемепхпнбюрэ жекше вхякю~$X_n$ б хмрепбюке нр~$0$ дн мейнрнпнцн~$m$. Рнцдю дпнаэ $$ U_n=X_n/m \eqno(1) $$ оноюдер б хмрепбюк нр мскъ дн едхмхжш. Нашвмн~$m$ мю едхмхжс анкэье люйяхлюкэмнцн вхякю, йнрнпне лнфмн гюохяюрэ б люьхммнл якнбе [($m$ пюбмн \emph{пюглепс якнбю} (word size)]. Онщрнлс~$X_n$ лнфмн хмрепоперхпнбюрэ (йнмяепбюрхбмн) йюй жекне яндепфхлне люьхммнцн якнбю я деяърхвмни гюоърни, пюяонкнфеммни яопюбю, ю~$U_n$ лнфмн явхрюрэ (кхаепюкэмн) дпнаэч, яндепфюыеияъ б рнл фе якнбе, я гюоърни б йпюимеи кебни онгхжхх. \subsubchap{Кхмеимши йнмцпсщмрмши лернд} % 3.2.1 Мюхксвьхе хг хгбеярмшу яецндмъ дюрвхйнб яксвюимшу вхяек опедярюбкъчр янани вюярмше яксвюх якедсчыеи яуелш, опедкнфеммни Д.~X.~Келепнл б~1948~ц.\ [Ял. Proc. 2nd Symposium on Large-Scale Digital Computing Machinery (Cambridge: Harvard University Press, 1951), 141--146.] Бшахпюел вершпе "люцхвеяйху вхякю": $$ \vcenter{\halign{ $#$\hfil\bskip&#\bskip\hfil&\bskip\hfil$#$&${}#$\hfil\cr X_0, & мювюкэмне гмювемхе; & X_0&\ge 0; \cr a, & лмнфхрекэ; & a&\ge 0; \cr c, & опхпюыемхе; & c&\ge 0; \cr m, & лндскэ; & m&> X_0, m>a, m>c.\cr }} \eqno(1) $$ Рнцдю хяйнлюъ онякеднбюрекэмнярэ яксвюимшу вхяек~$\$ онксвюеряъ хг яннрмньемхъ $$ X_{n+1}=(aX_n+c) \bmod m, \rem{$n\ge 0$.} \eqno (2) $$ Нмю мюгшбюеряъ \dfn{кхмеимни йнмцпсщмрмни онякеднбюрекэмнярэч.} %% 23 Мюопхлеп, опх~$X_0=a=c=7$, $m=10$ онякеднбюрекэмнярэ бшцкъдхр рюй: $$ 7,\; 6,\; 9,\; 0,\; 7,\; 6,\; 9,\; 0,\;~\ldots \eqno (3) $$ Йюй бхдмн хг опхбедеммнцн опхлепю, онякеднбюрекэмнярэ ме бяецдю нйюгшбюеряъ "яксвюимни", еякх бшахпюрэ~$X_0$, $a$, $c$, $m$ опнхгбнкэмн. Б онякедсчыху пюгдекюу щрни цкюбш асдср ондпнамн хяякеднбюмш опхмжхош бшанпю щрху гмювемхи. Опхлеп~(3) хккчярпхпсер рнр тюйр, врн йнмцпсщмрмше онякеднбюрекэмнярх бяецдю "гюжхйкхбючряъ", р.~е.\ б йнмже йнмжнб вхякю напюгсчр жхйк, йнрнпши онбрнпъеряъ аеяйнмевмне вхякн пюг. Щрн ябниярбн опхясые бяел онякеднбюрекэмняръл, хлечыхл наыхи бхд~$X_{n+1}=f(X_n)$; ял.~соп.~3.1-6. Онбрнпъчыхияъ жхйк мюгшбюеряъ \dfn{оепхнднл.} Дкхмю оепхндю с онякеднбюрекэмнярх~(3) пюбмю~$4$. Пеюкэмше онякеднбюрекэмнярх, йнрнпшлх онкэгсчряъ, хлечр, йнмевмн, япюбмхрекэмн анкэьни оепхнд. Яоежхюкэмнцн сонлхмюмхъ гюяксфхбюер вюярмши яксвюи~$c=0$, йнцдю опнжеяя бшпюанрйх яксвюимшу вхяек опнхяундхр меяйнкэйн ашярпее. Онгфе лш сбхдхл, врн нцпюмхвемхе~$c=0$ слемэьюер дкхмс оепхндю онякеднбюрекэмнярх, мн опх щрнл бяе еые лнфмн онксвхрэ нрмняхрекэмн анкэьни оепхнд. Б оепбнмювюкэмнл лернде Келепю ашкн опхмърн~$c=0$, унръ юбрнп х сонлъмск бнглнфмнярэ хяонкэгнбюмхъ~$c\ne 0$. Хдеъ онксвемхъ анкее дкхммшу онякеднбюрекэмняреи гю явер нанаыемхъ~$c\ne 0$ опхмюдкефхр Рнлянмс [{\sl Comp. J.,\/} {\bf 1} (1958), 83, 86] х мегюбхяхлн Пнремаепцс [{\sl JACM,\/} {\bf 7} (1960), 75--77]. Лмнцхлх юбрнпюлх реплхмш \dfn{лскэрхокхйюрхбмши йнмцпсщмрмши лернд} х \dfn{ялеьюммши йнмцпсщмрмши лернд} опхлемъчряъ дкъ нангмювемхъ кхмеимшу йнмцпсщмрмшу лернднб я~$c=0$ х~$c\ne0$ яннрберярбеммн. Бн бяеи щрни цкюбе асйбш~$a$, $c$, $m$, $X_0$ асдср хяонкэгнбюрэяъ б рнл ялшяке, йюй щрн опхмърн бшье. Анкее рнцн, врнаш сопнярхрэ лмнцхе мюьх тнплскш, нйюгшбюеряъ онкегмшл нопедекхрэ $$ b=a-1. \eqno(4) $$ Лнфмн япюгс фе нрапняхрэ яксвюи~$a=1$, рюй йюй опх щрнл $X_n=(X_0+nc) \bmod m$, х нвебхдмн, врн онякеднбюрекэмнярэ ме яксвюимюъ. Бюпхюмр~$a=0$ еые усфе. Якеднбюрекэмн, дкъ опюйрхвеяйху жекеи лш лнфел опедонкнфхрэ, врн $$ a\ge 2, \qquad b \ge 1. \eqno (5) $$ Реоепэ лнфмн нанаыхрэ яннрмньемхе~(2), $$ X_{n+k}=(a^k X_n+(a^k-1)c/b) \bmod m, \rem{$k\ge 0$, $n\ge 0$}, \eqno (6) $$ бшпюгхб $(n+k)\hbox{-и}$~вкем опълн вепег~$n\hbox{-и}$. (Якедсер напюрхрэ бмхлюмхе мю вюярмши яксвюи~$n=0$.) Онякеднбюрекэмнярэ, янярюбкеммюъ %% 24 хг йюфднцн $k\hbox{-цн}$~вкемю мюьеи онякеднбюрекэмнярх напюгсер дпсцсч кхмеимсч йнмцпсщмрмсч онякеднбюрекэмнярэ я лмнфхрекел~$a^k$ х опхпюыемхел~$((a^k-1)c/b)$. \excercises \ex[10] Б опхлепе~(3) хккчярпхпсеряъ яхрсюжхъ, йнцдю~$X_4=X_0$, рюй врн онякеднбюрекэмнярэ ноърэ мювхмюеряъ ямювюкю. Мюидхре опхлеп рюйни кхмеимни йнмцпсщмрмни онякеднбюрекэмнярх я~$m=10$, б йнрнпни $X_0$~бярпевюеряъ рнкэйн ндхм пюг. \rex[Л20] Онйюфхре, врн, еякх~$a$ х~$m$ бгюхлмн опнярше, вхякн~$X_0$ асдер оепхндхвеяйх онбрнпърэяъ. \ex[Л10] На╝ъямхре, онвелс, еякх~$a$ х~$m$ ме ъбкъчряъ бгюхлмн опняршлх, онякеднбюрекэмнярэ б йюйнл-рн ялшяке месдювмюъ х, бепнърмн, ме якхьйнл яксвюимюъ. Онщрнлс, бннаые цнбнпъ, лш асдел ярюпюрэяъ бшахпюрэ~$a$ х~$m$ бгюхлмн опняршлх. \ex[11] Днйюфхре яннрмньемхе~(6). \ex[Л20] Яннрмньемхе~(6) бшонкмъеряъ дкъ~$k\ge 0$. Еякх щрн бнглнфмн, онксвхре тнплскс, бшпюфючысч~$X_{n+k}$ вепег~$X_n$ х дкъ \emph{нрпхжюрекэмшу} гмювемхи~$k$. \subsubsubchap{Бшанп лндскъ}%3.2.1.1 Ямювюкю наясдхл, йюй опюбхкэмн бшахпюрэ вхякн~$m$. Лш унрхл, врнаш гмювемхе~$m$ ашкн днярюрнвмн анкэьхл, рюй йюй дкхмю оепхндю ме лнфер ашрэ анкэье~$m$. (Дюфе еякх рпеасчряъ рнкэйн яксвюимше мскх х едхмхжш, ме якедсер апюрэ~$m=2$, рюй йюй опх щрнл б ксвьел яксвюе онксвхряъ мюанп $$ \ldots, 0, 1, 0, 1, 0, 1,\ldots\,! $$ Лерндш хяонкэгнбюмхъ пюбмнлепмн пюяопедекеммшу яксвюимшу вхяек дкъ онксвемхъ онякеднбюрекэмнярх мскеи х едхмхж наясфдючряъ б~\S~3.4.) Дпсцни тюйрнп, бкхъчыхи мю бшанп~$m$---щрн яйнпнярэ бшпюанрйх вхяек: лш унрхл онднапюрэ рюйне гмювемхе, врнаш ашярпее бшвхякърэ~$(aX_n+c)\bmod m$. Пюяялнрпхл б йювеярбе опхлепю люьхмс~\MIX. Лш лнфел бшвхякърэ~$y \bmod m$, онлеыюъ~$y$ б пецхярпш~|A| х~|X|, онякедсчыхл декемхел мю~$m$. Опедонкнфхб, врн~$y$ х~$m$---онкнфхрекэмше вхякю, лнфмн саедхрэяъ, врн б пегскэрюре б пецхярпе~|X| нйюферяъ~$y\bmod m$. Мн рюй йюй декемхе---япюбмхрекэмн ледкеммюъ ноепюжхъ, ее лнфмн хгаефюрэ гю явер нянан сднамнцн бшанпю~$m$, опхмъб ецн пюбмшл \emph{пюглепс якнбю} (р.~е.~мю едхмхжс анкэье люйяхлюкэмнцн жекнцн вхякю, пюглеыючыецняъ б якнбе бшвхякхрекэмни люьхмш). Осярэ~$w$---рюйне люйяхлюкэмне жекне вхякн. Рнцдю ноепюжхъ якнфемхъ опнхгбндхряъ он лндскч~$w$, ю слмнфемхе он лндскч~$w$ рюйфе япюбмхрекэмн опнярн, рюй йюй мсфмши пегскэрюр онксвюеряъ б лкюдьху пюгпъдюу опнхгбедемхъ. Рюйхл напюгнл, якедсчыюъ %% 25 опнцпюллю щттейрхбмн бшвхякъер~$(aX+c)\bmod w$: $$ \vcenter{ \mixcode LDA & A MUL & X SLAX & 5 ADD & C \endmixcode } \eqno(1) $$ Пегскэрюр онксвюеряъ б пецхярпе~|A|. Б йнмже бшонкмемхъ щрни онякеднбюрекэмнярх йнлюмд лнфер опнхгнирх оепеонкмемхе, яхцмюк йнрнпнцн лнфмн бшйкчвхрэ, мюохяюб бякед гю онякедмеи йнлюмдни~"|JOV *+1|". Лемее ьхпнйн хгбеярмсч рнмйсч реумхйс лнфмн хяонкэгнбюрэ дкъ бшвхякемхи он лндскч~$(w+1)$. Он опхвхмюл, н йнрнпшу асдер яйюгюмн мхфе, опх~$m=w+1$ лш нашвмн онкюцюел~$c=0$. Онщрнлс мюл мсфмн бшвхякърэ опнярн~$(aX)\bmod(w+1)$. Щрн декюер якедсчыюъ опнцпюллю: $$ \vcenter{ \mixcode LDAN & X MUL & A STX & TEMP SUB & TEMP JANN & *+3 INCA & 2 ADD & =W-1= \endmixcode } \eqno(2) $$ Б пецхярпе~|A| реоепэ яндепфхряъ гмювемхе~$(aX)\bmod (w+1)$. Йнмевмн, нмн лнфер ашрэ кчашл б хмрепбюке лефдс~$0$ х~$w$. Онщрнлс вхрюрекэ бонкме гюйнммн лнфер яопняхрэ, йюй лнфмн гюохяюрэ рюй лмнцн гмювемхи я онлныэч |A|-пецхярпю! (Нвебхдмн, врн б пецхярпе ме лнцср онлеыюрэяъ вхякю, анкэьхе, вел~$w-1$.) Нрбер янярнхр б рнл, врн оепеонкмемхе опнхгнидер рнцдю х рнкэйн рнцдю, йнцдю пегскэрюр пюбем~$w$ (б опедонкнфемхх, врн яхцмюк оепеонкмемхъ ашк пюмее бшйкчвем). Дкъ днйюгюрекэярбю рнцн, врн опнцпюллю~(2), б яюлнл деке, бшвхякъер~$(aX)\bmod (w+1)$, гюлерхл, врн б ярпнйе~04 лш бшвхрюел лкюдьсч онкнбхмс опнхгбедемхъ хг ярюпьеи. Оепеонкмемхъ опх щрнл опнхгнирх ме лнфер, х, еякх~$aX=qw+r$, цде~$0\le r < w$, б пецхярпе~|A| оняке бшонкмемхъ ярпнйх~04 нйюферяъ гмювемхе~$r-q$. Гюлерхл, врн $$ aX=q(w+1)+(r-q), $$ ю рюй йюй~$q2$. Еякх $$ x\equiv 1 \pmod{p^e}, \quad x \not\equiv 1 \pmod{p^{e+1}}, \eqno(1) $$ рн $$ x^p \equiv 1 \pmod{p^{e+1}}, \quad x^p \not\equiv 1 \pmod{p^{e+2}}. \eqno(2) $$ \proof Лш хлеел~$x=1+qp^e$, цде~$q$---мейнрнпне жекне, ме йпюрмне~$p$. %% 30 Он тнплске ахмнлю гюохьел $$ \eqalign{ x^p&=1+\perm{p}{1}qp^e+\cdots+\perm{p}{p-1}q^{p-1}p^{(p-1)e}+q^pp^{pe}=\cr &=1+qp^{e+1}\left(1+{1\over p}\perm{p}{2}qp^e+{1\over p}\perm{p}{3}q^2p^{2e}+ \cdots+{1\over p}\perm{p}{p}q^{p-1}p^{(p-1)e}\right).\cr } $$ Бшпюфемхе б яйнайюу---жекне вхякн, опхвел йюфдне якюцюелне йпюрмн~$p$, гю хяйкчвемхел оепбнцн вкемю. Б яюлнл деке, еякх~$11$ опх~$p^e>2$. Рюйхл напюгнл, $x^p=1+q'p^{e+1}$, цде~$q'$---жекне вхякн, йнрнпне ме декхряъ мю~$p$. Рел яюлшл днйюгюрекэярбн гюбепьемн. (\emph{Гюлевюмхе:} нанаыемхе щрнцн пегскэрюрю яндепфхряъ б соп.~3.2.2-11~(a).) \proofend \proclaim Келлю~Q. {Осярэ пюгкнфемхе~$m$ мю опнярше лмнфхрекх хлеер бхд $$ m=p_1^{e_1}\ldots p_t^{e_t}. \eqno(3) $$ \hiddenpar Дкхмю~$\lambda$ оепхндю кхмеимни йнмцпсщмрмни онякеднбюрекэмнярх, нопедекъелни~$(X_0, a, c, m)$, пюбмю мюхлемэьелс наыелс йпюрмнлс дкхм~$\lambda_j$ оепхнднб кхмеимшу йнмцпсщмрмшу онякеднбюрекэмняреи $$ (X_0 \bmod p_j^{e_j}, a p_j^{e_j}, c p_j^{e_j}, p_j^{e_j}), \rem{$1\le j \le t$.} $$ } \proof Хмдсйжхеи он~$t$ днярюрнвмн днйюгюрэ, врн, еякх~$r$ х~$s$---бгюхлмн опнярше вхякю, дкхмю~$\lambda$ оепхндю кхмеимни йнмцпсщмрмни онякеднбюрекэмнярх, нопедекъелни~$(X_0, a, c, rs)$, пюбмю мюхлемэьелс наыелс йпюрмнлс дкхм~$\lambda_1$ х~$\lambda_2$ оепхнднб онякеднбюрекэмняреи~$(X_0 \bmod r, a \bmod r, c \bmod r, r)$ х~$(X_0 \bmod s, a \bmod s, c \bmod s, s)$. Б опедшдсыел пюгдеке (ял.~тнплскс~(5)) лш бхдекх, врн еякх нангмювхрэ щкелемрш щрху рпеу онякеднбюрекэмняреи яннрберярбеммн~$X_n$, $Y_n$, $Z_n$, рн бшонкмъчряъ якедсчыхе яннрмньемхъ: $$ Y_n=X_n \bmod r \hbox{ х } Z_n=X_n \bmod s \rem{дкъ бяеу~$n\ge 0$.} $$ %% 31 Онщрнлс хг ябниярбю~D о.~1.2.4 мюундхл, врн $$ X_n=X_k \rem{рнцдю х рнкэйн рнцдю, йнцдю~$Y_n=Y_k$ х~$Z_n=Z_k$.} \eqno (4) $$ Осярэ~$\lambda'$---мюхлемэьее наыее йпюрмне дкхм~$\lambda_1$ х~$\lambda_2$; днйюфел, врн~$\lambda'=\lambda$. Рюй йюй~$X_n=X_{n+\lambda}$ дкъ бяеу днярюрнвмн анкэьху~$n$, хлеел~$Y_n=Y_{n+\lambda}$ (якеднбюрекэмн, $\lambda$ йпюрмн~$\lambda_1$) х~$Z_n=Z_{n+\lambda}$ (якеднбюрекэмн, $\lambda$ йпюрмн~$\lambda_2$), х онщрнлс~$\lambda\ge\lambda'$. Я дпсцни ярнпнмш, лш гмюел, врн~$Y_n=Y_{n+\lambda'}$ х~$Z_n=Z_{n+\lambda'}$ дкъ бяеу днярюрнвмн анкэьху~$n$. Онщрнлс мю нямнбюмхх~(4) хлеел~$X_n=X_{n+\lambda'}$, хг вецн онксвюел~$\lambda\le\lambda'$, рюй врн~$\lambda=\lambda'$. \proofend Реоепэ лш цнрнбш днйюгюрэ ренпелс~A. Хлеъ б бхдс келлс~Q, днярюрнвмн днйюгюрэ ренпелс дкъ яксвюъ, йнцдю $m$~еярэ яреоемэ опнярнцн вхякю. Б яюлнл деке, мепюбемярбн $$ p_1^{e_1} \ldots p_t^{e_t}=\lambda=\мнй(\lambda_1,~\ldots, \lambda_t) \le \lambda_1 \ldots \lambda_t \le p_1^{e_1}\ldots p_t^{e_t} $$ лнфер ашрэ яопюбедкхбн б рнл х рнкэйн рнл яксвюе, еякх~$\lambda_j=p_j^{e_j}$ дкъ~$1\le j \le t$. Онщрнлс опедонкнфхл, врн~$m=p^e$, цде~$p$---опнярне, ю~$e$---онкнфхрекэмне жекне вхякн. Нвебхдмн, врн опх~$a=1$ ренпелю яопюбедкхбю, онщрнлс лнфмн явхрюрэ~$a>1$. Дкхмю оепхндю пюбмю~$m$ рнцдю х рнкэйн рнцдю, йнцдю йюфдне жекне вхякн~$x$, рюйне, врн~$0 \le x < m$, бярпевюеряъ б онякеднбюрекэмнярх мю опнръфемхх оепхндю (оняйнкэйс мх ндмн хг гмювемхи ме лнфер бярперхрэяъ гю оепхнд анкее ндмнцн пюгю). Рюйхл напюгнл, оепхнд хлеер дкхмс~$m$ б рнл х рнкэйн рнл яксвюе, еякх дкхмю оепхндю онякеднбюрекэмнярх я~$X_0=0$ пюбмю~$m$, врн нопюбдшбюер опедонкнфемхе~$X_0=0$. Хг. тнплскш~3.2.1-(6) хлеел $$ X_n=\left({a^n-1 \over a-1}\right) c \bmod m. \eqno (5) $$ Еякх вхякю~$c$ х~$m$ ме ъбкъчряъ бгюхлмн опняршлх, $X_n$ мхйнцдю ме лнфер ашрэ пюбмн~$1$. Онщрнлс сякнбхе~(i) нйюгшбюеряъ менаундхлшл. Оепхнд хлеер дкхмс~$m$ рнцдю х рнкэйн рнцдю, йнцдю мюхлемэьее онкнфхрекэмне гмювемхе~$n$, дкъ йнрнпнцн~$X_n=X_0=0$, рюйнбн, врн~$n=m$. Реоепэ б яхкс~(5) х сякнбхъ~(i) мюью ренпелю ябндхряъ й днйюгюрекэярбс якедсчыецн србепфдемхъ. \proclaim Келлю~R. Опедонкнфхл, врн~$12$,\cr a\equiv 1 \pmod{4} & опх $p=2$. } $$ %% 32 \proof Опедонкнфхл, врн~$\lambda=p^e$. Еякх~$a\not\equiv 1 \pmod{p}$, рн~$(a^n-1)/(a-1)\equiv 0 \pmod{p^e}$ б рнл х рнкэйн рнл яксвюе, йнцдю~$a^n-1\equiv 0 \pmod{p^e}$. Сякнбхе~$a^{p^e}-1\equiv 0 \pmod{p^e}$ рнцдю рпеасер, врнаш бшонкмъкняэ яннрмньемхе~$a^{p^e}\equiv 1 \pmod{p}$. Мн хг ренпелш~1.2.4F якедсер, врн~$a^{p^e}\equiv a \pmod{p}$; рюйхл напюгнл онксвюел~$a\not\equiv 1 \pmod{p}$, врн опхбндхр й опнрхбнпевхч. Еякх фе~$p=2$ х~$a\equiv 3 \pmod{4}$, рн хг соп.~8 хлеел~$(a^{2^{e-1}}-1)/(a-1)\equiv 0 \pmod{2^e}$. Щрх яннапюфемхъ нанямнбшбючр менаундхлнярэ пюбемярбю~$a=1+qp^f$, цде~$p^f>2$, ю~$q$ ме йпюрмн~$p$ дкъ кчашу~$\lambda=p^e$. Нярюеряъ онйюгюрэ, врн щрн сякнбхе \emph{днярюрнвмн} дкъ бшонкмемхъ яннрмньемхъ~$\lambda=p^e$. Онбрнпмн хяонкэгсъ келлс~P, мюундхл, врн $$ a^{p^g}\equiv 1 \pmod{p^{f+g}}, \quad a^{p^g}\not\equiv 1 \pmod{p^{f+g+1}}, $$ х онщрнлс $$ \eqalign{ (a^{p^g}-1)/(a-1) &\equiv 0 \pmod{p^g}, \cr (a^{p^g}-1)/(a-1) &\not\equiv 0 \pmod{p^{g+1}}.\cr } \eqno(6) $$ Б вюярмнярх, $(a^{p^e}-1)/(a-1)\equiv 0 \pmod{p^e}$. Рюйхл напюгнл, б йнмцпсщмрмни онякеднбюрекэмнярх~$(0, a, 1, p^e)$ хлеел~$X_n=(a^n-1)/(a-1) \bmod p^e$; онщрнлс дкхмю ее оепхндю пюбмю~$\lambda$, р.~е.~$X_n=0$ рнцдю х рнкэйн рнцдю, йнцдю~$n$ йпюрмн~$\lambda$. Якеднбюрекэмн, $p^e$ йпюрмн~$\lambda$. Щрн бнглнфмн рнкэйн, еякх~$\lambda=p^g$ дкъ мейнрнпнцн~$g$. Хг яннрмньемхъ~(6) онксвюел~$\lambda=p^e$, врн гюбепьюер днйюгюрекэярбн. \proofend Реоепэ гюйнмвемн х днйюгюрекэярбн ренпелш~A. \proofend Б гюйкчвемхе щрнцн пюгдекю пюяялнрпхл яоежхюкэмши яксвюи вхярн лскэрхокхйюрхбмшу дюрвхйнб, дкъ йнрнпшу~$c=0$. Унръ опх щрнл бшпюанрйю яксвюимшу вхяек опнхяундхр меяйнкэйн ашярпее, ренпелю~A онйюгшбюер, врн днахрэяъ люйяхлюкэмни дкхмш оепхндю мекэгъ. Деиярбхрекэмн, щрн бонкме нвебхдмн, рюй йюй вкемш онякеднбюрекэмнярх сднбкербнпъчр яннрмньемхч $$ X_{n+1}=aX_n\bmod m, \eqno(7) $$ х гмювемхе~$X_n=0$ лнфер б меи бярперхрэяъ, рнкэйн еякх онякеднбюрекэмнярэ бшпнфдюеряъ б мскэ. Бннаые, еякх~$d$---кчани декхрекэ~$m$ х еякх~$X_n$ йпюрмн~$d$, бяе онякедсчыхе гмювемхъ~$X_{n+1}$, $X_{n+2}$,~\dots{} рнфе йпюрмш~$d$. Онщрнлс опх~$c=0$ фекюрекэмн, врнаш $X_n$~ашкх бгюхлмн опнярш я~$m$ дкъ бяеу~$n$, ю щрн нцпюмхвхбюер дкхмс оепхндю. Лнфмн днахрэяъ опхелкелн анкэьнцн оепхндю, дюфе еякх лш мюярюхбюел, врнаш~$c=0$. Оношрюеляъ реоепэ мюирх рюйхе сякнбхъ, %% 33 нопедекъчыхе лмнфхрекэ, врнаш х б щрнл вюярмнл яксвюе дкхмю оепхндю ашкю люйяхлюкэмю. Бякедярбхе келлш~Q оепхнд онякеднбюрекэмнярх онкмнярэч нопедекъеряъ оепхндюлх онякеднбюрекэмняреи я~$m=p^e$, рюй врн пюяялнрпхл хлеммн рюйсч яхрсюжхч. Лш хлеел~$X_n=a^n X_0 \bmod p^e$, х ъямн, врн дкхмю оепхндю пюбмю~$1$, еякх~$a$ йпюрмн~$p$\note{1}% {Еякх~$a$ йпюрмн~$p$, рн, бннаые цнбнпъ, оепхнд ме опебняундхр~$e$.---{\sl Опхл. пед.\/} }. Онщрнлс бшаепел~$a$ бгюхлмн опняршл я~$p^e$. Рнцдю оепхнд пюбем мюхлемэьелс жекнлс~$\lambda$, рюйнлс, врн~$X_0=a^\lambda X_0 \bmod p^e$. Еякх мюханкэьхи наыхи декхрекэ~$X_0$ х~$p^e$ еярэ~$p^f$, щрн сякнбхе щйбхбюкемрмн якедсчыелс: $$ a^\lambda \equiv 1 \pmod{p^{e-f}}. \eqno(8) $$ Он ренпеле Щикепю (соп.~1.2.4-28) $$ a^{\varphi(p^{e-f})} \equiv 1 \pmod{p^{e-f}}; $$ якеднбюрекэмн, $\lambda$~еярэ декхрекэ: $$ \varphi(p^{e-f})=p^{e-f-1}(p-1). $$ Дкъ бгюхлмн опняршу~$a$ х~$m$ мюхлемэьее жекне~$\lambda$, дкъ йнрнпнцн~$a^\lambda \equiv 1 \pmod{m}$, нашвмн мюгшбючр \dfn{онпъдйнл он лндскч~$m$}. Бекхвхмю~$a$, йнрнпни яннрберярбсер \emph{люйяхлюкэмн} бнглнфмши онпъднй он лндскч~$m$, мюгшбюеряъ \dfn{оепбннапюгмшл щкелемрнл} он лндскч~$m$\note{2}% {Ме якедсер осрюрэ оепбннапюгмши щкелемр я оепбннапюгмшл йнпмел. Оепбннапюгмше йнпмх ясыеярбсчр ме дкъ бяеу~$m$.---{\sl Опхл. пед.\/} }. Нангмювхл вепег~$\lambda(m)$ онпъднй оепбннапюгмнцн щкелемрю, р.~е.\ люйяхлюкэмн бнглнфмши онпъднй он лндскч~$m$. Опедшдсыхе гюлевюмхъ онйюгшбючр, врн~$\lambda(p^e)$ еярэ декхрекэ~$p^{e-1}(p-1)$; ме янярюбкъер рпсдю (ял.~мхфе соп.~11--16) опхбеярх рнвмше гмювемхъ~$\lambda(m)$ б якедсчыху яксвюъу: $$ \eqalignrem{ & \lambda(2)=1, \quad \lambda(4)=2, \quad \lambda(2^e)=2^{e-2}, & еякх $e\ge3$,\cr & \lambda(p^e)=p^{e-1}(p-1), & еякх $p>2$, \cr & \lambda(p_1^{e_1}\ldots p_t^{e_t})=\мнй(\lambda(p_1^{e_1},\ldots, \lambda(p_t^{e_t}))).\cr } \eqno(9) $$ Мюьх гюлевюмхъ лнфмн ясллхпнбюрэ б якедсчыеи ренпеле: \proclaim Ренпелю~B. (П. Йюплюийк) [R. D. Carmichael, {\sl Bull.\ Amer.\ Math.\ Soc.,\/} {\bf 16} (1910), 232--238]. Люйяхлюкэмн бнглнфмши опх~$c=0$ оепхнд пюбем~$\lambda(m)$, цде~$\lambda(m)$ нопедекъеряъ бшпюфемхълх~(9). Рюйни оепхнд пеюкхгсеряъ, еякх \medskip \item{i)}~$X_0$ х~$m$---бгюхлмн опнярше вхякю; \item{ii)}~$a$---оепбннапюгмши щкелемр он лндскч~$m$. \endmark %% 34 Гюлерэре, врн еякх~$m$---опнярне вхякн, лнфмн онксвхрэ дкхмс оепхндю~$m-1$, врн бяецн кхьэ мю едхмхжс лемэье люйяхлюкэмнцн гмювемхъ. Бнопня реоепэ гюйкчвюеряъ б рнл, йюй мюундхрэ оепбннапюгмше щкелемрш он лндскч~$m$. Хг сопюфмемхи б йнмже оюпюцпютю бшрейюер \proclaim Ренпелю~C. Вхякн~$a$ еярэ оепбннапюгмши щкелемр он лндскч~$p^e$ рнцдю х рнкэйн рнцдю, йнцдю \medskip \item{i)}~$p^e=2$, $a$---мевермне; хкх~$p^e=4$, $a \bmod 4=3$; хкх~$p^e=8$, $a \bmod 8=3, 5, 7$; хкх~$p=2$, $e \ge 4$, $a \bmod 8=3$ хкх~$5$; % \hiddenpar\noindent хкх \item{ii)}~$p$---мевермне, $e=1$, $a \not\equiv 0 \pmod{p}$ х~$a^{(p-1)q} \not\equiv 1 \pmod{p}$ дкъ кчанцн опнярнцн декхрекъ~$q$ вхякю~$p-1$; % \hiddenpar\noindent хкх \item{iii)}~$p$---мевермне, $e>1$, $a$~сднбкербнпъер~(ii) х~$a^{p-1} \not\equiv 1 \pmod{p^2}$\note{1}% {Ондпюгслебюеряъ, врн~$p$--- опнярне; еякх лндскэ хлеер бхд~$2$, $2^2$, $p^e$, цде~$p$---мевермне, оепбннапюгмше щкелемрш асдср х оепбннапюгмшлх йнпмълх.---{\sl Опхл. пед.\/} }. \endmark Сякнбхъ~(ii) х~(iii) щрни ренпелш кецйн опнбепъчряъ мю бшвхякхрекэмни люьхме дкъ анкэьху гмювемхи~$p$, еякх дкъ бшвхякемхъ яреоемеи хяонкэгнбюрэ щттейрхбмше лерндш, наясфдюелше б о.~4.6.3. Мюйнмеж, еякх мюл дюмш бекхвхмш~$a_j$, ъбкъчыхеяъ оепбннапюгмшлх щкелемрюлх он лндскч~$p_j^{e_j}$, лнфмн мюирх едхмярбеммне гмювемхе~$a$, рюйне, врн~$a \equiv a_j \pmod{p_j^{e_j}}$, $1\le j \le t$, опхлемъъ "йхрюияйсч ренпелс на нярюрйюу", йнрнпюъ наясфдюеряъ б~о.4.3.2. Якеднбюрекэмн, $a$~асдер оепбннапюгмшл щкелемрнл он лндскч~$p_1^{e_1}\ldots p_t^{e_t}$. Щрн дюер мюл днбнкэмн щттейрхбмши яоняна бшвхякемхъ лмнфхрекеи, сднбкербнпъчыху сякнбхч ренпелш~Б, дкъ кчанцн гмювемхъ~$m$. Ндмюйн б наыел яксвюе бшвхякемхъ нйюгшбючряъ меяйнкэйн дкхммшлх. Дкъ бюфмнцн яксвюъ~$m=2^e$ опх~$e\ge 4$ опхбедеммше бшье сякнбхъ ябндъряъ й едхмярбеммнлс опнярнлс рпеанбюмхч, врнаш~$a \equiv 3\hbox{ хкх } 5 \pmod{8}$. Б щрнл яксвюе вербепрюъ вюярэ бяеу бнглнфмшу лмнфхрекеи дюер люйяхлюкэмши оепхнд. Брнпни мюханкее пюяопнярпюмеммши яксвюи, щрн~$m=10^e$. Онкэгсъяэ келлюлх~П х~Q, мерпсдмн онксвхрэ менаундхлше х днярюрнвмше сякнбхъ днярхфемхъ люйяхлюкэмнцн оепхндю дкъ деяърхвмни бшвхякхрекэмни люьхмш. \proclaim Ренпелю~D. Еякх~$m=10^e$, $e\ge 5$, $c=0$ х~$X_0$ ме йпюрмн~$2$ хкх~$5$, оепхнд кхмеимни йнмцпсщмрмни онякеднбюрекэмнярх пюбем~$5\times10^{e-2}$ б рнл х рнкэйн рнл яксвюе, йнцдю~$a \bmod 200$ опхмхлюер ндмн %% 35 хг якедсчыху $32$~гмювемхи: $$ \eqalign{ & 3,11,13,19,21,27, 29, 37, 53,59, 61, 67, 69,77, 83,91,109,117,\cr & 123,131,133,139,141,147,163,171,173,179,181,187,189.197.~\endmark\cr } \eqno(10) $$ \excercises \ex[10] Йюйнбю дкхмю оепхндю кхмеимни йнмцпсщмрмни онякеднбюрекэмнярх я~$X_0=5772156648$, $a=3141592621$, $c=2718281829$, $m=10000000000$? \ex[10] Цюпюмрхпсер кх бшонкмемхе якедсчыху дбсу сякнбхи: (i)~$c$~мевермне, (ii)~$a\bmod 4=1$, люйяхлюкэмсч дкхмс оепхндю, йнцдю~$m=2^e$, р.~е.\ яреоемэ дбнийх? \ex[13] Опедонкнфхл, врн~$m=10^e$, цде~$e\ge 3$, ю~$c$ ме йпюрмн мх~$2$, мх~$5$. Онйюфхре, врн кхмеимюъ йнмцпсщмрмюъ онякеднбюрекэмнярэ асдер хлерэ люйяхлюкэмн анкэьни оепхнд рнцдю х рнкэйн рнцдю, йнцдю~$a\bmod 20=1$. \ex[20] Велс пюбмн гмювемхе~$X_{2^{e-1}}$, еякх~$a$ х~$c$ сднбкербнпъчр сякнбхъл ренпелш~A, $m=2^e$, $X_0=0$? \rex[20] Мюидхре бяе лмнфхрекх~$a$, сднбкербнпъчыхе сякнбхъл ренпелш~A, йнцдю~$m=2^{35}+1$ (опнярше лмнфхрекх вхякю~$m$ лнфмн мюирх хг рюак.~3.2.1.1-1). \ex[20] Мюидхре бяе лмнфхрекх~$a$, сднбкербнпъчыхе сякнбхъл ренпелш~A, опх~$m=10^6-1$ (ял.~рюак.~3.2.1.1-1). \rex[Л24] Оепхнд йнмцпсщмрмни онякеднбюрекэмнярх ме наъгюрекэмн мювхмюрэ я~$X_0$. Ндмюйн лш бяецдю лнфел мюирх хмдейяш~$\mu\ge0$, $\lambda>0$, рюйхе, врн~$X_{n+\lambda}=X_n$ дкъ кчашу~$n\ge\mu$, опхвел~$\mu$ х~$\lambda$---мюхлемэьхе гмювемхъ, накюдючыхе щрхл ябниярбнл. (Яп.~я~соп.~3.1-6 х~3.2.1-1.) Осярэ~$\mu_j$, $\lambda_j$ яннрберярбсчр онякеднбюрекэмнярх~$(X_0 \bmod p_j^{e_j}, a \bmod p_j^{e_j}, c \bmod p_j^{e_j}, p_j^{e_j})$ х~$\mu$, $\lambda$ яннрберярбсчр онякеднбюрекэмнярх~$(X_0, a, c, p_1^{e_1}\ldots p_t^{e_t})$; келлю~Q сярюмюбкхбюер, врн $\lambda$~еярэ мюхлемэьее наыее йпюрмне дкъ~$\lambda_1$,~\dots, $\lambda_t$. Велс пюбмн гмювемхе~$\mu$, бшпюфеммне вепег~$\mu_1$,~\dots, $\mu_t$? Йюйне люйяхлюкэмне гмювемхе~$\mu$ лнфмн онксвхрэ, хглемъъ~$X_0$, $a$ х~$c$ опх тхйяхпнбюммнл~$m=p_1^{e_1}\ldots p_t^{e_t}$? \ex[Л20] Онйюфхре, врн еякх~$a \bmod 4=3$, $e>1$, рн~$(a^{2^{e-1}}-1)/(a-1) \equiv 0 \pmod{2^e}$. (Хяонкэгсире келлс~P.) \rex[Л22] (С.~Рнлянм.) Дкъ~$c=0$ х~$m=2^e\ge 8$ ренпелш~B х~C србепфдючр, врн дкхмю оепхндю пюбмю~$2^{e-2}$ б рнл х рнкэйн рнл яксвюе, йнцдю лмнфхрекэ~$a$ сднбкербнпъер яннрмньемхъл~$a\bmod 8=3$ хкх~$a \bmod 8=5$. Онйюфхре, врн йюфдюъ рюйюъ онякеднбюрекэмнярэ б ясымнярх ъбкъеряъ кхмеимни йнмцпсщмрмни онякеднбюрекэмнярэч я~$m=2^{e-2}$, хлечыеи \emph{онкмши} оепхнд б якедсчыел ялшяке: \medskip \item{a)}~еякх~$X_{n+1}=(4c+1) X_n \bmod 2^e$ х~$X_n=4Y_n+1$, рн $$ Y_{n+1}=((4c+1) Y_n+c) \bmod 2^{e-2}; $$ \item{b)}~еякх~$X_{n+1}=(4c-1)X_n \bmod 2^e$ х~$X_n=((-1)^n (4Y_n+1)) \bmod 2^e$, рн $$ Y_{n+1}=((1-4c)Y_n-c)\bmod 2^{e-2}. $$ [\emph{Гюлевюмхе.} Б щрху тнплскюу~$c$---мевермне жекне. Б кхрепюрспе лнфмн бярперхрэ србепфдемхъ н рнл, врн онякеднбюрекэмнярх я~$c=0$, сднбкербнпъчыхе %% 36 сякнбхъл ренпелш~B, меяйнкэйн анкее яксвюимш, вел ре, йнрнпше сднбкербнпъчр сякнбхъл ренпелш Ю, меялнрпъ мю рн, врн б яксвюе ренпелш~B оепхнд б вершпе пюгю лемэье. Щрн сопюфмемхе нопнбепцюер онднамше србепфдемхъ.] \ex[Л21] Дкъ йюйху гмювемхи~$m$ яопюбедкхбн пюбемярбн~$\lambda(m)=\varphi(m)$? \ex[Л28] Осярэ~$x$---мевермне жекне вхякн, анкэьее~$1$. % \hiddenpar (a)~Онйюфхре, врн ясыеярбсер едхмярбеммне жекне~$f>1$, рюйне, врн $x\equiv 2^f \pm 1 \pmod{2^{f+1}}$. % \hiddenpar (b)~Опх сякнбхх, врн~$11$, рн~$a$---оепбннапюгмши щкелемр он лндскч~$p^e$ б рнл х рнкэйн рнл яксвюе, йнцдю~$a$---оепбннапюгмши щкелемр он лндскч~$p$ х~$a^{p-1}\equiv 1 \pmod{p^2}$. (Опедонкнфхре, врн~$\lambda(p^e)=p^{e-1}(p-1)$. Щрн днйюгшбюеряъ мхфе б соп.~14 х~16. \ex[Л22] Осярэ~$p$---опнярне вхякн х~$a$ ме ъбкъеряъ оепбннапюгмшл щкелемрнл он лндскч~$p$. Онйюфхре, врн кхан~$a$ йпюрмн~$p$ кхан~$a^{(p-1)/q}\equiv 1 \pmod{p}$ дкъ мейнрнпнцн опнярнцн вхякю~$q$, декъыецн~$p-1$. \ex[Л18] Осярэ~$e>1$, $p$---мевермне опнярне х~$a$---оепбннапюгмши щкелемр он лндскч~$p$, днйюфхре, врн рнцдю кхан~$a$, кхан~$a+p$---оепбннапюгмши щкелемр он лндскч~$p^e$. [\emph{Сйюгюмхе:} ял.~соп.~12.] \ex[Л29] (a)~Осярэ~$a_1$, $a_2$ бгюхлмн опнярше я~$m$. Осярэ дкъ щрху вхяек онпъдйх он лндскч~$m$ пюбмш~$\lambda_1$, $\lambda_2$ яннрберярбеммн. Днйюфхре врн еякх~$\lambda$---мюхлемэьее наыее йпюрмне~$\lambda_1$ х~$\lambda_2$, рн~$a_1^{\kappa_1}a_2^{\kappa_2}$ хлеер онпъднй~$\lambda$ он лндскч~$m$ дкъ бшапюммшу мюдкефюыхл напюгнл~$\kappa_1$, $\kappa_2$. [\emph{Сйюгюмхе}. Пюяялнрпхре ямювюкю яксвюи, йнцдю~$\lambda_1$ х~$\lambda_2$---бгюхлмн опнярше вхякю.] (b)~Осярэ~$\lambda(m)$---люйяхлюкэмши он бяел щкелемрюл онпъднй он лндскч~$m$. Днйюфхре, врн~$\lambda(m)$ йпюрмн онпъдйс он лндскч~$m$ дкъ кчанцн щкелемрю. Дпсцхлх якнбюлх, днйюфхре, врн~$a^{\lambda(m)} \equiv 1 \pmod{m}$ дкъ кчанцн~$a$, бгюхлмн опнярнцн я~$m$. \rex[Л24] Осярэ~$p$---опнярне вхякн. (a)~Осярэ~$f(x)=x^n+c_1 x^{n-1}+\cdots+c_n$, цде бяе~$c$---жекше вхякю, х гюдюмн рюйне жекне~$a$, врн~$f(a) \equiv 0 \pmod{p}$. Онйюфхре, врн ясыеярбсер онкхмнл~$q(x)=x^n+q_1x^{n-2}+\cdots+q_{n-1}$ я жекшлх йнщттхжхемрюлх, рюйни, врн~$f(x)\equiv (x-a)q(x) \pmod{p}$ дкъ бяеу жекшу~$x$. (b)~Осярэ~$f(x)$---онкхмнл, рaйни фe, йaй х б~(a). Оoйюфхре, врн~$f(x)$ хлеер яюлне анкэьее $n$~пюгкхвмшу "йнпмеи" он лндскч~$p$, р.е.\ ясыеярбсер яюлне анкэьее $n$~жекшу вхяек~$a$, рюйху, врн~$f(a)\equiv 0 \pmod{p}$, $0\le a < p$. (c)~Б соп.~15(b) србепфдюеряъ, врн онкхмнл~$f(x)=x^{\lambda(p)}-1$ хлеер $p-1$~пюгкхвмшу йнпмеи; якеднбюрекэмн, ясыеярбсер жекне~$a$ я онпъдйнл~$p-1$. \ex[Л26] Ме бяе гмювемхъ, оепевхякеммше б ренпеле~D лнфмн онксвхрэ лернднл, хгкнфеммшл б рейяре. Мюопхлеп, вхякн~$11$ ме ъбкъеряъ оепбннапюгмшл щкелемрнл он лндскч~$5^e$. Йюй щрн лнфер ашрэ еякх~$11$ (б яннрберярбхх я ренпелни~D)---оепбннапюгмши щкелемр он лндскч~$10^e$? Йюйхе хг вхяек, оепевхякеммшу б ренпеле~D,---оепбннапюгмше щкелемрш йюй он лндскч~$2^e$, рюй х~$5^e$? \ex[Л25] Днйюфхре ренпелс~D. (Яп.\ я опедшдсыхл сопюфмемхел.) \ex[40] Янярюбэре рюакхжс мейнрнпшу унпньху лмнфхрекеи~$a$ дкъ йюфднцн хг гмювемхи~$m$, оепевхякеммшу б рюак.~3.2.1.1-1, б опедонкнфемхх~$c=0$. \ex[Л24] Йюйнбю дкхмю оепхндю кхмеимни йнмцпсщмрмни онякеднбюрекэмнярх, дкъ йнрнпни (i)~$X_0=0$; (ii)~$a$---оепбннапюгмши щкелемр он лндскч~$p_j^{e_j}$, $1\le i \le t$; дкъ бяеу яреоемеи опняршу вхяек б пюгкнфемхх~$m=p_1^{e_1}\ldots p_t^{e_t}$ мю опнярше лмнфхрекх; (iii)~$c$ х~$m$ бгюхлмн опнярш? \subsubsubchap{Лнымнярэ\note{1}% {Б нпхцхмюке "potency",--- {\sl Опхл. оепеб.\/}}}%3.2.1.3 Б опедшдсыел пюгдеке лш онйюгюкх, врн люйяхлюкэмши оепхнд лнфмн онксвхрэ опх~$b=a-1$, йпюрмнл %% 37 бяел опняршл декхрекъл вхякю~$m$ ($b$ рюйфе днкфмн ашрэ йпюрмн~$4$, еякх $m$~декхряъ мю~$4$). Еякх~$z$---нямнбюмхе, йнрнпне хяонкэгсеряъ б люьхме (рюй, $z=2$---дкъ дбнхвмни люьхмш х~$z=10$---дкъ деяърхвмни), ю~$m$---пюглеп якнбю~$z^e$ люьхмш, рн лмнфхрекэ $$ a=z^k+1, \rem{$2\le k < e$,} \eqno(1) $$ сднбкербнпъер щрхл сякнбхъл. Хг ренпелш~3.2.1.2.A рюйфе якедсер, врн лнфмн опхмърэ~$c=1$. Пейсппемрмне яннрмньемхе реоепэ хлеер бхд $$ X_{n+1}=((z^k+1)X_n+1) \bmod z^e. \eqno(2) $$ Опх бшвхякемхъу лнфмн хгаефюрэ слмнфемхъ; днярюрнвмн опнярнцн якнфемхъ х ядбхцю. Мюопхлеп, опедонкнфхл, врн~$a=B^2+1$, цде~$B$---пюглеп аюирю \MIX. Блеярн йнлюмд, опхбедеммшу б~о.3.2.1.1, лнфмн мюохяюрэ рюйсч опнцпюллс: $$ \vcenter{ \mixcode LDA & X SLA & 2 ADD & X INCA & 1 \endmixcode } \eqno(3) $$ Бпелъ ее бшонкмемхъ слемэьюеряъ я~$16u$ дн~$7u$. Ббхдс яйюгюммнцн лмнфхрекх бхдю~(1) ьхпнйн наясфдюкхяэ б кхрепюрспе х пейнлемднбюкхяэ лмнцхлх юбрнпюлх. Ндмюйн онврх оърхкермхе опнбепнвмше щйяоепхлемрш онйюгшбючр, врн \emph{якедсер хгаецюрэ лмнфхрекеи, хлечыху рюйни опнярни бхд, йюй~(1)}. Опхвхм гдеяэ меяйнкэйн. Опефде бяецн бпелъ яверю ме слемэьюеряъ мю яюлнл деке бдбне, йюй щрн опнхяундхр б опхлепе~(3). Еякх днаюбхрэ й опнцпюлле йнлюмдш~|JMP|, |STJ|, |STA|, |JNOV|, япюбмхрекэмше бпелемю яверю асдср пюбмш~$22u$ дкъ лскэрхокхйюрхбмнцн лерндю х~$13u$ дкъ лерндю, хяонкэгсчыецн якнфемхе х ядбхц. Йпнле щрнцн, менаундхлн свеярэ бпелъ пюанрш нямнбмни опнцпюллш, хяонкэгсчыеи яксвюимше вхякю. Вхярюъ щйнмнлхъ люьхммнцн бпелемх б опнжемрюу онврх мхврнфмю. Ю мю лмнцху янбпелеммшу люьхмюу слмнфемхе бшонкмъеряъ \emph{ашярпее,} вел ядбхц х якнфемхе! Яюлши беяйхи юпцслемр, опеоърярбсчыхи хяонкэгнбюмхч лмнфхрекъ бхдю~$z^k+1$, гюйкчвюеряъ б рнл, врн нм опхбндхр й меднярюрнвмн яксвюимшл вхякюл. Ндмю хг опхвхм щрнцн ябъгюмю я йнмжеожхеи "лнымнярх", йнрнпсч лш яеивюя наясдхл. \dfn{Лнымнярэ} кхмеимни йнмцпсщмрмни онякеднбюрекэмнярх я люйяхлюкэмшл оепхнднл нопедекъеряъ йюй мюхлемэьее жекне вхякн~$s$, рюйне, врн $$ b^s \equiv 0 \pmod{m}. \eqno(4) $$ %% 38 (Рюйне жекне~$s$ бяецдю ясыеярбсер, еякх лмнфхрекэ сднбкербнпъер сякнбхъл ренпелш~3.2.1.2A, б вюярмнярх, еякх $b$~йпюрмн кчанлс опнярнлс декхрекч~$m$.) Лш лнфел юмюкхгхпнбюрэ яксвюимнярэ онякеднбюрекэмнярх, опхмхлюъ~$X_0=0$, рюй йюй мскэ наъгюрекэмн бярпевюеряъ мю опнръфемхх ее оепхндю. Б рюйнл яксвюе хлеел~$X_n=((a^n-1)c/b)\bmod m$ х, пюгкнфхб~$a^n-1=(b+1)^n-1$ он тнплске ахмнлю, мюундхл $$ X_n=c\left(n+\perm{n}{2}b+\cdots+\perm{n}{s}b^{s-1}\right) \bmod m. \eqno(5) $$ Бяе вкемш я~$b^s$, $b^{s+1}$ х р.~д.\ лнфмн носярхрэ, рюй йюй нмх йпюрмш~$m$. Хяундъ хг спюбмемхъ~(5), пюяялнрпхл мейнрнпше вюярмше яксвюх. Еякх~$a=1$, лнымнярэ пюбмю~$1$ х, йюй лш сфе бхдекх, $X_n \equiv cn \pmod{m}$, рюй врн онякеднбюрекэмнярэ ъбмн ме яксвюимюъ. Еякх лнымнярэ пюбмю~$2$, хлеел~$X_n \equiv cn+cb\perm{n}{2}$, х ямнбю онякеднбюрекэмнярэ мекэгъ явхрюрэ яксвюимни. Деиярбхрекэмн, $$ X_{n+1}-X_n \equiv c+cbn, $$ рюй врн пюгмнярэ лефдс яняедмхлх яксвюимшлх вхякюлх бшпюфюеряъ нвемэ опнярни гюбхяхлнярэч нр~$n$. Еякх $$ d=cb \bmod m, $$ рнвйю~$(X_n, X_{n+1}, X_{n+2})$ бяецдю кефхр мю ндмни хг вершпеу окняйняреи б рпеулепмнл опнярпюмярбе: $$ \eqalign{ x-2y+z &= d+m,\cr x-2y+z &= d,\cr x-2y+z &= d-m,\cr x-2y+z &=d-2m.\cr } $$ Еякх лнымнярэ пюбмю~$3$, онякеднбюрекэмнярэ бшцкъдхр меяйнкэйн анкее яксвюимни. Мн~$X_n$, $X_{n+1}$, х~$X_{n+2}$ бяе еые ябъгюмш яхкэмни гюбхяхлнярэч. Пюгмнярх~$X_{n+1}-X_n$ напюгсчр онякеднбюрекэмнярэ я лнымнярэч~$2$, х реярш онйюгшбючр, врн онякеднбюрекэмнярх я лнымнярэч~$3$ бяе еые меднярюрнвмн унпньх. Яннаыюкняэ, врн опхелкелше пегскэрюрш лнцср ашрэ онксвемш дкъ гмювемхъ лнымнярх, пюбмнцн~$4$ х бшье, мн щрн няоюпхбюкняэ лмнцхлх юбрнпюлх. Бхдхлн, дкъ днярюрнвмн яксвюимшу гмювемхи рпеасеряъ лнымнярэ, пюбмюъ он лемэьеи лепе~$5$. Опедонкнфхл, мюопхлеп, врн~$m=2$ х~$a=2^k+1$. Рнцдю~$b=2^k$, рюй врн опх~$k \ge 18$ гмювемхе~$b^2=2^{2k}$ йпюрмн~$m$: лнымнярэ пюбмю~$2$. Еякх~$k=17$, $16$,~\dots, $12$, лнымнярэ пюбмю~$3$, ю опх~$k=11$, $10$, $9$ днярхцюеряъ гмювемхе~$4$. Онщрнлс я рнвйх гпемхъ лнымнярх едхмярбеммн опхелкелш рюйхе лмнфхрекх, дкъ йнрнпшу~$k\le 8$. %% 39 Щрн гмювхр, врн~$a\le 257$, ю лш сбхдхл онгфе, врн \emph{меанкэьху} лмнфхрекеи рюйфе якедсер хгаецюрэ. Хрюй, бяе лмнфхрекх бхдю~$2^k+1$ опх~$m=2^{35}$ нйюгшбючряъ меопхелкелшлх. Опх анкэьху пюглепюу якнбю лмнфхрекх бхдю~$2^k+1$ опхмърэ лнфмн. Ашк хяошрюм х нохяюм б кхрепюрспе дюрвхй я~$m=2^{47}$, $a=2^9+1$ х лнымнярэч, пюбмни~$6$ ({\sl CACM,\/} {\bf 4} (1961), 350--352). Меялнрпъ мю щрн, мюдн ашрэ нвемэ нярнпнфмшл я лмнфхрекълх рхою~(1), онрнлс врн онврх бяе хгбеярмше мемюдефмше дюрвхйх ашкх хлеммн рюйнцн рхою. Б деиярбхрекэмнярх дюфе опхбедеммши опхлеп ме сднбкербнпъер ярюрхярхвеяйхл реярюл о.3.3.4. Опх~$m$, пюбмнл~$w\pm1$, цде~$w$---пюглеп якнбю, $m$, бннаые цнбнпъ, ме пюгкюцюеряъ мю опнхгбедемхъ бшянйху яреоемеи опняршу вхяек, рюй врн анкэьюъ лнымнярэ мебнглнфмю (ял.\ опхлеп~6). Онщрнлс б щрнл яксвюе \emph{ме} ярнхр онкэгнбюрэяъ лернднл люйяхлюкэмнцн оепхндю, ю якедсер опхлемърэ лернд вхярнцн слмнфемхъ я~$c=0$. Бяе еые нярюеряъ лмнцн ябнандш б бшанпе лмнфхрекъ. Бннаые цнбнпъ, лш унрхл янупюмхрэ лнымнярэ бшянйни, лмнфхрекэ днярюрнвмн анкэьхл х, йпнле рнцн, хгаефюрэ якхьйнл опнярнцн он бхдс мюанпю жхтп б лмнфхреке. Опедонкнфхл, врн~$m=2^{35}$, ю ноепюжхъ слмнфемхъ сяйнпъеряъ опх слемэьемхх йнкхвеярбю "едхмхвмшу" ахрнб б лмнфхреке. Лнфмн пейнлемднбюрэ (щйяоепхлемрюкэмн) рюйни лмнфхрекэ, йюй~$2^{23}+2^{14}+2^2+1$. Вкем~$2^{23}$ декюер лмнфхрекэ днбнкэмн анкэьхл. Вкем~$2^2$ наеяоевхбюер бшянйсч лнымнярэ. Едхмхжю менаундхлю дкъ онксвемхъ люйяхлюкэмнцн оепхндю, ю $2^{14}$~днаюбкъеряъ, врнаш лмнфхрекэ ме нйюгюкяъ якхьйнл опняршл дкъ бшпюанрйх днярюрнвмн яксвюимни онякеднбюрекэмнярх (яп.~соп.~8). Вкем, онднамши~$2^{34}$, ашк аш гдеяэ ме ярнкэ унпнь, йюй~$2^{23}$, рюй йюй б опнхгбедемхх~$2^{34}X_n$ хяонкэгсеряъ рнкэйн яюлши лкюдьхи ахр вхякю~$X_n$ (йнрнпши ме якхьйнл яксвюем). Еякх яйнпнярэ слмнфемхъ ме ъбкъеряъ кхлхрхпсчыеи, анкее "яксвюимши" лмнфхрекэ (мюопхлеп, $a=3141592621$), бепнърмн, нйюферяъ гмювхрекэмн анкее сднбкербнпхрекэмшл. Б деиярбхрекэмнярх йнмжеожхъ лнымнярх дюер рнкэйн ндхм хг йпхрепхеб бшанпю лмнфхрекъ; й мелс лнфмн днаюбхрэ мелюкн дпсцху. Мхфе, б о.3.3.4, наясфдюеряъ "яоейрпюкэмши реяр" дкъ лмнфхрекеи кхмеимшу йнмцпсщмрмшу онякеднбюрекэмняреи. Щрн---бюфмши йпхрепхи, бйкчвючыхи, йюй вюярмше яксвюх, лнымнярэ х бекхвхмс лмнфхрекъ. Б о.3.3.4 лш, мюопхлеп, сбхдхл, врн бшанп~$2^{23}+2^{13}+2^2+1$ мюлмнцн усфе, вел~$2^{23}+2^{14}+2^2+1$. Кчани лмнфхрекэ, йнрнпши асдер ьхпнйн хяонкэгнбюрэяъ, якедсер опнбепхрэ яоейрпюкэмшл реярнл. \excercises \ex[M10] Онйюфхре, врн мегюбхяхлн нр рнцн, йюйхл нйюферяъ пюглеп аюирю~$B$ люьхмш \MIX, опнцпюллю~(3) яксфхр дюрвхйнл яксвюимшу вхяек я люйяхлюкэмшл оепхнднл. %% 40 \ex[10] Йюйнбю лнымнярэ дюрвхйю, пеюкхгнбюммнцн \MIX-опнцпюллни~(3)? \ex[11] Йюйнбю лнымнярэ кхмеимни йнмцпсщмрмни онякеднбюрекэмнярх опх~$m=2^{35}$, $a=3141592621$? Велс пюбмю лнымнярэ, еякх лмнфхрекэ~$a=2^{23}+2^{13}+2^2+1$? \ex[20] Онйюфхре, врн, еякх~$m=2^e\ge 8$, люйяхлюкэмюъ лнымнярэ днярхцюеряъ опх~$a \bmod 8 = 5$. \ex[M20] Дюмн, врн~$m=p_1^{e_1}\ldots p_t^{e_t}$ х~$a=1+kp_1^{f_1}\ldots p_t^{f_t}$, цде~$a$ сднбкербнпъер сякнбхъл ренпелш~3.2.1.2A, ю~$k$ х~$m$ бгюхлмн опнярш. Онйюфхре, врн лнымнярэ пюбмю~$\max(\ceil{e_1/f_1},~\ldots, \ceil{e_t/f_t})$. \rex[20] Йюйхе хг гмювемхи~$m=w\pm1$ б рюак.~3.2.1.1-1 лнцср дюрэ лнымнярэ, пюбмсч он лемэьеи лепе~$4$? (Хяонкэгсире пегскэрюр соп.~5.) \ex[Л20] Еякх вхякн~$a$ сднбкербнпъер сякнбхъл ренпелш~3.2.1.2A, нмн бгюхлмн опнярн я~$m$; якеднбюрекэмн, ясыеярбсер вхякн~$a'$, рюйне, врн~$aa'\equiv 1 \pmod{m}$. Онйюфхре, врн~$a'$ лнфмн опнярн бшпюгхрэ я онлныэч~$b$. \rex[Л26] Дюрвхй яксвюимшу вхяек я~$X_{n+1}=(2^{17}+3)X_n \bmod 2^{35}$ х~$X_0=1$ ондбепцкх якедсчыелс реярс. Осярэ~$Y_n=\floor{10X_n/2^{35}}$, рнцдю~$Y_n$ днкфмю ашрэ яксвюимни жхтпни лефдс~$6$ х~$9$, ю рпхюдш~$(Y_{3n}, Y_{3n+1}, Y_{3n+2})$ днкфмш опхмхлюрэ кчане хг $1000$~бнглнфмшу гмювемхи нр~$(0, 0, 0)$ дн~$(9, 9, 9)$ я пюбмни бепнърмнярэч. Мн б $30\,000$~опнбепеммшу вхяек мейнрнпше рпхюдш бярпевюкхяэ нвемэ педйн, ю мейнрнпше онъбкъкхяэ цнпюгдн вюые дпсцху. Лнфере кх бш на╝ъямхрэ рюйни ярпюммши пегскэрюр? \subsubchap{Дпсцхе лерндш} %3.2.2 Йнмевмн, кхмеимше йнмцпсщмрмше онякеднбюрекэмнярх---ме едхмярбеммши хг опедкнфеммшу дкъ бшвхякхрекэмшу люьхм хярнвмхйнб яксвюимшу вхяек. Б щрнл осмйре лш опхбедел нагнп дпсцху мюханкее бюфмшу лернднб. Мейнрнпше хг мху днярюрнвмн бюфмш рнцдю йюй дпсцхе опедярюбкъчр хмрепея кхьэ онярнкэйс, оняйнкэйс нйюгшбючряъ янбяел ме рюйхлх унпньхлх, йюй йюфсряъ мю оепбши бгцкъд. Ндмн хг наыеопхмършу гюаксфдемхи, я йнрнпшлх опхундхряъ ярюкйхбюрэяъ, йнцдю певэ хдер н онксвемхх яксвюимшу вхяек гюйкчвюеряъ б рнл, врн днярюрнвмн бгърэ унпньхи дюрвхй х якецйю ецн хглемхрэ, врнаш бшпюанрюрэ "еые анкее яксвюимсч" онякеднбюрекэмнярэ. Днбнкэмн вюярн щрн мебепмн. Мюопхлеп, лш гмюел врн он тнплске $$ X_{n+1}=(aX_n+c) \bmod m \eqno(1) $$ лнфмн онксвхрэ днбнкэмн унпньхе яксвюимше вхякю Ме асдер кх онякеднбюрекэмнярэ $$ X_{n+1}=((aX_n) \bmod (m+1)+c) \bmod m \eqno(2) $$ еые анкее яксвюимни? Нрбер рюйнб, врн мнбюъ онякеднбюрекэмнярэ я анкэьеи бепнърмнярэч \emph{лемее} яксвюимю. Гюлерхл, врн жекнярмюъ ренпхъ дкъ мее псьхряъ, ю б нрясрярбхе йюйни-кхан ренпхх н онбедемхъ онякеднбюрекэмнярх~(2) лш оноюдюел б накюярэ дюрвхйнб. рхою~$X_{n+1}=f(X_n)$ ян яксвюимн бшапюммни тсмйжхеи~$f$. Блеяре я рел соп.~3.1-11--3.1-15 онйюгшбючр, врн щрх онякеднбюрекэмнярх %% 41 бедср яеаъ янбяел ме рюй унпньн, йюй еякх аш тсмйжхъ~(1) ашкю верйн нопедекемю. Пюяялнрпхл дпсцни ондунд, ошрюъяэ цемепхпнбюрэ "анкее яксвюимше" вхякю. Кхмеимши йнмцпсщмрмши лернд лнфмн нанаыхрэ, опебпюрхб ецн, яйюфел, б йбюдпюрхвмши йнмцпсщмрмши лернд: $$ X_{n+1}=(dX_n^2+aX_n+c) \bmod m. \eqno(3) $$ Б соп.~8 нанаыюеряъ ренпелю~3.2.1.2A я жекэч онксвхрэ менаундхлше х днярюрнвмше сякнбхъ дкъ~$a$, $c$ х~$d$, рюйхе, врнаш онякеднбюрекэмнярэ, нопедекеммюъ яннрмньемхел~(3), хлекю аш люйяхлюкэмши оепхнд~$m$. Нцпюмхвемхъ нйюгшбючряъ ме анкее феярйхлх, вел б кхмеимнл лернде. Дкъ яксвюъ, йнцдю $m$~опедярюбкъеряъ яреоемэч дбнийх, хмрепеямши йбюдпюрхвмши лернд опедкнфхк П.~Йнбщч. Осярэ $$ X_0 \bmod 4 =2, \quad X_{n+1}=X_n(X_n+1) \bmod 2^e, \rem{$n\ge 0$.} \eqno(4) $$ Щрс онякеднбюрекэмнярэ лнфмн бшвхякърэ онврх я рни фе щттейрхбмнярэч, йюй х~(1), ме гюанръяэ н оепеонкмемхх. Нмю хлеер хмрепеямсч ябъгэ я оепбнмювюкэмшл лернднл яепедхмш йбюдпюрю тнм Меилюмю. Бнгэлел~$Y_n$, пюбмне~$2^eX_n$, рюй врн~$Y_n$---вхякн, опедярюбкеммне я дбнимни рнвмнярэч осрел опхохяшбюмхъ яопюбю $e$~мскеи дбнхвмнлс опедярюбкемхч~$X_n$. Рнцдю~$Y_{n+1}$ янярнхр б рнвмнярх хг $2e$~япедмху жхтп вхякю~$Y_n^2+2^eY_n$! Рюйхл напюгнл, лернд Йнбщч онврх хдемрхвем лерндс яепедхмш йбюдпюрю я дбнимни рнвмнярэч, я рни пюгмхжеи, врн нм цюпюмрхпсер анкэьни оепхнд. Лнфмн опхбеярх х дюкэмеиьхе днйюгюрекэярбю яксвюимнярх онксвюелни онякеднбюрекэмнярх (ял. соп. 3.3.4-25). Дпсцхе нанаыемхъ яннрмньемхъ~(1) рюйфе днбнкэмн нвебхдмш. Мюопхлеп, лш лнцкх аш оношрюрэяъ сбекхвхрэ оепхнд онякеднбюрекэмнярх. Оепхнд кхмеимни йнмцпсщмрмни онякеднбюрекэмнярх впегбшвюимн бекхй. Нашвмн, еякх $m$~опхакхфюеряъ й пюглепс люьхммнцн якнбю, лш хлеел декн я оепхндюлх онпъдйю~$10^9$ х анкэье, рюй врн б рхохвмшу гюдювюу хяонкэгсеряъ рнкэйн нвемэ люкюъ вюярэ онякеднбюрекэмнярх. Я дпсцни ярнпнмш, бекхвхмю оепхндю бкхъер мю яреоемэ яксвюимнярх, йнрнпюъ днярхцюеряъ б онякеднбюрекэмнярх (ял.\ гюлевюмхъ, опхбедеммше оняке яннрмньемхъ~3.3.4-13). Онщрнлс нашвмн лш ярпелхляъ онксвюрэ анкэьни оепхнд, дкъ вецн х ясыеярбсер пъд лернднб. Б ндмнл хг мху ббндхряъ гюбхяхлнярэ~$X_{n+1}$ нр~$X_n$ х~$X_{n-1}$ блеярн опнярни гюбхяхлнярх рнкэйн нр~$X_n$. Рнцдю дкхмс оепхндю лнфмн сбекхвхрэ дн~$m^2$, рюй йюй онякеднбюрекэмнярэ мювмер онбрнпърэяъ ме пюмэье, вел асдер бшонкмемн пюбемярбн~$(X_{n+\lambda}, X_{n+\lambda+1})=(X_n, X_{n+1})$. Опняреиьхи яксвюи гюбхяхлнярх~$X_{n+1}$ нр анкее вел ндмнцн хг опедшдсыху гмювемхи пеюкхгсеряъ б онякеднбюрекэмнярх Тханмюввх $$ X_{n+1}=(X_n+X_{n-1}) \bmod m. \eqno (5) $$ %% 42 Щрнр дюрвхй пюяялюрпхбюкяъ б мювюке оърхдеяършу цнднб. Нм дюер нашвмн дкхмс оепхндю, анкэьсч, вел~$m$. Ндмюйн реярш я нопедекеммнярэч онйюгюкх, врн вхякю, онксвюелше хг яннрмньемхъ Тханмюввх~(5), ъбкъчряъ \emph{меднярюрнвмн} яксвюимшлх. Онщрнлс б мюярнъыее бпелъ тнплскю~(5) хмрепеямю цкюбмшл напюгнл йюй опейпюямши "окнуни опхлеп". Лнфмн рюйфе пюяялнрперэ дюрвхйх бхдю $$ X_{n+1}=(X_n+X_{n-k}) \bmod m, \eqno(6) $$ цде~$k$---днярюрнвмн анкэьне вхякн, опедкнфеммше Цпхмнл, Ялхрнл х Йкелнл (Green, Smith, Klem, {\sl JACM,\/} {\bf 6} (1959), 527--537). Опх яннрберярбсчыел бшанпе~$X_0$, $X_1$,~\dots, $X_k$ щрю тнплскю наеыюер ярюрэ хярнвмхйнл унпньху яксвюимшу вхяек. Мю оепбши бгцкъд яннрмньемхе~(6) бшцкъдхр ме якхьйнл сднамшл дкъ хяонкэгнбюмхъ б люьхме, рел ме лемее ясыеярбсер нвемэ щттейрхбмюъ опнжедспю дкъ ее пеюкхгюжхх. \alg A.(Юддхрхбмши дюрвхй вхяек.) Ямювюкю б ъвеийх~$Z$, $Y[0]$, $Y[1]$,~\dots, $Y[k]$ гюмняъряъ яннрберярбеммн гмювемхъ~$X_k$, $X_k$, $X_{k-1}$,~\dots, $X_0$, ю $j$~опхмхлюеряъ пюбмшл~$k$. Онякеднбюрекэмне хяонкэгнбюмхе юкцнпхрлю опхбндхр й онксвемхч онякеднбюрекэмнярх~$X_{k+1}$, $X_{k+2}$, $\ldots\,$. \st[$j<0$?] Еякх~$j<0$, сярюмнбхрэ~$j\asg k$. \st[Опхаюбхрэ, гюлемхрэ.] Сярюмнбхрэ~$Z\asg Y[j] \asg (Z+Y[j]) \bmod m$. \st[Слемэьхрэ~$j$.] Слемэьхрэ~$j$ мю~$1$, бшдюрэ~$Z$. \algend Щрнр юкцнпхрл мю ъгшйе~\MIX{} бшцкъдхр рюй (опх сякнбхх, врн хмдейямши пецхярп~6 ме хяонкэгсеряъ б нямнбмни опнцпюлле): $$ \vcenter{ \mixcode J6NN & *+2 & A1. $j<0$? ENT6 & K & Сярюмнбхрэ~$j\asg k$. LDA & Z & A2. Опхаюбхрэ, гюлемхрэ. ADD & Y, 6 & $Z+Y[j]$ (бнглнфмн оепеонкмемхе) STA & Y, 6 & $\rasg Y[j]$. STA & Z & $\rasg Z$. DEC6 & 1 & A3. Слемэьхрэ~$j$. \endmixcode } \eqno(7) $$ Щрнр дюрвхй пюанрюер нашвмн ашярпее, вел дюрвхйх, пеюкхгсчыхе опедшдсыхе лерндш, рюй йюй гдеяэ ме рпеасеряъ мхйюйнцн слмнфемхъ. Яеивюя н рюйнл юддхрхбмнл дюрвхйе хгбеярмн мелмнцн. Опефде вел ецн лнфмн асдер пейнлемднбюрэ, якедсер пюгбхрэ ренпхч, онгбнкъчысч сярюмнбхрэ менаундхлше онйюгюрекх яксвюимнярх бшпюаюршбюелшу вхяек, х опнбеярх ьхпнйхе хяошрюмхъ дкъ нрдекэмшу гмювемхи~$k$ х~$X_0$, $X_1$,~\dots, $X_k$. Дкхмю оепхндю наясфдюеряъ б соп.~11; бннаые цнбнпъ, нмю ме мюлмнцн анкэье~$m$. Б ярюрэе %% 43 Цпхмю, Ялхрю х Йкелю цнбнпхряъ, врн опх~$k\le 15$ онякеднбюрекэмнярэ ме сднбкербнпъер реярс "опнбепйю хмрепбюкнб", нохяюммнлс б о.~3.3.2, унръ опх~$k=16$ реяр опнундхр мнплюкэмн. Ясыеярбсер онунфхи, мн цнпюгдн анкее щттейрхбмши яоняна сксвьемхъ яксвюимнярх кхмеимшу йнмцпсщмрмшу онякеднбюрекэмняреи, еякх~\emph{$m$---опнярне вхякн.} Мюопхлеп, $m$~лнфмн бшапюрэ йюй яюлне анкэьне опнярне вхякн, йнрнпне лнфмн гюохяюрэ б люьхммнл якнбе. Рюйне вхякн лнфмн бшвхякхрэ гю опхелкелне бпелъ, опхлемъъ реумхйс о.~4.5.4. Йнцдю~$m=p$---опнярне вхякн, хг ренпхх йнмевмшу онкеи якедсер, врн ясыеярбсчр рюйхе лмнфхрекх~$a_1$,~\dots, $a_k$, врн онякеднбюрекэмнярэ, нопедекеммюъ тнплскни $$ X_n=(a_1X_{n-1}+\cdots+a_kX_{n-k}) \bmod p, \eqno(8) $$ хлеер оепхнд дкхмш~$p^k-1$. Гдеяэ~$X_0$,~\dots, $X_{k-1}$ лнцср ашрэ бшапюмш опнхгбнкэмн, мн ме днкфмш ашрэ бяе пюбмш мскч. (Вюярмши яксвюи~$k=1$ яннрберярбсер лскэрхокхйюрхбмни йнмцпсщмрмни онякеднбюрекэмнярх он опнярнлс лндскч, я йнрнпни лш сфе гмюйнлш.) Бшанп онярнъммшу~$a_1$,~\dots, $a_k$ б~(8) рнцдю х рнкэйн рнцдю дюер фекюелши пегскэрюр, йнцдю онкхмнл $$ f(x)=x^k-a_1x^{k-1}-\cdots-a_k \eqno(9) $$ ъбкъеряъ \dfn{"опхлхрхбмшл лмнцнвкемнл он лндскч~$p$",} р.~е.\ хлеер йнпемэ, ъбкъчыхияъ \emph{оепбннапюгмшл щкелемрнл онкъ хг~$p^k$} щкелемрнб\note{1}% {Щрнр щкелемр---напюгсчыюъ лскэрхокхйюрхбмни цпсоош онкъ Цюксю, йнрнпюъ, йюй хгбеярмн, жхйкхвмю.--- {\sl Опхл. пед.\/}} (ял. соп. 4.6.2-16). Йнмевмн, опнярни тюйр \emph{ясыеярбнбюмхъ} ондундъыху йнмярюмр~$a_1$,~\dots, $a_k$, наеяоевхбючыху дкхмс оепхндю~$p^k-1$, меднярюрнвем дкъ опюйрхвеяйху жекеи. Лш днкфмш слерэ \emph{мюундхрэ} ху, ме оепеахпюъ бяе $p^k$~бюпхюмрнб, рюй йюй $p$~хлеер онпъднй пюглепю люьхммнцн якнбю. Й явюярэч, ясыеярбсер б рнвмнярх~$\varphi(p^k-1)/k$ ондундъыху йнлахмюжхи~$(a_1,~\ldots, a_k)$, рюй врн хлееряъ днбнкэмн анкэьни ьюмя намюпсфхрэ ндмс хг мху оняке меяйнкэйху яксвюимшу оношрнй. Мн, йпнле бяецн опнвецн, мюл мсфмн слерэ ашярпн нопедекхрэ, ъбкъеряъ кх~(9) опхлхрхбмшл лмнцнвкемнл он лндскч~$p$. Янбепьеммн мелшякхлн бшпюаюршбюрэ $p^k-1$~щкелемрнб онякеднбюрекэмнярх б нфхдюмхх онбрнпемхъ! Лерндш опнбепйх рнцн, ъбкъеряъ кх лмнцнвкем опхлхрхбмшл он лндскч~$p$, наясфдюкхяэ Щкюмемнл х Ймсрнл (Alanen, Knuth, {\sl Sankhy\=a\/}, Ser.~A, {\bf 26} (1964), 305--328). Лнфмн хяонкэгнбюрэ якедсчыхи йпхрепхи. Осярэ~$r=(p^k-1)/(p-1)$. \medskip \item{i)}~Бекхвхмю~$(-1)^{k+1}a_k$ днкфмю ашрэ оепбннапюгмшл йнпмел он лндскч~$p$ (яп.~о.~3.2.1.2). \item{ii)}~Онкхмнл~$x^r$ днкфем ашрэ япюбмхл я~$(-1)^{k+1}a_k$ он лндскч~$f(x)$ х~$p$. %% 44 \item{iii)}~Яреоемэ~$x^{r/q} \bmod f(x)$, цде ондпюгслебюеряъ онкхмнлхюкэмюъ юпхтлерхйю он лндскч~$p$, днкфмю ашрэ онкнфхрекэмни дкъ бяъйнцн опнярнцн декхрекъ~$q$ вхякю~$r$. \medskip \noindent Щттейрхбмше лерндш бшвхякемхъ~$x^n \bmod f(x)$, хяонкэгсчыхе онкхмнлхюкэмсч юпхтлерхйс он лндскч опнярнцн~$p$, наясфдючряъ б~о.~4.6.2. Врнаш ядекюрэ рюйсч опнбепйс, мюл мсфмн гмюрэ тюйрнпхгюжхч~$r=(p^k-1)/(p-1)$ я онлныэч опняршу вхяек. Щрн нцпюмхвхбюер бнглнфмнярх бшвхякемхи. Гю опхелкелне бпелъ лнфмн тюйрнпхгнбюрэ~$r$ опх~$k=2$, $3$ х, лнфер ашрэ, $4$, мн я анкэьхлх гмювемхълх~$k$, еякх $p$~бекхйн, рпсдмн хлерэ декн. Дюфе опх~$k=2$ вхякн "гмювхлшу яксвюимшу жхтп" сдбюхбюеряъ он япюбмемхч я~$k=1$. Онщрнлс анкэьхе гмювемхъ~$k$ педйн менаундхлш. Дкъ нжемйх онякеднбюрекэмнярх вхяек, онксвюелшу я онлныэч~(8), лнфмн бняонкэгнбюрэяъ бюпхюмрнл яоейрпюкэмнцн реярю, нохяюммшл б о.~3.3.4 (ял.~соп.~3.3.4-26). Хг хгкнфеммнцн б щрнл осмйре якедсер, врн \emph{межекеяннапюгмн} нцпюмхвхбюрэяъ нвебхдмшлх гмювемхълх~$a_1=+1$ хкх~$a_1=-1$, дюфе еякх щрн бнглнфмн. Ксвье бгърэ анкэьхе, ясыеярбеммн "яксвюимше" вхякю~$a_1$,~\dots, $a_k$, сднбкербнпъчыхе сякнбхъл, ю гюрел опнбепхрэ бшанп я онлныэч яоейрпюкэмнцн реярю. Дкъ нопедекемхъ~$a_1$,~\dots, $a_k$, рпеасеряъ опнбеярх лмнцн бшвхякемхи, мн еярэ бяе нямнбюмхъ явхрюрэ, врн б пегскэрюре лш онксвхл беяэлю сднбкербнпхрекэмши хярнвмхй яксвюимшу вхяек. Нянаши хмрепея опедярюбкъер гмювемхе~$p=2$. Хмнцдю ашбюер мсфем дюрвхй, онпнфдючыхи яксвюимсч онякеднбюрекэмнярэ \emph{ахрнб}---мскеи х едхмхж (б нркхвхе нр дпнаеи, опхмхлючыху гмювемхъ нр мскъ дн едхмхжш). Ясыеярбсер опнярни яоняна бшпюаюршбюрэ мю дбнхвмни люьхме я $k\hbox{-пюгпъдмшлх}$ якнбюлх беяэлю яксвюимсч онякеднбюрекэмнярэ ахрнб. Мювхмюел я опнхгбнкэмнцн дбнхвмнцн якнбю~$|Y|=(Y_1 Y_2 \ldots Y_k)_2$, нркхвмнцн нр мскъ. Врнаш онксвхрэ нвепедмни яксвюимши ахр онякеднбюрекэмнярх, опндекюел якедсчыхе ноепюжхх, гюохяюммше мю ъгшйе~\MIX: $$ \vcenter{ \mixcode LDA & Y & (Опедонкюцюел, врн яхцмюк оепеонкмемхъ бшйкчвем.) ADD & Y & Ядбхц бкебн мю ндхм пюгпъд. JNOV & *+2 & Оепеунд, еякх б ярюпьел пюгпъде бмювюке ашк мскэ. XOR & C & Б опнрхбмнл яксвюе йнппейрхпсел вхякн ноепюжхеи "хяйкчвючыее хкх". STA & Y \endmixcode } \eqno(10) $$ Вербепрюъ он онпъдйс ноепюжхъ, "хяйкчвючыее хкх", хлееряъ онврх мю бяеу дбнхвмшу люьхмюу (яп.~соп.~2.5-28). Нмю хглемъер гмювемхе йюфднцн пюгпъдю, яннрберярбсчыецн рнлс, цде |C|~яндепфхр едхмхжс, мю напюрмне. Б ъвеийе~|C| мюундхряъ дбнхвмюъ %% 45 йнмярюмрю~$(a_1\ldots{}a_k)_2$, нопедекъчыюъ опхлхрхбмши лмнцнвкем он лндскч~$2$: $x^k-a_1x^{k-1}-\cdots-a_k$. Оняке бшонкмемхъ опнцпюллш~(10) б лкюдьел пюгпъде~|Y| яндепфхряъ якедсчыхи ахр онякеднбюрекэмнярх (еякх щрн анкее сднамн, лнфмн, мюнанпнр, хяонкэгнбюрэ ярюпьхи пюгпъд~|Y|). Пюяялнрпхл б йювеярбе опхлепю пхя.~1, хккчярпхпсчыхи $$\matrix{ 1011\cr 0101\cr 1010\cr 0111\cr 1110\cr 1111\cr 1101\cr 1001\cr 0001\cr 0010\cr 0100\cr 1000\cr 0011\cr 0110\cr 1100\cr 1011\cr } $$ %% Щрю люрпхжю х еярэ йюпрхмйю. \picture{ Пхя.~1. Онякеднбюрекэмше янярнъмхъ люьхммнцн якнбю~|Y| опх хяонкэгнбюмхх дбнхвмнцн лерндю дкъ~$k=4$ х $c=|CONTENTS|(|C|)= (0011)_2$. } онксвемхе онякеднбюрекэмнярх опх~$k=4$, $c=(0011)_2$ (щрн, йнмевмн, меярюмдюпрмн люкне гмювемхе~$k$). Опюбши ярнкаеж рюакхжш опедярюбкъер онякеднбюрекэмнярэ ахрнб, йнрнпюъ онбрнпъеряъ я оепхнднл~$2^k-1=15$: $1101011110001001\ldots\,$. Онякеднбюрекэмнярэ днярюрнвмн яксвюимюъ, еякх свеярэ, врн нмю онксвемю я онлныэч вершпеу пюгпъднб оюлърх. Врнаш саедхрэяъ б щрнл, пюяялнрпхл яняедмхе вербепйх ахрнб, онъбкъчыхеяъ мю опнръфемхх оепхндю, ю хлеммн: $1101$, $1010$, $0101$, $1011$, $0111$, $1111$, $1110$, $1100$, $1000$, $0001$, $0010$, $0100$, $1001$, $0011$, $0110$. Бннаые цнбнпъ, рюй йюй дкхмю оепхндю пюбмю~$2^k-1$, йюфдюъ бнглнфмюъ йнлахмюжхъ $k$~ахрнб бярпевюеряъ гю оепхнд рнвмн ндхм пюг, гю хяйкчвемхел мюанпю хг бяеу мскеи. Рюйхл напюгнл, яняедмхе мюанпш хг $k$~ахрнб ясыеярбеммн мегюбхяхлш. Б \S~3.5 лш сбхдхл, врн ясыеярбсер нвемэ лнымши йпхрепхи яксвюимнярх дкъ~$k$, пюбмнцн, яйюфел, $30$ хкх анкэье. Ренперхвеяйхе пегскэрюрш, хккчярпхпсчыхе яксвюимнярэ щрни онякеднбюрекэмнярх, опхбндъряъ б ярюрэе П.~Рюсябнпрю (R.~Я.~Tausworthe, {\sl Math. Comp.,\/} {\bf 19} (1965), 201--209). Опхлхрхбмше лмнцнвкемш яреоемх~$\le 100$ он лндскч~$2$ ашкх опнрюаскхпнбюмш Щ.~Снрянмнл (Е.~J.~Watson, {\sl Math. Comp.,\/} {\bf 16} (1962), 368--369). Опх~$k=35$ лнфмн опхмърэ $$ c = (00000000000000000000000000000000101)_2, $$ %% 46 ю дкъ~$k=30$ лнфмн бгърэ $$ c=(000000000000000000000001010011)_2. $$ Бяе фе, йюй якедсер хг соп.~18 х~3.3.4-26, дкъ нопедекемхъ опхлхрхбмшу лмнцнвкемнб он лндскч~$2$ ксвье мюундхрэ ясыеярбеммн "яксвюимше" йнмярюмрш~$c$. \emph{Опедсопефдемхе:} Мейнрнпше оноюдюкхяэ б кнбсьйс, ошрюъяэ хяонкэгнбюрэ лернд бшпюанрйх яксвюимшу онякеднбюрекэмняреи ахрнб дкъ онксвемхъ яксвюимшу дпнаеи, гюмхлючыху жекне якнбн~$(.Y_0Y_1\ldots{}Y_{k-1})_2$, $(.Y_kY_{k+1}\ldots{}Y_{2k-1})_2$,~$\ldots\,$. Мю яюлнл деке щрн днбнкэмн окнуни яоняна, унръ нрдекэмше ахрш йюфдни дпнах бонкме яксвюимш (ял.~соп.~18)! Лш сфе бхдекх, врн, йнцдю~$X_n$ нопедекъеряъ ондундъыеи тсмйжхеи нр~$X_{n-1}$,~\dots, $X_{n-k}$, лнфмн мюирх рюйхе онякеднбюрекэмнярх я~$0\le X_n < m$ х оепхнднл~$m^k-1$, цде~$m$---опнярне вхякн. Мюханкэьхи оепхнд, йнрнпши лнфмн онксвхрэ дкъ \emph{опнхгбнкэмни} онякеднбюрекэмнярх, нопедекеммни яннрмньемхел $$ X_n=f(X_{n-1}, \ldots, X_{n-k}), \rem{$0\le X_n < m$,} \eqno(11) $$ йюй лнфмн бхдерэ, пюбем~$m^k$. Л.~Люпрхм (Л.~H.~Martin {\sl Bull. Amer. Math. Soc.,\/} {\bf 40} (1934), 859--864) оепбши онйюгюк, врн ясыеярбсчр тсмйжхх, онгбнкъчыхе днярхвэ щрнцн люйяхлслю дкъ кчашу~$m$ х~$k$. Ецн лернд кецйн нанямнбюрэ, мн, й янфюкемхч, нм месднаем дкъ опнцпюллхпнбюмхъ (ял.~соп.~17). Хг хгбеярмшу тсмйжхи~$f$, дючыху люйяхлюкэмши оепхнд~$m^k$, яюлни опнярни ъбкъеряъ нохяюммюъ б соп.~21. Яннрберярбсчыхе опнцпюллш, бннаые цнбнпъ, ме рюй щттейрхбмш дкъ бшпюанрйх яксвюимшу вхяек, йюй опх пеюкхгюжхх дпсцху пюмее нохяюммшу лернднб. Бяе фе нмх онгбнкъчр опнделнмярпхпнбюрэ ъбмсч яксвюимнярэ онякеднбюрекэмнярх (йнцдю певэ хдер н оепхнде б жекнл). Дпсцни бюфмши йкюяя лернднб ябндхряъ й \emph{йнлахмюжхх} дюрвхйнб яксвюимшу вхяек дкъ онксвемхъ "еые анкее яксвюимшу" онякеднбюрекэмняреи. Бяецдю мюидсряъ яйеорхйх, онкюцючыхе, врн кхмеимше йнмцпсщмрмше лерндш, юддхрхбмше лерндш х р.~д.\ якхьйнл опнярш дкъ бшпюанрйх днярюрнвмн яксвюимшу онякеднбюрекэмняреи. Ю рюй йюй мебнглнфмн \emph{днйюгюрэ,} врн ху яйеорхжхгл менопюбдюм (унръ лш х бепхл, врн щрн рюй), днбнкэмн аеяонкегмн няоюпхбюрэ онднамне лмемхе. Ясыеярбсчр бонкме щттейрхбмше лерндш дкъ рнцн, врнаш онксвюрэ хг дбсу онякеднбюрекэмняреи мюярнкэйн яксвюимсч рперэч, врн рнкэйн яюлшл нр╝ъбкеммшл яйеорхйюл нмю лнфер ме онмпюбхрэяъ. Опедонкнфхл, врн лш хлеел дбе онякеднбюрекэмнярх~$X_0$, $X_1$,~\dots, х~$Y_0$, $Y_1$,~\dots, яксвюимшу вхяек, пюяонкнфеммшу лефдс мскел х~$m-1$, онксвеммше дбслъ мегюбхяхлшлх яонянаюлх. Ндмн хг опедкнфемхи ябндхряъ й рнлс, врнаш яйкюдшбюрэ вхякю оноюпмн он %% 47 лндскч~$m$, онксвюъ онякеднбюрекэмнярэ~$Z_n=(X_n+Y_n)\bmod m$. Б щрнл яксвюе фекюрекэмн, врнаш дкхмш оепхнднб~$\$ х~$\$ ашкх бгюхлмн опняршлх вхякюлх (ял.~соп.~13). Лернд, опедкнфеммши Люйкюпемнл х Люпяюкэеи гмювхрекэмн ксвье х сдхбхрекэмн сднаем дкъ опнцпюллхпнбюмхъ. \alg M.(Бонкме яксвюимюъ онякеднбюрекэмнярэ.) Опх гюдюммшу лерндюу бшпюанрйх дбсу онякеднбюрекэмняреи~$\$ х~$\$ щрнр лернд онгбнкъер цемепхпнбюрэ вкемш "гмювхрекэмн анкее яксвюимни" онякеднбюрекэмнярх. Лш хяонкэгсел бяонлнцюрекэмсч рюакхжс~$V[0]$, $V[1]$,~\dots, $V[k-1]$, цде~$k$---мейнрнпне вхякн, бшахпюелне нашвмн дкъ сднаярбю пюбмшл опхлепмн~$100$. Ямювюкю $V\hbox{-рюакхжю}$ гюонкмъеряъ оепбшлх $k$~гмювемхълх $X\hbox{-онякеднбюрекэмнярх}$. \st[Бшпюанрюрэ~$X$, $Y$.] Сярюмнбхрэ б~$X$ х~$Y$ гмювемхъ нвепедмшу вкемнб онякеднбюрекэмняреи~$\$ х~$\$ яннрберярбеммн. \st[Бшвхякхрэ~$j$.] Сярюмнбхрэ~$j\asg \floor{kY/m}$, цде~$m$---лндскэ, хяонкэгсчыхияъ б онякеднбюрекэмнярх~$\$. Рюйхл напюгнл, $j$~опхмхлюер яксвюимне гмювемхе, нопедекъелне я онлныэч~$Y$; $0 \le j $ х~$\$ бгюхлмн опнярше. Х дюфе еякх дкхмю оепхндю ме нвемэ ясыеярбеммю, яняедмхе вкемш онякеднбюрекэмнярх онврх ме йнппекхпсчр дпсц я дпсцнл. Опхвхмни рнцн, врн щрнр лернд мюлмнцн опебняундхр лернд яепедхмш йбюдпюрю хкх лернд, нямнбюммши мю яннрмньемхх~(2), ъбкъеряъ днярюрнвмюъ яксвюимнярэ онякеднбюрекэмняреи~$X_n$ х~$Y_n$, йнрнпше ме лнцср бшпнфдюрэяъ. Вхрюрекч пейнлемдсеряъ пюгнапюрэ соп.~3, врнаш сбхдерэ, йюй лернд пюанрюер б вюярмнл яксвюе. Мю люьхме~\MIX{} лнфмн пеюкхгнбюрэ юкцнпхрл~M, опхмхлюъ~$k$ мю едхмхжс анкэьхл люйяхлюкэмнцн гмювемхъ, пюглеыючыецняъ б ндмнл аюире (пюбмшл пюглепс аюирю). Ьюцх~M2 х~M3 кецйн опнцпюллхпсчряъ якедсчыхл напюгнл: $$ \vcenter{ \mixcode LD6 & Y(l:l) & $j\asg \hbox{ярюпьхи аюир } Y$. LDA & V, 6 & $|rA|\asg \hbox{якедсчыхи щкелемр мнбни онякеднбюрекэмнярх.}$ LDX & У STX & V,6 & $V[j]\asg X$. \endmixcode } \eqno(12) $$ Дкъ опхлепю опедонкнфхл, врн юкцнпхрл~M опхлемъеряъ й рюйхл дбсл онякеднбюрекэмняръл я~$k=64$: $$ \matrix{ X_0=5772156649, & X_{n+1}=(3141592653 X_n + 2718281829) \bmod 2^{35};\cr Y_0=1781072418, & Y_{n+1}=(2718281829 Y_n + 3141592653) \bmod 2^{35}.\cr } $$ %% 48 Лш србепфдюел, врн онякеднбюрекэмнярэ, онксвеммюъ я онлныэч юкцнпхрлю~M, асдер сднбкербнпърэ тюйрхвеяйх \emph{кчанлс} йпхрепхч яксвюимнярх дкъ цемепхпселшу бшвхякхрекэмни люьхмни онякеднбюрекэмняреи. Анкее рнцн, бпелъ бшпюанрйх всрэ анкэье вел бдбне опебшьюер бпелъ онксвемхъ ндмни онякеднбюрекэмнярх~$$. Т.~Цеауюпдр онйюгюк [F.~Gebhardt, {\sl Math. Comp.,\/} {\bf 21} (1967),708--709], врн юкцнпхрл~M онгбнкъер онксвюрэ сднбкербнпхрекэмше пегскэрюрш, дюфе еякх ецн опхлемърэ й рюйхл меяксвюимшл онякеднбюрекэмняръл, йюй онякеднбюрекэмнярэ Тханмюввх я~$X_n=F_2 \bmod m$ х~$Y_n=F_{2n+1} \bmod m$. Дпсцни яоняна йнлахмхпнбюрэ дбе онякеднбюрекэмнярх нямнбюм мю жхйкхвеяйнл ядбхце х "хяйкчвючыел хкх" б дбнхвмни люьхме. Ецн опедкнфхк С.~Сщяркщий (W.~J.~Westlake, {\sl JACM,\/} {\bf 14} (1967), 337--340). \excercises \rex[12] Опюйрхвеяйх лш онксвюел яксвюимше вхякю, онкэгсъяэ яннрмньемхел~$X_{n+1}=(aX_n+c) \bmod m$, цде~$X_n$---\emph{жекше.} Оняке вецн лш напюыюеляъ я мхлх, йюй я \emph{дпнаълх:} $U_n=X_n/m$. Пейсппемрмюъ тнплскю дкъ~$U_n$ б деиярбхрекэмнярх рюйнбю: $$ U_{n+1}=(aU_n+c/m) \bmod 1. $$ Надслюире \emph{опълне} хяонкэгнбюмхе щрни тнплскш дкъ бшпюанрйх яксвюимшу онякеднбюрекэмняреи я онлныэч ноепюжхи я окюбючыеи рнвйни, хлечыхуяъ б люьхме. \rex[Л20] Дкъ унпньецн хярнвмхйю яксвюимшу вхяек яннрмньемхе~$X_{n-1}$ х~$\$ ме якхьйнл яксвюимш.) \ex[00] Онвелс б оепбни йнлюмде опнцпюллш~(12) хяонкэгсеряъ хлеммн ярюпьхи аюир, ю ме йюйни-мхасдэ дпсцни? \rex[20] Пюяялнрпхре бнглнфмнярэ хяонкэгнбюмхъ сякнбхъ~$X_n=Y_n$ дкъ сяйнпемхъ пюанрш юкцнпхрлю~M. \ex[10] Б рейяре опх хяякеднбюмхх дбнхвмнцн лерндю~(10) србепфдюеряъ, врн лкюдьхи ахр якнбю~$X$ яксвюем, еякх лмнцнйпюрмн опхлемърэ щрнр лернд. Онвелс ме яксвюимн бяе \emph{якнбн}~$X$? \ex[20] Онйюфхре, врн лнфмн онксвхрэ онкмсч онякеднбюрекэмнярэ дкхмш~$2^e$ (р.~е.\ йюфдши хг $2^e$~бнглнфмшу бюпхюмрнб яняедмху $e$~ахрнб, йнрнпши пеюкхгсеряъ рнкэйн ндхм пюг мю опнръфемхх оепхндю), еякх хглемхрэ опнцпюллс~(10) якедсчыхл напюгнл: %% !!! Меопхърмюъ ьрсйю: рюй йюй акнй \mixcode бундхр б юпцслемр люйпняю \ex, %% ецн рнйемш онксвючр йюрецнпхч, дн рнцн, йюй б \mixcode опнхгнидер %% бшонкмемхе \obeylines. Б хрнце йнмжш ярпнй ме явхрючряъ \cr ? Йюй щрн ядекюрэ? $$ \vcenter{ \mixcode LDA & У \cr JANZ & *+2 \cr LDA & C \cr ADD & X \cr JNOV & *+3 \cr JAZ & *+2 \cr XOR & C \cr STA & X \cr \endmixcode } $$ %% 49 \ex[M39] Днйюфхре, врн йбюдпюрхвмюъ йнмцпсщмрмюъ онякеднбюрекэмнярэ~$(3)$ хлеер оепхнд дкхмш~$m$ рнцдю х рнкэйн рнцдю, йнцдю бшонкмъчряъ якедсчыхе сякнбхъ: \medskip \item{i)}~$c$ х~$m$---бгюхлмн опнярше вхякю; \item{ii)}~$d$ х~$a-1$ йпюрмш~$p$---бяел мевермшл опняршл декхрекъл~$m$; \item{iii)}~$d$---вермне х~$d\equiv a-1\pmod{4}$, еякх~$m$ йпюрмн~$4$, $d\equiv a-1 \pmod{2}$, еякх~$m$ йпюрмн~$2$; \item{iv)}~хкх~$d=0$, хкх~$a\equiv 1$ х~$cd\equiv 6\pmod{9}$, еякх~$m$ йпюрмн~$9$. [\emph{Сйюгюмхе.} Онякеднбюрекэмнярэ, нопедекеммюъ яннрмньемхълх~$X_0=0$, $X_{n+1}=dX_n^2+aX_n+c$, хлеер он лндскч~$m$ оепхнд дкхмш~$m$, еякх рнкэйн щрю дкхмю оепхндю пюбмю~$d$ он лндскч~$d$, цде~$d$---опнхгбнкэмши декхрекэ~$m$.] \rex[Л24] (П.~Йнбщч.) Хяонкэгсире пегскэрюр соп.~8, врнаш днйюгюрэ, врн б лндхтхжхпнбюммнл лернде яепедхмш йбюдпюрю~(4) дкхмю оепхндю пюбмю~$2^{e-2}$. \ex[Л29] Онйюфхре, врн еякх~$X_0$ х~$X_1$ ме ъбкъчряъ наю вермшлх х~$m=2^e$, рн оепхнд онякеднбюрекэмнярх Тханмюввх~(5) пюбем~$3\cdot 2^{e-1}$. \ex[Л36] Гюдювю щрнцн сопюфмемхъ янярнхр б рнл, врнаш опнюмюкхгхпнбюрэ нопедекеммше ябниярбю жекнвхякеммшу онякеднбюрекэмняреи, сднбкербнпъчыху пейсппемрмнлс яннрмньемхч $$ X_n=a_1X_{n-1}+\cdots+a_kX_{n-k}, \rem{$n\ge k$.} $$ Еякх лш лнфел бшвхякхрэ дкхмс оепхндю щрни онякеднбюрекэмнярх он лндскч~$m=p^e$, цде~$p$---опнярне вхякн, рн дкхмю оепхндю нрмняхрекэмн опнхгбнкэмнцн лндскъ~$m$ пюбмю мюхлемэьелс наыелс йпюрмнлс дкхм оепхнднб, бшвхякеммшу нрмняхрекэмн яреоемеи опняршу янлмнфхрекеи~$m$. \medskip % \item{a)}~Осярэ~$f(z)$, $a(z)$, $b(z)$)---онкхмнлш я жекнвхякеммшлх йнщттхжхемрюлх; асдел охяюрэ~$a(z)\equiv b(z) \pmod{f(z)\hbox{ х } m}$, еякх~$a(z)=b(z)+f(z)u(z)+mv(z)$ дкъ мейнрнпшу онкхмнлнб~$u(z)$, $v(z)$ я жекнвхякеммшлх йнщттхжхемрюлх. Днйюфхре, врн опх~$f(0)=1$ х~$p^e>2$ яопюбедкхбн якедсчыее: "еякх~$z^\lambda\equiv 1 \pmod{f(z)\hbox{ х }p^e}$, $z^\lambda\not\equiv 1\pmod{f(z)\hbox{ х }p^{e+1}}$, рнцдю~$z^{p\lambda}\equiv 1 \pmod{f(z)\hbox{ х }p^{e+1}}$, $z^{p\lambda}\not\equiv 1 \pmod{f(z)\hbox{ х } p^{e+2}}$". % \item{b)}~Осярэ $$ \eqalign{ f(z)&=1-a_1z-\cdots-a_kz^k,\cr G(z)&=1/f(z)=A_0+A_1z+A_2z^2+\ldots\,.\cr } $$ Нангмювхл яхлбнкнл~$\lambda(m)$ дкхмс оепхндю онякеднбюрекэмнярх~$\$. Днйюфхре, врн~$\lambda(m)$---мюхлемэьее онкнфхрекэмне жекне~$\lambda$, рюйне, врн~$z^\lambda\equiv 1 \pmod{f(z)\hbox{ х } m}$. % \item{c)}~Осярэ~$p$---опнярне, $p^e>2$ х~$\lambda(p^e)\ne \lambda(p^{e+1})$. Днйюфхре, врн~$\lambda(p^{e+r})=p^r\lambda(p^e)$ дкъ бяеу~$r\ge0$. (Рюйхл напюгнл, врнаш мюирх дкхмс оепхндю онякеднбюрекэмнярх~$\$, лнфмн бшвхякърэ~$\lambda(4)$, $\lambda(8)$, $\lambda(16)$,~\dots{} бпсвмсч дн реу онп, онйю лш ме мюидел мюхлемэьее~$r\ge2$, рюйне, врн~$\lambda(2^{r+1})\ne\lambda(4)$. Рнцдю дкхмю оепхндю нопедекемю он~$\bmod 2^e$ дкъ бяеу~$e$.) % \item{d)}~Онйюфхре, врн кчаюъ онякеднбюрекэмнярэ жекшу вхяек, сднбкербнпъчыюъ пейсппемрмнлс яннрмньемхч, опхбедеммнлс б мювюке сопюфмемхъ, хлеер опнхгбндъысч тсмйжхч~$g(z)/f(z)$, цде~$g(z)$---мейнрнпши онкхмнл я жекнвхякеммшлх йнщттхжхемрюлх. % \item{e)}~Осярэ онкхмнлш~$f(z)$ х~$g(z)$ хг~(d) бгюхлмн опнярше он лндскч~$p$ (яп.~о.~4.6.1). Днйюфхре, врн онякеднбюрекэмнярэ~$\$ хлеер дкхмс оепхндю б рнвмнярх рюйсч фе, йюй х яоежхюкэмюъ онякеднбюрекэмнярэ~$\$ б~(b). (Мхйюйхл бшанпнл~$X_0$,~\dots, $X_{k-1}$ мекэгъ онксвхрэ анкее дкхммши оепхнд, рюй йюй наыюъ онякеднбюрекэмнярэ опедярюбкъеряъ кхмеимни йнлахмюжхеи "ядбхцнб" яоежхюкэмни онякеднбюрекэмнярх.) [\emph{Сйюгюмхе.} Ясыеярбсчр онкхмнлш, рюйхе, врн~$a(z)f(z)+b(z)g(z)\equiv 1 \pmod{p^e}$. Щрн якедсер хг соп.~4.6.2-22 (келлю Цемгекъ).] \rex[Л28] Мюидхре жекше вхякю~$X_0$, $X_1$, $a$, $b$ х~$c$, рюйхе, врн онякеднбюрекэмнярэ $$ X_{n+1}=(aX_n+bX_{n-1}+c)\bmod 2^e, \rem{$n\ge 1$,} $$ %% 50 хлеер яюлши анкэьни оепхнд хг бяеу онякеднбюрекэмняреи щрнцн рхою. [\emph{Сйюгюмхе.} $X_{n+2}=((a+1)X_{n+1}+(b-a)X_n-bX_{n-1})\bmod 2^e$ Ял.~соп.~11~(c).] \ex[Л20] Осярэ~$\$ х~$\$--- онякеднбюрекэмнярх жекшу вхяек он лндскч~$m$ я оепхндюлх дкхмш~$\lambda_1$ х~$\lambda_2$; напюгсел мнбсч онякеднбюрекэмнярэ~$Z_n=(X_n+Y_n)\bmod m$. Онйюфхре, врн, еякх~$\lambda_1$ х~$\lambda_2$---бгюхлмн опнярше вхякю, онякеднбюрекэмнярэ~$\$ хлеер дкхмс оепхндю~$\lambda_1\lambda_2$. \ex[Л24] Осярэ~$X_n$, $Y_n$, $Z_n$, $\lambda_1$, $\lambda_2$, рюйхе фе, йюй х б опедшдсыел сопюфмемхх. Опедонкнфхл, врн~$\lambda_1=2^{e_2}3^{e_3}5^{e_5}\ldots$---пюгкнфемхе~$\lambda_1$ мю опнярше лмнфхрекх, х юмюкнцхвмн~$\lambda_2=2^{f_2}3^{f_3}5^{f_5}\ldots\,$. Осярэ~$\lambda_0=2^{g_2}3^{g_3}5^{g_5}\ldots$, цде~$g_p=(\max(e_p, f_p)$, еякх~$e_p\ne f_p$, х~$0$, еякх~$e_p=f_p$). Онйюфхре, врн оепхнд~$\lambda'$ онякеднбюрекэмнярх~$Z_n$ йпюрем~$\lambda_0$, мн ъбкъеряъ декхрекел~$\lambda$---мюхлемэьецн наыецн йпюрмнцн~$\lambda_1$, $\lambda_2$. Б вюярмнярх, $\lambda'=\lambda$, еякх $(e_p\ne f_p \ror e_p=f_p=0)$ дкъ бяъйнцн опнярнцн~$p$. \ex[Л46] Врн лнфмн яйюгюрэ он онбндс дкхмш оепхндю онякеднбюрекэмнярх, бшпюаюршбюелни юкцнпхрлнл~M? \rex[Л28] Осярэ дбнхвмне опедярюбкемхе йнмярюмрш~$c$, тхцспхпсчыеи б лернде~(10), хлеер бхд~$(a_1 a_2 \ldots a_k)_2$. Онйюфхре, врн онякеднбюрекэмнярэ ахрнб~$Y_0$, $Y_1$,~\dots{} сднбкербнпъер яннрмньемхч $$ Y_n=(a_1Y_{n-1}+a_2Y_{n-2}+\cdots+a_kY_{n-k}) \bmod 2. $$ [Щрo лнфмн пюяялюрпхбюрэ йюй дпсцни яоняна нопедекемхъ онякеднбюрекэмнярх. унръ мю оепбши бгцкъд ябъгэ лефдс щрхл яннрмньемхел х щттейрхбмни опнцпюллни~(10) ме нвебхдмю!] \ex[Л33] (Л.~Люпрхм, 1934.) Осярэ~$m, k\ge 1$---жекше вхякю х~$X_1=X_2=\ldots=X_k=0$. Дкъ~$n>0$ онкнфхл~$X_{n+k}$ пюбмшл мюханкэьелс менрпхжюрекэмнлс гмювемхч~$y$ ме сднбкербнпъер реярс~3.3.2D опх~$d=8$. \ex[M41] Мюидхре дкъ йюфднцн опнярнцн~$p$ хг оепбнцн ярнкажю рюак.~1 б о.~4.5.4 ондундъыхе (б ялшяке, сйюгюммнл б рейяре) йнмярюмрш~$a_1$, $a_2$, рюйхе, врн дкхмю оепхндю~(8) опх~$k=2$ пюбмю~$p^2-1$. \ex[Л40] Бшвхякхре йнмярюмрш~$c$, сднамше дкъ хяонкэгнбюмхъ ху б лернде~(10), хлечыхе опхлепмн ндхмюйнбне вхякн мскеи х едхмхж, дкъ~$1\le k \le 64$. \ex[Л35] (Д. Пхя.) Б рейяре на╝ъямъеряъ, йюй мюундхрэ тсмйжхх~$f$, рюйхе, врн с онякеднбюрекэмнярх~(11) дкхмю оепхндю пюбмю~$m^k-1$ опх сякнбхх, врн~$m$---опнярне вхякн, ю~$X_0$,~\dots, $X_{k-1}$ нркхвмш нр мскъ. Онйюфхре, врн щрх тсмйжхх лнфмн лндхтхжхпнбюрэ, врнаш онксвхрэ онякеднбюрекэмнярх бхдю~(11) %% 51 я дкхмни оепхндю~$m^k$ дкъ \emph{бяеу}~$m$. [\emph{Сйюгюмхе.} Бняонкэгсиреяэ келлни~3.2.1.2Q, хяйсяярбеммшл опхелнл соп.~7 х онякеднбюрекэмнярълх бхдю~$\$.] \rex[Л24] Б рейяре наясфдемхе нанаыеммшу кхмеимшу онякеднбюрекэмняреи~(8) нцпюмхвхбюеряъ яксвюел, йнцдю~$m$---опнярне вхякн. Днйюфхре, врн днярюрнвмн анкэьхе оепхндш лнфмн онксвхрэ, йнцдю~$m$ "ябнандмн нр йбюдпюрнб", р.~е.\ опедярюбкъеряъ б бхде опнхгбедемхъ пюгкхвмшу опняршу вхяек. (Опнбепйю рюак.~3.2.1.1-1 онйюгшбюер, врн~$m=w\pm1$ вюярн сднбкербнпъер щрни цхонреге. Лмнцхе пегскэрюрш, онксвеммше б рейяре, лнфмн онщрнлс опхлемърэ х б щрнл яксвюе, меяйнкэйн анкее сднамнл дкъ бшвхякемхи.) %% 52 \subchap{ЯРЮРХЯРХВЕЯЙХЕ РЕЯРШ} % 3.3 Мюью нямнбмюъ гюдювю янярнхр б онксвемхх онякеднбюрекэмняреи, йнрнпше онунфх мю яксвюимше. Лш сфе бхдекх, йюй днахрэяъ рюйнцн анкэьнцн оепхндю онякеднбюрекэмнярх, врнаш б опюйрхвеяйху гюдювюу хяйкчвхрэ бнглнфмнярэ ее онбрнпемхъ. Унръ щрн х бюфмн, мн анкэьни оепхнд еые бнбяе ме нгмювюер, врн онякеднбюрекэмнярэ унпнью дкъ пюанрш. Йюй фе пеьюрэ, днярюрнвмн кх яксвюимю онякеднбюрекэмнярэ? Еякх дюрэ кчанлс векнбейс йюпюмдюь х аслюцс х онопняхрэ ецн мюохяюрэ 100~яксвюимшу деяърхвмшу жхтп, нвемэ люкн ьюмянб мю рн, врн нм днярюрнвмн унпньн ялнфер я щрхл яопюбхрэяъ. Кчдх ярпелъряъ хгаецюрэ йнлахмюжхи, йюфсыхуяъ хл меяксвюимшлх, рюйху, йюй оюпш ндхмюйнбшу яняедмху жхтп (унръ опхлепмн йюфдюъ хг 10~жхтп днкфмю янбоюдюрэ я опедшдсыеи). Онщрнлс, сбхдеб рюакхжс деиярбхрекэмн яксвюимшу вхяек, кчани векнбей яйнпее бяецн яйюфер, врн нмх янбяел ме яксвюимше, ецн цкюг япюгс фе нрлерхр мейнрнпше бхдхлше гюйнмнлепмнярх. Йюй гюлерхк д-п~Люрпхжю (жхрхпсеряъ он пюанре Л.~Gardner, {\sl Scientific American,\/} ъмбюпэ, 1965), "люрелюрхйх пюяялюрпхбючр деяърхвмне опедярюбкемхе вхякю~$\pi$ йюй яксвюимши пъд, рнцдю йюй дкъ янбпелеммнцн рнкйнбюрекъ вхяек---щрн йкюдегэ гюлевюрекэмшу гюйнмнлепмняреи". Д-п~Люрпхжю сйюгюк, мюопхлеп, врн оепбне онбрнпъчыееяъ дбсгмювмне вхякн б пюгкнфемхх~$\pi$---щрн 26, ю брнпне ецн онъбкемхе опхундхряъ рнвмн оняепедхме ндмни кчаношрмни йнмтхцспюжхх: \picture{(1) p. 52} Бшохяюб нйнкн дчфхмш дпсцху ябниярб щрху жхтп, нм намюпсфхк, врн, асдсвх опюбхкэмн хмрепоперхпнбюмн, вхякн~$\pi$ нрпюфюер бяч хярнпхч векнбевеярбю! Бяе лш бшдекъел нянаеммнярх рекетнммшу мнлепнб, мнлепмшу гмюйнб люьхм х р.~д., врнаш кецве ху гюонлмхрэ. Цкюбмюъ лшякэ бяецн яйюгюммнцн гюйкчвюеряъ б рнл, врн лш ме лнфел днбепърэ яеае б нжемйе, яксвюимю хкх мер дюммюъ онякеднбюрекэмнярэ вхяек. Менаундхлн хяонкэгнбюрэ йюйхе-рн меопедбгърше леуюмхвеяйхе реярш. %% 53 Ярюрхярхвеяйюъ ренпхъ дюер мюл мейнрнпше йнкхвеярбеммше йпхрепхх яксвюимнярх. Бнглнфмшл фе реярюл асйбюкэмн мер йнмжю. Лш наясдхл рнкэйн ре хг мху, йнрнпше, асдсвх мюханкее онкегмшлх х онсвхрекэмшлх, ндмнбпелеммн кецйн пеюкхгсчряъ мю бшвхякхрекэмшу люьхмюу. Еякх онякеднбюрекэмнярэ бедер яеаъ сднбкербнпхрекэмн нрмняхрекэмн реярнб~$T_1$, $T_2$,~\dots{}, $T_n$, лш ме лнфел ашрэ \emph{сбепемш} б рнл, врн нмю бшдепфхр, х якедсчыее хяошрюмхе~$T_{n+1}$. Ндмюйн йюфдши реяр дюер мюл бяе анкэье х анкэье сбепеммнярх б яксвюимнярх онякеднбюрекэмнярх. Нашвмн онякеднбюрекэмнярэ опнбепъеряъ я онлныэч онксдчфхмш пюгмшу реярнб. Еякх ху пегскэрюрш нйюгшбючряъ сднбкербнпхрекэмшлх, лш явхрюел ее яксвюимни (нмю явхрюеряъ мебхмнбмни дн реу онп, онйю ме днйюгюмю ее бхмнбмнярэ). Йюфдсч онякеднбюрекэмнярэ, йнрнпюъ асдер хмремяхбмн хяонкэгнбюрэяъ, якедсер рыюрекэмн опнбепхрэ. Онщрнлс б якедсчыху пюгдекюу на╝ъямъеряъ, йюй опюбхкэмн опнбндхрэ рюйсч опнбепйс. Пюгкхвючряъ дбю янпрю реярнб: \dfn{щлохпхвеяйхе реярш,} йнцдю люьхмю люмхоскхпсер я цпсооюлх вхяек онякеднбюрекэмнярх х опнхгбндхр нжемйс я онлныэч нопедекеммшу ярюрхярхвеяйху йпхрепхеб, х \dfn{ренперхвеяйхе реярш,} йнцдю лш мюундхл мейнрнпше уюпюйрепхярхйх онякеднбюрекэмнярх, онкэгсъяэ лерндюлх ренпхх вхяек, аюгхпсчыхлхяъ мю пейсппемрмнл яннрмньемхх, я онлныэч йнрнпнцн бшпюаюршбюеряъ онякеднбюрекэмнярэ. Б ймхце Д.~Уюттю [D.~Huff, How to Lie With Statistics, (Norton, 1954)] вхрюрекэ лнфер мюирх пъд дпсцху пейнлемдюжхи. \subsubchap{Смхбепяюкэмше реярш дкъ юмюкхгю яксвюимшу онякеднбюрекэмняреи} % 3.3.1 \section{A. Йпхрепхи~$\chi^2$}. Йпхрепхи~$\chi^2$ ("ух-йбюдпюр"), бепнърмн, яюлши пюяопнярпюмеммши хг бяеу ярюрхярхвеяйху йпхрепхеб. Нм хяонкэгсеряъ ме рнкэйн яюл он яеае, мн х йюй янярюбмюъ вюярэ лмнцху дпсцху реярнб. Опефде вел опхярсохрэ й наыелс нохяюмхч йпхрепхъ~$\chi^2$, пюяялнрпхл ямювюкю б йювеярбе опхлепю, йюй лнфмн ашкн аш опхлемхрэ щрнр йпхрепхи дкъ юмюкхгю хцпш б йнярх. Осярэ йюфдши пюг апняючряъ мегюбхяхлн дбе "опюбхкэмше" йнярх, опхвел апняюмхе йюфдни хг мху опхбндхр я пюбмни бепнърмнярэч й бшоюдемхч ндмнцн хг вхяек~$1$, $2$, $3$, $4$, $5$ х~$6$. Бепнърмнярх бшоюдемхъ кчани ясллш s опх ндмнл апняюмхх опедярюбкемш б рюакхже: $$ \vcenter{\halign{ #\hfil\bskip&\hfil$#{}$&\hfil$#$\hfil\bskip&&\bskip\hfil$#$\hfil\bskip\cr Ясллю & s=&2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12\cr Бепнърмнярэ& p_s=&{1\over 36} & 1\over 18 & 1\over 12 & 1\over 9 & 5\over 36 & 1\over 6 & 5 \over 36 & 1\over 9 & 1\over 12 & 1 \over 18 & 1 \over 36 \cr }} \eqno(1) $$(Мюопхлеп, ясллю s=4 лнфер ашрэ онксвемю рпелъ яонянаюлх: %% 54 $1+3$, $2+2$, $3+1$; опх $36$~бнглнфмшу хяундюу щрн янярюбкъер~$3/36=1/12=p_4$.) Еякх апняюрэ йнярх $n$~пюг, лнфмн нфхдюрэ, врн ясллю~$s$ онъбхряъ б япедмел $np_s$~пюг. Мюопхлеп, опх 144~апняюмхъу гмювемхе~$4$ днкфмн онъбхрэяъ нйнкн 12~пюг. Якедсчыюъ рюакхжю онйюгшбюер, йюйхе пегскэрюрш ашкх б \emph{деиярбхрекэмнярх,} онксвемш опх 144~апняюмхъу. $$ \vcenter{\halign{ #\hfil\bskip&\hfil$#{}$&\hfil$#$\bskip&&\bskip\hfil$#$\hfil\bskip\cr Ясллю & s=& 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 \cr Тюйрхвеяйне вхякн бшоюдемхи& Y_s=& 2 & 4 & 10 & 12 & 22 & 29 & 21 & 15 & 14 & 9 & 6\cr Япедмее вхякн бшоюдемхи & np_s=& 4 & 8 & 12 & 16 & 20 & 24 & 20 & 16 & 12 & 8 & 4 \cr }} \eqno(2) $$ Нрлерхл, врн тюйрхвеяйне вхякн бшоюдемхи нркхвюеряъ нр япедмецн бн бяеу яксвюъу. Б щрнл мер мхвецн сдхбхрекэмнцн. Декн б рнл, врн бяецн хлееряъ $36{144}$~бнглнфмшу онякеднбюрекэмняреи хяунднб дкъ 144~апняюмхи, х бяе нмх пюбмнбепнърмш. Ндмю хг рюйху онякеднбюрекэмняреи янярнхр, мюопхлеп, рнкэйн хг дбней ("глехмше цкюгю"), х йюфдши, с йнцн "глехмше цкюгю" бшоюдср ондпъд 144~пюгю, асдер сбепем, врн йнярх онддекэмше. Лефдс рел щрю онякеднбюрекэмнярэ рюй фе бепнърмю, йюй х кчаюъ дпсцюъ. Йюйхл фе напюгнл б рюйнл яксвюе лш лнфел опнбепхрэ, опюбхкэмн кх хгцнрнбкемю дюммюъ оюпю йняреи? Нрбер гюйкчвюеряъ б рнл, врн яйюгюрэ нопедекеммн "дю" хкх "мер" лш ме лнфел, мн лнфел дюрэ \emph{бепнърмнярмши} нрбер, р.~е.~сйюгюрэ, мюяйнкэйн бепнърмн хкх мебепнърмн дюммне янашрхе. Еяреярбеммши осрэ пеьемхъ мюьеи гюдювх янярнхр б якедсчыел. Бшвхякхл (опхаецмсб й онлных ЩБЛ) ясллс йбюдпюрнб пюгмняреи тюйрхвеяйнцн вхякю бшоюдемхи~$Y_s$ х япедмецн вхякю бшоюдемхи~$np_s$ (ял.~(2)): $$ V=(Y_2-np_2)^2+(Y_3-np_3)^2+\cdots+(Y_{12}-np_{12})^2. \eqno(3) $$ Дкъ окнунцн йнлокейрю йняреи днкфмш онксвюрэяъ нрмняхрекэмн бшянйхе гмювемхъ~$V$. Бнгмхйюер бнопня, мюяйнкэйн бепнърмш рюйхе бшянйхе гмювемхъ? Еякх бепнърмнярэ ху онъбкемхъ нвемэ люкю, яйюфел пюбмю~$1/100$,---р.~е.\ нрйкнмемхе пегскэрюрю нр япедмецн гмювемхъ мю рюйсч анкэьсч бекхвхмс бнглнфмн рнкэйн б ндмнл яксвюе хг~$100$,---рн с мюя еярэ нопедекеммше нямнбюмхъ дкъ онднгпемхи. (Ме якедсер гюашбюрэ, ндмюйн, врн дюфе \emph{унпньхе} йнярх асдср дюбюрэ рюйне бшянйне гмювемхе~$V$ ндхм пюг хг~100, рюй врн дкъ анкэьеи сбепеммнярх якеднбюкн аш онбрнпхрэ щйяоепхлемр х онялнрперэ, онксвхряъ кх онбрнпмн бшянйне гмювемхе~$V$.) Б ярюрхярхйс~$V$ бяе йбюдпюрш пюгмняреи бундър я пюбмшл беянл, унръ~$(Y_7-np_7)^2$, мюопхлеп, бепнърмн, асдер мюлмнцн анкэье, вел~$(Y_2-np_2)^2$, рюй йюй~$s=7$ бярпевюеряъ б ьеярэ пюг вюые, %% 55 вел~$s=2$. Нйюгшбюеряъ, врн б "опюбхкэмсч" ярюрхярхйс, хкх он йпюимеи лепе рюйсч, дкъ йнрнпни днйюгюмн, врн нмю мюханкее гмювхлю, вкем~$(Y_7-np_7)^2$ бундхр я лмнфхрекел, йнрнпши б ьеярэ пюг лемэье лмнфхрекъ опх~$(Y_2-np_2)^2$. Рюйхл напюгнл, якедсер гюлемхрэ~(3) мю якедсчысч тнплскс: $$ V={(Y_2-np_2)^2 \over np_2}+{(Y_3-np_3)^2\over np_3}+\cdots+{(Y_{12}-np_{12})^2\over np_{12}}. \eqno(4) $$ Нопедекеммсч рюйхл напюгнл бекхвхмс~$V$ мюгшбючр ярюрхярхйни~$\chi^2$, яннрберярбсчыеи гмювемхъл~$Y_2$,~\dots, $Y_{12}$, онксвеммшл б щйяоепхлемре. Ондярюбкъъ б щрс тнплскс гмювемхъ хг~(2), онксвюел $$ V={(2-4)^2\over 4}+{(4-8)^2\over 8}+\cdots+{(9-8)^2\over 8}+{(6-4)^2\over4}=7{7\over 48}. \eqno(5) $$ Реоепэ, еяреярбеммн, бнгмхйюер бнопня, ъбкъеряъ кх гмювемхе~$7{7\over48}$ мюярнкэйн анкэьхл, врн ецн яксвюимне онъбкемхе лнфмн явхрюрэ люкнбепнърмшл. Опефде вел нрбевюрэ мю щрнр бнопня, ятнплскхпсел йпхрепхи~$\chi^2$ б анкее наыел бхде. Опедонкнфхл, врн бяе бнглнфмше пегскэрюрш хяошрюмхи пюгдекемш мю $k$~йюрецнпхи. Опнбндхряъ $n$~\dfn{мегюбхяхлшу хяошрюмхи;} щрн нгмювюер, врн хяунд йюфднцн хяошрюмхъ юаянкчрмн ме бкхъер мю хяунд нярюкэмшу. Осярэ~$p_s$---бепнърмнярэ рнцн, врн пегскэрюр хяошрюмхъ оноюдер б йюрецнпхч~$s$, х осярэ~$Y_s$---вхякн хяошрюмхи, йнрнпше деиярбхрекэмн \emph{оноюкх} б йюрецнпхч~$s$. Ятнплхпсел ярюрхярхйс $$ V=\sum_{1\le s\le k} {(Y_s-np_s)^2\over np_s}. \eqno(6) $$ Б опедшдсыел опхлепе хлекняэ $11$~бнглнфмшу хяунднб опх йюфднл апняюмхх йняреи, рюй врн~$k=11$. [Тнплскш~(4) х~(6) пюгкхвючряъ рнкэйн мслепюжхеи: б ндмнл яксвюе нмю опнхгбндхряъ нр~2 дн~12, ю б дпсцнл---нр~$1$ дн~$k$.] Хяонкэгсъ рнфдеярбн~$(Y_s-np_s)^2=Y_s^2-2np_sY_s+n^2p_s^2$ х пюбемярбю $$ \eqalign{ Y_1+Y_2+\cdots+Y_k&=n,\cr p_1+p_2+\cdots+p_k&=1,\cr } \eqno(7) $$ лнфмн опенапюгнбюрэ тнплскс~(6) й бхдс $$ V={1\over n}\sum_{1\le s \le k} \left({Y_s^2\over p_s}\right)-n, \eqno(8) $$ опхвел б анкэьхмярбе яксвюеб рюйюъ гюохяэ накецвюер бшвхякемхъ. Бепмеляъ й бнопняс н рнл, йюйхе гмювемхъ~$V$ лнфмн явхрюрэ пюгслмшлх. Нрбер мю щрн дюер рюак.~1, б йнрнпни опхбедемн "пюяопедекемхе~$\chi^2$ я $\nu$~яреоемълх ябнандш" опх пюгмшу гмювемхъу~$\nu$. Якедсер онкэгнбюрэяъ ярпнйни рюакхжш я~$\nu=k-1$; \emph{вхякн "яреоемеи ябнандш" пюбмн~$k-1$, р.~е.\ мю едхмхжс лемэье вхякю йюрецнпхи.} %% 56 {\everycr={\noalign{\hrule}} \htable{Рюакхжю~1}% {Мейнрнпше дюммше дкъ пюяопедекемхъ~$\chi^2$}% {\offinterlineskip \strut\vrule\bskip$#$\bskip\hfil\vrule&&\bskip\hfil$#$\bskip\hfil\vrule\cr \noalign{ \embedpar{ \noindent (Анкее онкмше рюакхжш ял. б Handbook of Mathematical Functions, ed.\ by M.~Abramowitz and I.~A.~Stegun, U.~S. Government Printing Office, 1964, Table~26.8) } } & p=99\% & p=95\% & p=75\% & p=50\% & p=25\%& p=5\% & p=1\% \cr \nu=1 & 0.00016 & 0.00393 & 0.1015 & 0.4549 & 1.323 & 3.841 & 6.635\cr \nu=2 & 0.00201 & 0.1026 & 0.5753 & 1.386 & 2.773 & 5.991 & 9.210\cr \nu=3 & 0.1148 & 0.3518 & 1.213 & 2.366 & 4.108 & 7.815 & 11,34\cr \nu=4 & 0.2971 & 0.7107 & 1.923 & 3.357 & 5.385 & 9.488 & 13.28\cr \nu=5 & 0.5543 & 1.1455 & 2.675 & 4.351 & 6.626 & 11.07 & 15.09\cr \nu=6 & 0.8720 & 1.635 & 3.455 & 5.348 & 7.841 & 12.59 & 16.81\cr \nu=7 & 1.239 & 2.167 & 4.255 & 6.346 & 9.037 & 14.07 & 18.48\cr \nu=8 & 1.646 & 2.733 & 5.071 & 7.344 & 10.22 & 15.51 & 20.09\cr \nu=9 & 2.088 & 3.325 & 5.899 & 8.343 & 11.39 & 16.92 & 21.67\cr \nu=10 & 2.558 & 3.940 & 6.737 & 9.342 & 12.55 & 18.31 & 23.21\cr \nu=11 & 3.053 & 4.575 & 7.584 & 10.34 & 13.70 & 19.68 & 24.73\cr \nu=12 & 3.571 & 5.226 & 8.438 & 11.34 & 14.84 & 21.03 & 26.22\cr \nu=15 & 5.229 & 7.261 & 11.04 & 14.34 & 18.25 & 25.00 & 30.58\cr \nu=20 & 8.260 & 10.85 & 15.45 & 19.34 & 23.83 & 31.41 & 37.57\cr \nu=30 & 14.95 & 18.49 & 24.48 & 29.34 & 34.80 & 43.77 & 50.89\cr \nu=50 & 29.71 & 34.76 & 42.94 & 49.33 & 56.33 & 67.50 & 76.15\cr \nu>30 & \multispan{7} \hfil\emph{опхакхгхрекэмн~$\nu+2\sqrt{\nu}x_p+{4\over3}x^2_p-{2\over3}$\hfil}\vrule\cr x_p= & -2.33 & -1.64 & -.675 & 0.00 & 0.675 & 1.64 & 2.33\cr }} (Мю хмрсхрхбмнл спнбме щрн лнфмн онъямхрэ якедсчыхл напюгнл: гмювемхъ~$Y_1$, $Y_2$,~\dots, $Y_k$ ме янбяел мегюбхяхлш, рюй йюй~$Y_1$, янцкюямн~(7), лнфмн бшвхякхрэ, гмюъ~$Y_2$,~\dots, $Y_k$. Якеднбюрекэмн, хлееряъ $k-1$~яреоемеи ябнандш. Анкее ярпнцюъ юпцслемрюжхъ асдер опхбедемю мхфе.) Еякх б рюакхже б ярпнйе~$\nu$ х йнкнмйе~$p$ мюундхряъ вхякн~$x$, рн щрн нгмювюер, врн гмювемхе~$V$, нопедекъелне он тнплске~(8), асдер анкэье~$x$ я бепнърмнярэч~$p$. Мюопхлеп, дкъ~$p=5$\% х~$\nu=10$ рюакхжю дюер гмювемхе~$x=18.31$; щрн нгмювюер, врн~$V>18.31$ рнкэйн б~$5$\% бяеу яксвюеб. Опедонкнфхл, врн нохяюммши опнжеяя апняюмхъ йняреи лндекхпсеряъ мю ЩБЛ я онлныэч онякеднбюрекэмнярх вхяек, йнрнпше %% 57 опедонкюцючряъ яксвюимшлх, х врн онксвемш якедсчыхе пегскэрюрш: $$ \vcenter{ \halign{#\bskip\hfil&\bskip\hfil$#{}$&$#$\bskip\hfil&&\bskip\hfil$#$\bskip\cr & s=& 2 & 3& 4& 5& 6& 7& 8& 9& 10& 11& 12\cr Щйяоепхлемр~1 & Y_s=& 4 & 10& 10& 13& 20& 18& 18& 11& 13& 14& 13\cr Щйяоепхлемр~2 & Y_s=& 3 & 7& 11& 15& 19& 24& 21& 17& 13& 9& 5\cr } } \eqno(9) $$ Бшвхякъъ ярюрхярхйс йпхрепхъ~$\chi^2$, онксвюел б оепбнл яксвюе $V_1=29{59\over 120}$, ю бн брнпнл яксвюе~$V_2=1{17\over 120}$. Рюакхвмше гмювемхъ, яннрберярбсчыхе $10$~яреоемъл ябнандш, онйюгшбючр, врн~$V_1$ \emph{ъбмн якхьйнл, бекхйн;} $V$~ашбюер анкэье, вел~$23.2$, рнкэйн б ндмнл опнжемре яксвюеб! (Анкее онкмше рюакхжш онйюгшбючр, врн бепнърмнярэ онъбкемхъ ярнкэ анкэьнцн гмювемхъ~$V$ пюбмю~$0.1$\%.) Рюйхл напюгнл, б щйяоепхлемре~1 гюпецхярпхпнбюмн гмювхрекэмне нрйкнмемхе нр мнплш. Я дпсцни ярнпнмш, $V_2$ нвемэ люкн, онрнлс врн~$Y_s$ б щйяоепхлемре~2 нйюгюкхяэ нвемэ акхгйх й япедмхл гмювемхъл~$np_s$ [яп.~я~(2)]. Хг рюакхжш пюяопедекемхъ~$\chi^2$ якедсер, врн б~$99$\% яксвюеб $V$~днкфмн ашрэ анкэье, вел~$2.56$. Гмювемхе~$V_2$ \emph{ъбмн якхьйнл люкн;} онксвеммше б щйяоепхлемре гмювемхъ~$V_3$ %% ?? V_s мюярнкэйн акхгйх й япедмел гмювемхъл, врн мебнглнфмн явхрюрэ щрнр щйяоепхлемр яксвюимшл хяошрюмхел. (Б яюлнл деке, хг анкее онкмшу рюакхж якедсер, врн опх $10$~яреоемъу ябнандш рюйхе мхгйхе гмювемхъ~$V$ бярпевючряъ рнкэйн б $0.03$\%~яксвюеб). Мюйнмеж, я онлныэч рюакхжш пюяопедекемхъ~$\chi^2$ лнфмн опнбепхрэ онксвеммне мюлх б~(5) гмювемхе~$V=7{7\over 48}$. Нмн оноюдюер б хмрепбюк лефдс~$75$ х~$50$\%, рюй врн лш ме лнфел явхрюрэ ецн якхьйнл бшянйхл хкх якхьйнл мхгйхл; дюммше, опедярюбкеммше б~(2), сднбкербнпъчр йпхрепхч~$\chi^2$. Анкэьхл опехлсыеярбнл пюяялюрпхбюелнцн лерндю ъбкъеряъ рн, врн ндмх х ре фе рюакхвмше гмювемхъ хяонкэгсчряъ опх кчашу~$n$ х кчашу бепнърмняръу~$p_s$. Едхмярбеммни оепелеммни ъбкъеряъ~$\nu=k-1$. Мю яюлнл деке опхбедеммше б рюакхже гмювемхе ме ъбкъчряъ юаянкчрмн рнвмшлх бн бяеу яксвюъу: \emph{щрн опхакхфеммше гмювемхъ, яопюбедкхбше кхьэ опх днярюрнвмн анкэьху гмювемхъу~$n$.} Йюй бекхйн днкфмн ашрэ~$n$? Днярюрнвмн анкэьхлх лнфмн явхрюрэ рюйхе гмювемхъ~$n$, опх йнрнпшу кчане хг~$np_s$ ме лемэье~$5$; ндмюйн ксвье апюрэ~$n$ гмювхрекэмн анкэьхлх, врнаш онбшяхрэ мюдефмнярэ йпхрепхъ. Гюлерхл, врн б пюяялнрпеммшу опхлепюу лш апюкх~$n=144$, х $np_2$~пюбмъкняэ бяецн~$4$, врн опнрхбнпевхр рнкэйн врн ятнплскхпнбюммнлс опюбхкс. Едхмярбеммюъ опхвхмю щрнцн мюпсьемхъ йпнеряъ б рнл, врн юбрнпс мюднекн апняюрэ йнярх; б пегскэрюре вхякю хг рюакхжш нйюгюкхяэ ме нвемэ ондундъыхлх дкъ мюьецн яксвюъ. Ашкн аш цнпюгдю ксвье опнбеярх щрх щйяоепхлемрш мю люьхме опх~$n=1000$ хкх~$10\,000$, хкх дюфе~$100\,000$. %% 58 Мю яюлнл деке бнопня н бшанпе~$n$ ме рюй опняр. Еякх аш йнярх ашкх деиярбхрекэмн меопюбхкэмше, щрн опнъбкъкняэ аш опх яйнкэ сцндмн анкэьху~$n$ (ял.~соп.~12). Мн опх анкэьху гмювемхъу~$n$ лнцср яцкюфхбюрэяъ \emph{кнйюкэмше} нрйкнмемхъ, рюйхе, йюй якедсчыхе дпсц гю дпсцнл акнйх вхяек я яхкэмшл яхярелюрхвеяйхл ялеыемхел б опнрхбнонкнфмше ярнпнмш. Опх деиярбхрекэмнл апняюмхх йняреи щрнцн лнфмн ме ноюяюрэяъ, рюй йюй бяе бпелъ хяонкэгсчряъ ндмх х ре фе йнярх, мн еякх певэ хдер н онякеднбюрекэмнярх вхяек, онксвеммшу мю ЩБЛ, рн рюйни рхо нрйкнмемхъ нр яксвюимнцн онбедемхъ бонкме бнглнфем. Б ябъгх \picture{ Пхя.~2. Пегскэрюрш 90~опнбепнй я хяонкэгнбюмхел йпхрепхъ~$\chi^2$ (яп. я~пхя.~5). } я щрхл фекюрекэмн опнбндхрэ опнбепйс я онлныэч йпхрепхъ~$\chi^2$ опх пюгмшу гмювемхъу~$n$, мн б кчанл яксвюе щрх гмювемхъ днкфмш ашрэ днбнкэмн анкэьхлх. Хрюй, опнбепйю я онлныэч йпхрепхъ~$\chi^2$ гюйкчвюеряъ б якедсчыел. Опнбндхряъ $n$~мегюбхяхлшу хяошрюмхи, цде~$n$---днярюрнвмн анкэьне вхякн. (Якедсер хгаецюрэ опхлемемхъ йпхрепхъ~$\chi^2$ б яксвюъу, еякх хяошрюмхъ ме мегюбхяхлш; ял., мюопхлеп, соп.~10, цде пюяялнрпем яксвюи, йнцдю ндмю онкнбхмю янашрхи гюбхяхр нр дпсцни.) Ондявхршбюеряъ вхякн хяошрюмхи, пегскэрюр йнрнпшу нрмняхряъ й йюфдни хг $k$~йюрецнпхи, х он тнплскюл~(6) хкх~(8) бшвхякъеряъ гмювемхе~$V$. Гюрел~$V$ япюбмхбюеряъ я вхякюлх хг рюак.~1 опх~$\nu=k-1$. Еякх $V$~лемэье гмювемхъ, яннрберярбсчыецн~$p=99\%$, хкх анкэье гмювемхъ, яннрберярбсчыецн~$p=1\%$, рн пегскэрюрш апюйсчряъ йюй меднярюрнвмн яксвюимше. Еякх~$p$ %% 59 кефхр лефдс~99 х~95\% хкх лефдс~5 х~1\%, рн пегскэрюрш явхрючряъ "онднгпхрекэмшлх"; опх гмювемхъу~$p$, онксвеммшу хмрепонкъжхеи он рюакхже, гюйкчвеммшу лефдс~$95$ х~$90$\% хкх~$10$ х~$5$\%, пегскэрюрш "якецйю онднгпхрекэмш". Вюярн я онлныэч йпхрепхъ~$\chi^2$ опнбепъчр он йпюимеи лепе рпх пюгю пюгмше вюярх хяякедселнцн пъдю вхяек, х, еякх ме лемее дбсу пюг хг рпеу пегскэрюрш нйюгшбючряъ онднгпхрекэмшлх, вхякю нрапюяшбючряъ йюй меднярюрнвмн яксвюимше. Пюяялнрпхл б йювеярбе опхлепю пхя.~2, цде яуелюрхвеяйх опедярюбкемш пегскэрюрш опнбепйх я онлныэч йпхрепхъ~$\chi^2$ ьеярх онякеднбюрекэмняреи яксвюимшу вхяек. Дкъ йюфдни онякеднбюрекэмнярх декюкняэ оърэ пюгмшу опнбепнй (нямнбюммшу мю йпхрепхх~$\chi^2$), йюфдюъ хг йнрнпшу онбрнпъкюяэ мю рпеу пюгмшу свюярйюу онякеднбюрекэмнярх. Б дюрвхйе~A хяонкэгнбюм лернд Люйкюпемю-Люпяюкэх (юкцнпхрл~3.2.2Л), б дюрвхйе~E---лернд Тханмюввх, нярюкэмше дюрвхйх яннрберярбсчр кхмеимшл йнмцпсщмрмшл онякеднбюрекэмняръл ян якедсчыхлх оюпюлерпюлх: \ctable{#\hfil\bskip&\bskip # \hfil\cr Дюрвхй~Б:& $X_0=0$, $a=3141592653$, $c=2718281829$, $m=2^{35}$.\cr Дюрвхй~C:& $X_0=0$, $a=2^7+1$, $c=1$, $m=2^{35}$.\cr Дюрвхй~D:& $X_0=47594118$, $a=23$, $c=0$, $m=10^8+1$.\cr Дюрвхй~F:& $X_0=314159265$, $a=2^{18}+1$, $c=1$, $m=2^{35}$.\cr } Пегскэрюрш, опхбедеммше мю пхя.~2, онгбнкъчр ядекюрэ якедсчыхе бшбндш. Дюрвхйх~A, B, D опнькх хяошрюмхъ сднбкербнпхрекэмн, дюрвхй~C мюундхряъ мю цпюмх х днкфем ашрэ, он-бхдхлнлс, гюапюйнбюм, ю дюрвхйх~E х~F нопедекеммн ме опнькх хяошрюмхи. Дюрвхй~F, аегсякнбмн, люкнлныем; дюрвхйх~C х~D наясфдюкхяэ б кхрепюрспе, мн с мху якхьйнл люкн гмювемхе~$a$. Б дюрвхйе~D пеюкхгнбюм лернд бшвернб б рнл бхде, б йюйнл нм ашк боепбше опедкнфем Келепнл б~1948~ц., ю б дюрвхйе~C---кхмеимши йнмцпсщмрмши лернд я~$c\ne 0$ рюйфе б ецн оепбнмювюкэмнл бхде (Пнремаепц, 1960). Меяйнкэйн дпсцни ондунд й ясфдемхч н пегскэрюрюу опнбепйх он йпхрепхч~$\chi^2$, аег хяонкэгнбюмхъ рюйху онмърхи, йюй "онднгпхрекэмши", "якецйю онднгпхрекэмши" х~р.~д., х лемее онгбнкъчыхи онкюцюрэяъ мю лмемхе ad hoc, нохяшбюеряъ мхфе б щрнл пюгдеке. \section{B. Йпхрепхи Йнклнцнпнбю-Ялхпмнбю (ЙЯ-йпхрепхи)}. Йюй лш бхдекх, йпхрепхи~$\chi^2$ опхлемъеряъ б реу яксвюъу, йнцдю пегскэрюрш хяошрюмхи пюяоюдючряъ мю йнмевмне вхякн $k$~йюрецнпхи. Ндмюйн мепедйн яксвюимше бекхвхмш лнцср опхмхлюрэ аеяйнмевмн лмнцн гмювемхи. Б вюярмнярх, аеяйнмевмн лмнцн гмювемхи опхмхлючр беыеярбеммше яксвюимше вхякю б хмрепбюке лефдс~$0$ х~$1$. Унръ лмнфеярбн гмювемхи яксвюимшу вхяек, онксвеммшу б %%60 бшвхякхрекэмни люьхме, мехгаефмн нцпюмхвемн, унрекняэ аш, врнаш щрн мхйюй ме яйюгшбюкняэ мю пегскэрюрюу пюявернб. Б ренпхх бепнърмняреи х ярюрхярхйе опхмърн хяонкэгнбюрэ ндмх х ре фе нангмювемхъ опх нохяюмхх дхяйпермшу х меопепшбмшу пюяопедекемхи. Осярэ рпеасеряъ нохяюрэ пюяопедекемхе гмювемхи яксвюимни бекхвхмш~$X$. Щрн декюеряъ я онлныэч \dfn{тсмйжхх пюяопедекемхъ~$F(x)$,} цде $$ F (x) = \hbox{бепнърмнярэ рнцн, врн~$(X\le x)$.} $$ Мю пхя.~3 опедярюбкемш рпх опхлепю. Оепбши хг мху---тсмйжхъ пюяопедекемхъ \emph{яксвюимнцн ахрю,} р.~е.\ яксвюимни бекхвхмш~$X$, \picture{Пхя.~3. Опхлепш тсмйжхи пюяопедекемхъ.} опхмхлючыеи гмювемхъ~$0$ хкх~$1$, йюфдне я бепнърмнярэч~$1/2$. Мю пхя.~3,~b онйюгюмю тсмйжхъ пюяопедекемхъ \emph{беыеярбеммни яксвюимни бекхвхмш, пюбмнлепмн пюяопедекеммни} лефдс мскел х едхмхжеи, рюй врн бепнърмнярэ рнцн, врн~$X\le x$, опнярн пюбмю~$x$, еякх~$0\le x \le 1$. Мюопхлеп, бепнърмнярэ рнцн, врн~$X\le{2\over3}$, пюбмю~$2\over3$. Мю пхя.~3,~c онйюгюмн опедекэмне пюяопедекемхе гмювемхи~$V$ б йпхрепхх~$\chi^2$ (опх 10~яреоемъу ябнандш); щрн фе пюяопедекемхе, мн б дпсцни тнпле, ашкн сфе опедярюбкемн б рюак.~1. Гюлерхл, врн~$F(x)$ бяецдю бнгпюярюер нр~$0$ дн~$1$ опх сбекхвемхх~$x$ нр~$-\infty$ дн~$+\infty$. Хяонкэгсъ гмювемхъ~$X_1$, $X_2$,~\dots, $X_n$ яксвюимни бекхвхмш~$X$, онксвеммше б пегскэрюре мегюбхяхлшу хяошрюмхи, лнфмн онярпн- %% 61 \bye