Раз­ло­жив де­ли­мое и де­ли­тель на мно­жи­те­ли, по­лу­ча­ем усло­вие Зна­чит, одно из чисел k или де­лит­ся на 101. Рас­смот­рим два слу­чая.

а)  Когда то есть Тогда по­лу­ча­ем

Пер­вый мно­жи­тель де­лит­ся на 5 при а вто­рой  — при от­ку­да по­лу­ча­ем, что

б)  Когда то есть Тогда по­лу­ча­ем

Пер­вый мно­жи­тель де­лит­ся на 5 при а вто­рой  — при от­ку­да по­лу­ча­ем, что Итак, усло­вию за­да­чи удо­вле­тво­ря­ют числа, да­ю­щие остат­ки 0, 404, 100, 504 при де­ле­нии на 505, то есть под­хо­дят каж­дые 4 из 505 под­ряд иду­щих чисел. Так как по­лу­ча­ем чисел.

Ответ: 2800.

Раз­ло­жив де­ли­мое и де­ли­тель на мно­жи­те­ли, по­лу­ча­ем усло­вие

Зна­чит, одно из чисел или де­лит­ся на 97. Рас­смот­рим два слу­чая.

а)  Когда то есть Тогда по­лу­ча­ем

Пер­вый мно­жи­тель де­лит­ся на 3 при а вто­рой  — при от­ку­да по­лу­ча­ем, что

б)  Когда то есть Тогда по­лу­ча­ем

Пер­вый мно­жи­тель де­лит­ся на 3 при а вто­рой  — при от­ку­да по­лу­ча­ем, что

Итак, усло­вию за­да­чи удо­вле­тво­ря­ют числа, да­ю­щие остат­ки 193, 290, 98, 1 при де­ле­нии на 291, то есть под­хо­дят каж­дые 4 из 291 под­ряд иду­щих чисел. Так как по­лу­ча­ем чисел.

Ответ: 4000.

Раз­ло­жив де­ли­мое и де­ли­тель на мно­жи­те­ли, по­лу­ча­ем усло­вие

Зна­чит, одно из чисел или де­лит­ся на 89. Рас­смот­рим два слу­чая.

а)  Когда то есть Тогда по­лу­ча­ем

Пер­вый мно­жи­тель де­лит­ся на 5 при а вто­рой  — при от­ку­да по­лу­ча­ем, что где

б)  Когда то есть Тогда по­лу­ча­ем

Пер­вый мно­жи­тель де­лит­ся на 5 при а вто­рой  — при от­ку­да по­лу­ча­ем, что где

Итак, усло­вию за­да­чи удо­вле­тво­ря­ют числа, да­ю­щие остат­ки 276, 444, 179, 1 при де­ле­нии на 445, то есть под­хо­дят каж­дые 4 из 445 под­ряд иду­щих чисел. Так как по­лу­ча­ем чисел.

Ответ: 4000.

Будем сле­дить, какие остат­ки дают сте­пе­ни 3 и 5 при де­ле­нии на 13. Обо­зна­чим эти остат­ки чисел 3ⁿ и 5ⁿ через rⁿ и со­от­вет­ствен­но. По­сле­до­ва­тель­но на­хо­дим остат­ки при де­ле­нии rⁿ при де­ле­нии 3ⁿ на 13:

Для того, чтобы со­ста­вить такую таб­ли­цу, вовсе не нужно де­лить 3⁵, 3⁶, ... на 13: ясно, что если тоже де­лит­ся на 13, так что оста­ток можно по­лу­чить про­сто как оста­ток при де­ле­нии на 13. Таким об­ра­зом, остат­ки по­вто­ря­ют­ся с пе­ри­о­дом 3, по­это­му

Для остат­ков, по­лу­ча­ю­щих­ся при де­ле­нии на 13 чисел 5ⁿ, имеем такую таб­ли­цу:

Здесь пе­ри­од равен 4, и Таким об­ра­зом, дает в остат­ке дает в остат­ке 12, по­лу­ча­ем

Ответ: 5.

Рас­смот­ри вы­ра­же­ние

Каж­дая скоб­ка в левой части де­лит­ся на по­это­му и пра­вая часть де­лит­ся, то есть крат­но n.

Лидии нра­вят­ся пя­ти­знач­ные числа, со­став­лен­ные толь­ко из цифр 1, 2, 4, 5, 7, 8. За­ме­тим, что все такие числа можно раз­бить на пары сле­ду­ю­щим спо­со­бом: каж­дую цифру а за­ме­ним на то есть 1 за­ме­ня­ет­ся на 8,2 на 7, 4 на 5 и на­о­бо­рот. На­при­мер, число 42 718 на­хо­дит­ся в паре с чис­лом 57 281. Это раз­би­е­ние хо­ро­шо тем, что сумма цифр в каж­дой паре равна 45 (по­то­му что сумма двух цифр в каж­дом раз­ря­де равна 9).

Оста­лось вы­яс­нить, сколь­ко всего таких пар. Для этого найдём общее ко­ли­че­ство чисел. В пер­вом раз­ря­де может сто­ять любая из шести цифр, во вто­ром  — тоже любая из шести и т. д. Общее ко­ли­че­ство чисел равно А ко­ли­че­ство пар  — и сумма цифр в каж­дой из них  — 45. Общая сумма цифр равна

Ответ: 174 690.

Будем ре­шать обоб­щен­ную за­да­чу. Дано на­ту­раль­ное число n и два не­чет­ных на­ту­раль­ных числа a и b. До­ка­жи­те, что су­ще­ству­ет такое на­ту­раль­ное k, что хотя бы одно из чисел и де­лит­ся на

Вос­поль­зу­ем­ся сле­ду­ю­щим из­вест­ным утвер­жде­ни­ем: пусть число дает оста­ток при де­ле­нии на где Тогда дает оста­ток при де­ле­нии на

Пусть де­лит­ся на и не де­лит­ся на а де­лит­ся на и не де­лит­ся на Оче­вид­но, что при этом Тогда дает оста­ток при де­ле­нии на а дает оста­ток при де­ле­нии на Пусть по­ло­жим для крат­ко­сти По лемме число

дает оста­ток при де­ле­нии на

Будем ре­шать за­да­чу ин­дук­ци­ей по n. Если то нам по­дой­дет по­сколь­ку и дают рав­ные остат­ки при де­ле­нии на Сде­ла­ем пе­ре­ход от n к По ин­дук­ци­он­но­му пред­по­ло­же­нию при не­ко­то­ром k число де­лит­ся на Если оно де­лит­ся и на то пе­ре­ход сде­лан. Иначе оно дает оста­ток при де­ле­нии на Пусть Тогда по лемме дает оста­ток при де­ле­нии на Сле­до­ва­тель­но, дает оста­ток при де­ле­нии на Вос­поль­зу­ем­ся фор­му­лой раз­но­сти сте­пе­ней:

Пер­вая скоб­ка дает оста­ток при де­ле­нии на вто­рая со­сто­ит из r не­чет­ных сла­га­е­мых и, зна­чит, нечётна. Стало быть, раз­ность дает оста­ток при де­ле­нии на Но тогда

де­лит­ся на по­сколь­ку вы­ра­же­ния в скоб­ках дают оди­на­ко­вые остат­ки при де­ле­нии на

Пред­ста­вим все дроби в виде тогда это снова все де­ли­те­ли числа по од­но­му разу. Ча­стич­ные суммы обо­зна­чим через Тогда зна­ме­на­тель не­со­кра­ти­мо­го пред­став­ле­ния ча­стич­ной суммы за­ви­сит от того, в какой сте­пе­ни вхо­дят про­стые мно­жи­те­ли 2 и 3 в чис­ли­тель

Не­слож­но по­нять, что среди есть как чет­ные, так и не­чет­ные числа, по­это­му в не­ко­то­рые двой­ка вхо­дит в ну­ле­вой сте­пе­ни, а в не­ко­то­рые  — в не­ну­ле­вой. Сле­до­ва­тель­но, ответ в за­да­че не мень­ше 2.

При­ве­дем при­мер рас­ста­нов­ки с двумя раз­лич­ны­ми зна­ме­на­те­ля­ми. Вна­ча­ле вы­пи­шем де­ли­тель Затем вы­пи­шем в любом по­ряд­ке все де­ли­те­ли, крат­ные 2 и 3. До этого мо­мен­та все ча­стич­ные суммы ни на 2, ни на 3, т. е. со­дер­жа­ли 2 и 3 в одной и той же (ну­ле­вой) сте­пе­ни, и по­след­няя из них дает оста­ток 1 от де­ле­ния и на 2, и на 3. Оста­лось вы­пи­сать все де­ли­те­ли вида и (k от 1 до 100). Вы­пи­шем спер­ва сте­пе­ни двой­ки, че­ре­дуя и (т. е. сте­пе­ни с чет­ны­ми и не­чет­ны­ми по­ка­за­те­ля­ми). Все по­лу­чен­ные ча­стич­ные суммы будут по-преж­не­му не­чет­ны и не крат­ны трем. На­ко­нец, оста­лось вы­пи­сать сте­пе­ни трой­ки, че­ре­дуя их остат­ки по мо­ду­лю 4 так, чтобы все остав­ши­е­ся ча­стич­ные суммы не де­ли­лись на 4. При этом они оста­нут­ся не крат­ны­ми трем, и двой­ка будет вхо­дить в них не более чем в пер­вой сте­пе­ни! Таким об­ра­зом, в этом при­ме­ре трой­ка вхо­дит во все в ну­ле­вой сте­пе­ни, а двой­ка  — в ну­ле­вой или в пер­вой.

Ответ: два зна­ме­на­те­ля.

Пусть про­стое число p вхо­дит в в k-й сте­пе­ни. До­ка­жем, что де­лит­ся на Тогда утвер­жде­ние за­да­чи будет вы­пол­не­но.

Пусть   — пер­вое число в нашей по­сле­до­ва­тель­но­сти, крат­ное Если то и Сле­до­ва­тель­но,

За­ме­тим, что для будет и вы­ве­ден­ное срав­не­ние тоже вы­пол­не­но. Итак, а даль­ше в по­сле­до­ва­тель­но­сти че­ре­ду­ют­ся остат­ки −1 и 0 от де­ле­ния на p:

и т. д. Более того, как видно из по­след­не­го вы­чис­ле­ния, сте­пе­ни числа p, на ко­то­рые де­лят­ся члены по­сле­до­ва­тель­но­сти, рас­тут: если де­ли­лось на p, то де­лит­ся на и т. д. От­сю­да сле­ду­ет, что если де­лит­ся на то де­лит­ся на Кроме того, учтем, что числа и n оди­на­ко­вой чет­но­сти, по­сколь­ку и остат­ки по мо­ду­лю 2 че­ре­ду­ют­ся. Сле­до­ва­тель­но, де­лит­ся на Оста­ет­ся за­ме­тить, что при (это зна­чит, что су­ще­ствен­но круп­нее n) и так как де­лит­ся на (это зна­чит, что су­ще­ствен­но круп­нее k), по­это­му от­ку­да сле­ду­ет тре­бу­е­мое.

Если ис­ко­мое число n не­чет­но, то все его де­ли­те­ли были бы не­чет­ны, то сумма квад­ра­тов любых пяти его де­ли­те­лей дает оста­ток 5 по мо­ду­лю 8 и по­то­му не может быть точ­ным квад­ра­том. Если число n не крат­но трем, то эта сумма квад­ра­тов дает оста­ток 2 по мо­ду­лю 3 и не может быть точ­ным квад­ра­том. Сле­до­ва­тель­но, n крат­но двум и трём. Тогда среди пяти наи­мень­ших де­ли­те­лей числа n име­ют­ся числа 1, 2, 3 и, воз­мож­но, 6. Если 6 не вхо­дит в число пяти наи­мень­ших де­ли­те­лей, то эти де­ли­те­ли  — 1, 2, 3, 4, 5; сумма их квад­ра­тов равна 55  — не яв­ля­ет­ся точ­ным квад­ра­том. Таким об­ра­зом, че­ты­ре из пяти наи­мень­ших де­ли­те­лей n  — это 1, 2, 3, 6. Зна­чит, среди пяти наи­мень­ших де­ли­те­лей два или три не­чет­ных числа и тогда сумма квад­ра­тов де­ли­те­лей равна 2 или 3 по мо­ду­лю 4, что опять не­воз­мож­но для точ­ных квад­ра­тов.

Ответ: таких чисел не су­ще­ству­ет.

Все воз­мож­ные пары по мо­ду­лю 7  — это (1, 3), (3, 3), (1, 5) и (5, 5).

Ответ: (1, 3), (3, 3), (1, 5), (5, 5).

Если про­из­ве­де­ние де­лит­ся на то можно раз­ло­жить в про­из­ве­де­ние двух таких мно­жи­те­лей что крат­но X, а крат­но Для этого до­ста­точ­но, на­при­мер, по­ло­жить Будем счи­тать, не ума­ляя общ­но­сти, что тогда

Пусть u  — оста­ток от де­ле­ния a на а v  — оста­ток от де­ле­ния b на Y. Тогда от­ку­да Легко по­нять, что де­лит­ся на X, но не де­лит­ся на и де­лит­ся на Y, но явно не де­лит­ся на Сле­до­ва­тель­но, про­из­ве­де­ние де­лит­ся на Таким об­ра­зом, u, v, c  — трой­ка, вы­зы­ва­ю­щая ин­те­рес.

Если де­лит­ся на ab, то n де­лит­ся и на a. Зна­чит, b² де­лит­ся на a. Стало быть, По­ка­жем, что a и k вза­им­но про­сты. Пред­по­ло­жим про­тив­ное. Тогда най­дет­ся такое про­стое число p, что a и k де­лят­ся на p. При этом b² де­лит­ся на p и, зна­чит, b также де­лит­ся на p. За­ме­тим далее, что

де­лит­ся на ab. Тогда де­лит­ся на b и, в част­но­сти, на p. Но это не­воз­мож­но, по­сколь­ку a и k де­лят­ся на p, а 1 не де­лит­ся. Итак, числа a и k вза­им­но про­сты и в про­из­ве­де­нии дают точ­ный квад­рат. Сле­до­ва­тель­но, они сами яв­ля­ют­ся точ­ны­ми квад­ра­та­ми.

Если то всё ясно. Если то по Малой Тео­ре­ме Ферма

Иначе же На­при­мер, по­то­му что из МТФ зна­чит,

Тогда

Слу­чаи раз­би­ра­ют­ся ру­ка­ми.

1)  Когда этот слу­чай де­ла­ет­ся точно так же, как в 3.2;

2)  Когда Тогда

зна­чит, если все остат­ков раз­лич­ны, их сумма не равна 0. Но с дру­гой сто­ро­ны, сум­ми­руя две гео­мет­ри­че­ские про­грес­сии, по­лу­ча­ем

Это вы­ра­же­ние равно 0 по МТФ.

Лемма 1. Пусть про­стое та­ко­во, что для лю­бо­го число xu оста­ток kx от де­ле­ния на q имеют раз­ную чётность. Тогда

До­ка­за­тель­ство леммы 1. Под­став­ляя по­лу­ча­ем, что k чётно, а зна­чит kx все­гда чётно, тогда оста­ток kx имеет ту же чет­ность, что и не­пол­ное част­ное Те­перь под­став­ля­ем тогда и не­чет­но, то есть Те­перь под­став­ля­ем тогда и четно, то етсь Про­дол­жая это, до­хо­дим до ра­вен­ства

что не­воз­мож­но при зна­чит,

След­ствие 1. Пусть q про­стое, k нечётное, не крат­но 2q. Тогда най­дет­ся l такое, что у обоих чисел l, kl остат­ки по мо­ду­лю 2q стро­го между 0 и q.

До­ка­за­тель­ство. Дей­стви­тель­но, по­про­бу­ем в ка­че­стве l все числа от 1 до Пусть все пары l, kl не по­до­шли, то есть все kl имеют остат­ки по мо­ду­лю 2q, боль­шие q. Это зна­чит, что чётность остат­ка kl по мо­ду­лю q про­ти­во­по­лож­на чет­но­сти остат­ка kl по мо­ду­лю 2q (q  — нечётно), а она сов­па­да­ет с чет­но­стью l (т. к. k нечётно) и мы по­па­да­ем в усло­вия леммы.

Пе­рейдём к ре­ше­нию за­да­чи. Пред­по­ло­жим, что все остат­ки раз­лич­ны. По­смот­рим, на по­ряд­ки 2 и 3 по мо­ду­лю p. По МТФ они могут быть равны лишь 1, 2, q, (по­ря­док a по мо­ду­лю p  — ми­ни­маль­ное на­ту­раль­ное k такое, что (или чис­ли­тель со­от­вет­ству­ю­щей не­со­кра­ти­мой дроби, если a  — дробь) крат­но p, это k мы будем обо­зна­чать Пер­вые два слу­чая про­игно­ри­ру­ем, а слу­чаи, когда хотя бы один из по­ряд­ков равен q иден­тич­ны разо­бран­ным в пунк­тах 1 и 3. Пусть по­ряд­ки 2q, в част­но­сти все остат­ки раз­лич­ны (иначе, если 2^a и 2^b дают оди­на­ко­вые остат­ки, то а зна­чит и крат­но p, но и найдётся такое m, что От­ме­тим также, что в этом слу­чае так что если при не­ко­то­ром k имеем то и

так что на­ру­ша­ет­ся усло­вие раз­лич­но­сти остат­ков. По­это­му в нашей по­сле­до­ва­тель­но­сти встре­ча­ют­ся по разу все не­ну­ле­вые остат­ки.

Под­берём по след­ствию 1 такое что −ml при де­ле­нии на 2q имеет оста­ток мень­ше q, назовём этот оста­ток r, де­лит­ся на 2q.

Те­перь изу­чим сумму

по мо­ду­лю p. С одной сто­ро­ны, вы­ра­же­ние в скоб­ках про­бе­га­ет все не­ну­ле­вые остат­ки, а число не крат­но так что эту сумму можно по­счи­тать, как сумму гео­мет­ри­че­ской про­грес­сии с не­по­сто­ян­ным зна­ме­на­те­лем и она равна нулю.

По­счи­та­ем эту же сумму дру­гим спо­со­бом. Рас­крыв все скоб­ки по би­но­му, пе­ре­груп­пи­ро­вав сла­га­е­мые и пе­ре­ста­вив мно­жи­те­ли в по­ка­за­те­лях сте­пе­ней, мы по­лу­чим сумму гео­мет­ри­че­ских про­грес­сий вида

До­ка­жем, что ровно одна из этих про­грес­сий по­сто­ян­на, а зна­чит, ровно одно из ука­зан­ных вы­ра­же­ний не­ну­ле­вое (тут надо от­ме­тить, что так что по­это­му по­яв­ля­ю­щи­е­ся би­но­ми­аль­ные ко­эф­фи­ци­ен­ты не крат­ны p). Это даст тре­бу­е­мое про­ти­во­ре­чие.

Дей­стви­тель­но, при по­лу­ча­ем, учи­ты­вая что так как де­лит­ся на 2q. С дру­гой сто­ро­ны, если при не­ко­то­ром то, деля, по­лу­ча­ем то есть По­лу­ча­ем, что

зна­чит, равен 1 или 2, что может быть лишь при этот слу­чай про­ве­ря­ет­ся не­по­сред­ствен­но.

По МТФ но в то же время и

Слу­чаи раз­би­ра­ют­ся ру­ка­ми. Даль­ше, ана­ло­гич­но преды­ду­щим пунк­там, если то всё ясно. Иначе а тогда для по­лу­ча­ем

Если бы остат­ки не по­вто­ря­лись, каж­дый бы встре­чал­ся по разу, и тогда их сумма была бы равна 0. Но тут, как мы видим, их сумма равна

Слу­чаи раз­би­ра­ют­ся ру­ка­ми. Даль­ше, ана­ло­гич­но преды­ду­щим пунк­там, если то всё ясно. Иначе а тогда для по­лу­ча­ем

Если бы остат­ки не по­вто­ря­лись, каж­дый бы встре­чал­ся по разу, и тогда их сумма была бы равна 0. Но тут, как мы видим, их сумма равна

Лемма 1. Пусть про­стое та­ко­во, что для лю­бо­го число xu оста­ток kx от де­ле­ния на q имеют раз­ную чётность. Тогда

До­ка­за­тель­ство леммы 1. Под­став­ляя по­лу­ча­ем, что k чётно, а зна­чит kx все­гда чётно, тогда оста­ток kx имеет ту же чет­ность, что и не­пол­ное част­ное Те­перь под­став­ля­ем тогда и не­чет­но, то есть Те­перь под­став­ля­ем тогда и четно, то етсь Про­дол­жая это, до­хо­дим до ра­вен­ства

что не­воз­мож­но при зна­чит,

След­ствие 1. Пусть q про­стое, k нечётное, не крат­но 2q. Тогда най­дет­ся l такое, что у обоих чисел l, kl остат­ки по мо­ду­лю 2q стро­го между 0 и q.

До­ка­за­тель­ство. Дей­стви­тель­но, по­про­бу­ем в ка­че­стве l все числа от 1 до Пусть все пары l, kl не по­до­шли, то есть все kl имеют остат­ки по мо­ду­лю 2q, боль­шие q. Это зна­чит, что чётность остат­ка kl по мо­ду­лю q про­ти­во­по­лож­на чет­но­сти остат­ка kl по мо­ду­лю 2q (q  — нечётно), а она сов­па­да­ет с чет­но­стью l (т. к. k нечётно) и мы по­па­да­ем в усло­вия леммы.

Пе­рейдём к ре­ше­нию за­да­чи. Пред­по­ло­жим, что все остат­ки раз­лич­ны. По­смот­рим, на по­ряд­ки 2 и 3 по мо­ду­лю p. По МТФ они могут быть равны лишь 1, 2, q, (по­ря­док a по мо­ду­лю p  — ми­ни­маль­ное на­ту­раль­ное k такое, что (или чис­ли­тель со­от­вет­ству­ю­щей не­со­кра­ти­мой дроби, если a  — дробь) крат­но p, это k мы будем обо­зна­чать Пер­вые два слу­чая про­игно­ри­ру­ем, а слу­чаи, когда хотя бы один из по­ряд­ков равен q иден­тич­ны разо­бран­ным в пунк­тах 1 и 3. Пусть по­ряд­ки 2q, в част­но­сти все остат­ки раз­лич­ны (иначе, если 2^a и 2^b дают оди­на­ко­вые остат­ки, то а зна­чит и крат­но p, но и найдётся такое m, что От­ме­тим также, что в этом слу­чае так что если при не­ко­то­ром k имеем то и

так что на­ру­ша­ет­ся усло­вие раз­лич­но­сти остат­ков. По­это­му в нашей по­сле­до­ва­тель­но­сти встре­ча­ют­ся по разу все не­ну­ле­вые остат­ки.

Под­берём по след­ствию 1 такое что −ml при де­ле­нии на 2q имеет оста­ток мень­ше q, назовём этот оста­ток r, де­лит­ся на 2q.

Те­перь изу­чим сумму

по мо­ду­лю p. С одной сто­ро­ны, вы­ра­же­ние в скоб­ках про­бе­га­ет все не­ну­ле­вые остат­ки, а число не крат­но так что эту сумму можно по­счи­тать, как сумму гео­мет­ри­че­ской про­грес­сии с не­по­сто­ян­ным зна­ме­на­те­лем и она равна нулю.

По­счи­та­ем эту же сумму дру­гим спо­со­бом. Рас­крыв все скоб­ки по би­но­му, пе­ре­груп­пи­ро­вав сла­га­е­мые и пе­ре­ста­вив мно­жи­те­ли в по­ка­за­те­лях сте­пе­ней, мы по­лу­чим сумму гео­мет­ри­че­ских про­грес­сий вида

До­ка­жем, что ровно одна из этих про­грес­сий по­сто­ян­на, а зна­чит, ровно одно из ука­зан­ных вы­ра­же­ний не­ну­ле­вое (тут надо от­ме­тить, что так что по­это­му по­яв­ля­ю­щи­е­ся би­но­ми­аль­ные ко­эф­фи­ци­ен­ты не крат­ны p). Это даст тре­бу­е­мое про­ти­во­ре­чие.

Дей­стви­тель­но, при по­лу­ча­ем, учи­ты­вая что так как де­лит­ся на 2q. С дру­гой сто­ро­ны, если при не­ко­то­ром то, деля, по­лу­ча­ем то есть По­лу­ча­ем, что

зна­чит, равен 1 или 2, что может быть лишь при этот слу­чай про­ве­ря­ет­ся не­по­сред­ствен­но.