\input style \chapter{ЪБНЕЮБОЙС ПВ ХРТБЦОЕОЙСИ} Хртбцоеойс, рпнеэеооще ч лойзби обуфпсэек уетйй, ртедобъобюеощ лбл дмс убнпуфпсфемшопк ртптбвпфлй, фбл й дмс уенйобтулйи ъбосфйк. Фтхдоп, еумй ое оечпънпцоп йъхюйфш ртеднеф, фпмшлп юйфбс фептйа й ое ртйнеосс рпмхюеооха йожптнбгйа дмс теыеойс урегйбмшощи ъбдбю й фен убнщн ое ъбуфбчмсс уевс пвдхнщчбфш фп, юфп вщмп ртпюйфбоп. Лтпне фпзп, нщ мхюые чуезп ъбхюйчбен фп, юфп убнй пфлтщчбен дмс уевс. Рпьфпнх хртбцоеойс пвтбъхаф чбцоха юбуфш дбоопк тбвпфщ; вщмй ртедртйосфщ пртедемеооще рпрщфлй, юфпвщ пфпвтбфш хртбцоеойс, ч лпфптщи вщ упдетцбмпуш лбл нпцоп впмшые йожптнбгйй й лпфптще вщмп вщ йофетеуоп теыбфш. Чп нопзйи лойзби мезлйе хртбцоеойс дбафус чретенеылх у йулмаюйфемшоп фтхдощнй. Ъбюбуфха ьфп пюеош оехдпвоп, фбл лбл ретед фен, лбл ртйуфхрбфш л теыеойа ъбдбюй, юйфбфемш пвсъбфемшоп дпмцео ртедуфбчмсфш уеве, улпмшлп чтенеой хкдеф х оезп об ьфп теыеойе (йобюе по нпцеф тбъче фпмшлп ртпунпфтефш чуе ъбдбюй). Лмбууйюеулйн ртйнетпн ъдеуш счмсефус лойзб Тйюбтдб Веммнбоб "Дйобнйюеулпе ртпзтбннйтпчбойе"; ьфп чбцобс рйпоетулбс тбвпфб, ч лпфптпк ч лпоге лбцдпк змбчщ рпд тхвтйлпк "Хртбцоеойс й йуумедпчбфемшулйе ртпвменщ" дбефус гемщк тсд ъбдбю, зде обтсдх у змхвплйнй еэе оетеыеоощнй ртпвменбнй чуфтеюбафус йулмаюйфемшоп фтйчйбмшоще чпртпущ. Зпчптсф, юфп пдобцдщ лфп-фп уртпуйм д-тб Веммнбоб, лбл пфмйюйфш хртбцоеойс пф йуумедпчбфемшулйи ртпвмен, й фпф пфчефйм: "Еумй чщ нпцефе теыйфш ъбдбюх, ьфп---хртбцоеойе; ч ртпфйчопн умхюбе ьфп---ртпвменб". Нпцоп ртйчеуфй нопзп дпчпдпч ч рпмшъх фпзп, юфп ч лойзе фйрб ьфпк дпмцощ вщфш лбл йуумедпчбфемшулйе ртпвменщ, фбл й пюеош ртпуфще хртбцоеойс, й дмс фпзп юфпвщ юйфбфема ое ртйипдймпуш мпнбфш зпмпчх обд фен, лблбс ъбдбюб мезлбс, б лблбс фтхдобс, нщ ччемй "пгеолй", лпфптще хлбъщчбаф уфереош фтхдопуфй лбцдпзп хртбцоеойс. Ьфй пгеолй йнеаф умедхаэее ъобюеойе: \descrtable{ \bf Пгеолб & \bf ПвRсуоеойе \cr 00 & Ютеъчщюбкоп мезлпе хртбцоеойе, об лпфптпе нпцоп пфчефйфш утбъх це, еумй рпосф нбфетйбм фелуфб, й лпфптпе рпюфй чуездб нпцоп теыйфш "ч хне".\cr %% 11 10 & Ртпуфбс ъбдбюб, лпфптбс ъбуфбчмсеф ъбдхнбфшус обд ртпюйфбоощн нбфетйбмпн, оп ое ртедуфбчмсеф ойлблйи пупвщи фтхдопуфек. Об теыеойе фблпк ъбдбюй фтевхефус ое впмшые пдопк нйохфщ; ч ртпгеууе теыеойс нпзхф рпобдпвйфшус лбтбодбы й вхнбзб. \cr 20 & Ъбдбюб утедоек фтхдопуфй, рпъчпмсаэбс ртпчетйфш, обулпмшлп иптпып рпосф фелуф. Об фп юфпвщ дбфш йуюетрщчбаэйк пфчеф, фтевхефус ртйнетоп 15--20~нйохф. \cr 30 & Ъбдбюб хнетеоопк фтхдопуфй й/ймй умпцопуфй, дмс хдпчмефчптйфемшопзп теыеойс лпфптпк фтевхефус впмшые дчхи юбупч. \cr 40 & Пюеош фтхдобс ймй фтхдпенлбс ъбдбюб, лпфптха, четпсфоп, умедхеф члмаюйфш ч рмбо ртблфйюеулйи ъбосфйк. Ртедрпмбзбефус, юфп уфхдеоф нпцеф теыйфш фблха ъбдбюх, оп дмс ьфпзп енх рпфтевхефус ъобюйфемшощк пфтеъпл чтенеой; ъбдбюб теыбефус оефтйчйбмшощн пвтбъпн. \cr 50 & Йуумедпчбфемшулбс ртпвменб, лпфптбс (обулпмшлп ьфп вщмп йъчеуфоп бчфптх ч нпнеоф обрйубойс) еэе ое рпмхюймб хдпчмефчптйфемшопзп теыеойс. Еумй юйфбфемш обкдеф теыеойе ьфпк ъбдбюй, езп обуфпсфемшоп ртпусф прхвмйлпчбфш езп; лтпне фпзп, бчфпт дбоопк лойзй вхдеф пюеош ртйъобфемео, еумй енх уппвэбф теыеойе, лбл нпцоп вщуфтее (ртй хумпчйй, юфп поп ртбчймшоп). \cr } Йофетрпмйтхс рп ьфпк "мпзбтйжнйюеулпк" ылбме, нпцоп ртйлйохфш, юфп пъобюбеф мавбс ртпнецхфпюобс пгеолб. Обртйнет, пгеолб~17 зпчптйф п фпн, юфп дбоопе хртбцоеойе юхфш мезюе, юен хртбцоеойе утедоек фтхдопуфй. Ъбдбюб у пгеолпк~50, еумй поб вхдеф теыеоб лблйн-мйвп юйфбфемен, ч умедхаэйи йъдбойси дбоопк лойзй нпцеф йнефш хце пгеолх~45. Бчфпт юеуфоп уфбтбмус дбчбфш пвRелфйчоще пгеолй, оп фпнх, лфп упуфбчмсеф ъбдбюй, фтхдоп ртедчйдефш, обулпмшлп фтхдощнй ьфй ъбдбюй плбцхфус дмс лпзп-фп дтхзпзп; л фпнх це х лбцдпзп юемпчелб ухэеуфчхеф пртедемеоощк фйр ъбдбю, лпфптще по теыбеф вщуфтее. Обдеауш, юфп чщуфбчмеооще нопк пгеолй дбаф ртбчймшопе ртедуфбчмеойе п уфереой фтхдопуфй ъбдбю, оп ч пвэен йи охцоп чпуртйойнбфш лбл птйеофйтпчпюоще, б ое бвупмафоще. Ьфб лойзб обрйубоб дмс юйфбфемек убнщи тбъощи уфереоек нбфенбфйюеулпк рпдзпфпчлй й йулхыеоопуфй, рпьфпнх оелпфптще хртбцоеойс ртедобъобюеощ фпмшлп дмс юйфбфемек у нбфенбфйюеулйн хлмпопн. Еумй ч лблпн-мйвп хртбцоеойй нбфенбфйюеулйе рпосфйс ймй теъхмшфбфщ йурпмшъхафус впмее ыйтплп, юен ьфп оепвипдйнп дмс феи, лпзп ч ретчха пюетедш йофетеухеф ртпзтбннйтпчбойе бмзптйфнпч, фп ретед пгеолпк фблпзп хртбцоеойс уфбчйфус вхлчб "\emph{Н}". Еумй дмс теыеойс хртбцоеойс фтевхефус ъобойе чщуыек нбфенбфйлй ч впмшыен пвRене, юен ьфп дбоп ч обуфпсэек %% 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{Тбъчмеюеойс.} Нопзйе ртпчпдсф чтенс, фбухс лбтфщ, втпубс лпуфй ймй обвмадбс ъб лпмеупн тхмефлй, й обипдсф ч ьфпн оейъRсуойнпе хдпчпмшуфчйе. Фблйн фтбдйгйпоощн йурпмшъпчбойен умхюбкощи юйуем пвRсуосефус, рпюенх фетнйо "Нпофе-Лбтмп" умхцйф пвэйн обйнеопчбойен дмс чуеи бмзптйфнпч, ч лпфптщи ртйнеосаф умхюбкоще юйумб. \medskip Уфбмп пвщюощн ч ьфпн неуфе рпучсэбфш оеулпмшлп бвъбгеч жймпупжулпнх пвухцдеойа фпзп, юфп це фблпе "умхюбкопуфш". Ч оелпфптпн унщуме фблпзп пвRелфб, лбл умхюбкопе юйумп, ртпуфп оеф. Улбцен, дчпклб---ьфп умхюбкопе юйумп? Улптее нщ зпчптйн п \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.] Чулпте рпуме упъдбойс чщюйумйфемшощи нбыйо обюбмйуш рпйулй ьжжелфйчощи нефпдпч рпмхюеойс умхюбкощи юйуем, ртйзпдощи дмс йурпмшъпчбойс ч ртпзтбннби. Ч ртйогйре нпцоп тбвпфбфш й у фбвмйгбнй, пдоблп, ьфпф нефпд йнееф пзтбойюеойс, учсъбооще у лпоеюощн пвRенпн рбнсфй нбыйо й ъбфтбфбнй чтенеой дмс ччпдб юйуем ч нбыйох ч фпн умхюбе, лпздб фбвмйгб плбъщчбефус умйылпн лптпфлпк. Лтпне фпзп, дпчпмшоп оертйсфоп зпфпчйфш фбвмйгщ ъбтбоее, дб й чппвэе йнефш у ойнй демп. Нпцоп ртйупедйойфш л ЬЧН нбыйох фйрб 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 (Ипфемпуш обрйубфш обуфпмшлп умпцоха ртпзтбннх, тебмйъхаэха прйубоощк чщые бмзптйфн, юфпвщ юемпчел, юйфбаэйк ее фелуф, ое нпз вщ веъ пвRсуоеойк дпзбдбфшус, юфп це ч оек дембефус.) Хюйфщчбс чуе нетщ ртедпуфптпцопуфй, ртйосфще ч бмзптйфне~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] ПвRсуойфе, рпюенх ч мавпн умхюбе оемшъс пцйдбфш рпмхюеойс "веулпоеюопзп нопцеуфчб" умхюбкощи юйуем у рпнпэша бмзптйфнб~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] ПвRсуойфе, рпюенх, еумй~$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$~ртпчетеоощи юйуем оелпфптще фтйбдщ чуфтеюбмйуш пюеош тедлп, б оелпфптще рпсчмсмйуш зптбъдп юбэе дтхзйи. Нпцефе мй чщ пвRсуойфш фблпк уфтбоощк теъхмшфбф? \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{дплбъбфш,} юфп йи улерфйгйън оепртбчдбо (ипфс нщ й четйн, юфп ьфп фбл), дпчпмшоп веурпмеъоп пурбтйчбфш рпдпвопе ноеойе. Ухэеуфчхаф чрпмое ьжжелфйчоще нефпдщ дмс фпзп, юфпвщ рпмхюбфш йъ дчхи рпумедпчбфемшопуфек обуфпмшлп умхюбкоха фтефша, юфп фпмшлп убнщн пфRсчмеоощн улерфйлбн поб нпцеф ое рпотбчйфшус. Ртедрпмпцйн, юфп нщ йнеен дче рпумедпчбфемшопуфй~$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] (Д. Тйу.) Ч фелуфе пвRсуосефус, лбл обипдйфш жхолгйй~$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}$. Пдоблп лбцдщк феуф дбеф обн чуе впмшые й впмшые хчетеоопуфй ч умхюбкопуфй рпумедпчбфемшопуфй. Пвщюоп рпумедпчбфемшопуфш ртпчетсефус у рпнпэша рпмхдацйощ тбъощи феуфпч. Еумй йи теъхмшфбфщ плбъщчбафус хдпчмефчптйфемшощнй, нщ уюйфбен ее умхюбкопк (поб уюйфбефус оечйопчопк дп феи рпт, рплб ое дплбъбоб ее чйопчопуфш). Лбцдха рпумедпчбфемшопуфш, лпфптбс вхдеф йофеоуйчоп йурпмшъпчбфшус, умедхеф фэбфемшоп ртпчетйфш. Рпьфпнх ч умедхаэйи тбъдемби пвRсуосефус, лбл ртбчймшоп ртпчпдйфш фблха ртпчетлх. Тбъмйюбафус дчб уптфб феуфпч: \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