Мы будем ис­поль­зо­вать сле­ду­ю­щее утвер­жде­ние: Если два из чисел x, y, z де­лят­ся на не­ко­то­рое на­ту­раль­ное число m, то и тре­тье де­лит­ся на m.

До­ка­за­тель­ство. Пусть на­при­мер x и y де­лят­ся на m.

След­ствие: если одно из чисел x, y, z не де­лит­ся на m, то из остав­ших­ся двух хотя бы одно тоже не де­лит­ся на m. Рас­смот­рим те­перь дан­ные в за­да­че числа:

За­ме­тим, что в пер­вых двух стро­ках все числа чётные, т. е. или Далее, оба числа 18 и 42 де­лят­ся на 3, т. е. Во вто­рой стро­ке нет чисел, де­ля­щих­ся на 3, т. е. Далее, На­ко­нец,

Зна­че­ния воз­мож­ны, на­при­мер, при

Ответ:

Мы будем ис­поль­зо­вать сле­ду­ю­щее утвер­жде­ние: Если два из чисел x, y, z де­лят­ся на не­ко­то­рое на­ту­раль­ное число m, то и тре­тье де­лит­ся на m.

До­ка­за­тель­ство. Пусть на­при­мер x и y де­лят­ся на m.

След­ствие: если одно из чисел x, y, z не де­лит­ся на m, то из остав­ших­ся двух хотя бы одно тоже не де­лит­ся на m. Рас­смот­рим те­перь дан­ные в за­да­че числа:

За­ме­тим, что в пер­вых двух стро­ках все числа чётные, т. е. или Далее, оба числа 18 и 42 де­лят­ся на 3, т. е. Во вто­рой стро­ке нет чисел, де­ля­щих­ся на 3, т. е. Далее, На­ко­нец,

Зна­че­ния воз­мож­ны, на­при­мер, при

Ответ:

За­ме­тим, что 45  — это наи­боль­ший общий де­ли­тель числе 585 и 855. За­ме­тим, что a и b не равны 0, так как числа не могут на­чи­нать­ся с 0. Пред­по­ло­жим, что есть два числа, для ко­то­рых этот НОД боль­ше 45. За­ме­тим, что

де­лит­ся на это НОД. Де­ли­мость на 2 и 5 опре­де­ля­ет­ся по­след­ней циф­рой, то есть b, а она не может быть нулём, так что НОД не может быть од­но­вре­мен­но чётным и де­ля­щим­ся на 5. Тогда Зна­чит, если НОД не де­лит­ся на 3, он не может быть боль­ше или в за­ви­си­мо­сти от слу­чая, ко­то­рый мы раз­би­ра­ем.

Зна­чит, чтобы НОД был боль­ше 45, он дол­жен де­лить­ся на 3, а, зна­чит, ис­ход­ные числа де­лят­ся на 3.

Чтобы число де­ли­лось на 3, числа a и b долж­ны да­вать оди­на­ко­вые остат­ки при де­ле­нии на 3. Зна­чит, при­ни­ма­ет зна­че­ния 3 или 6 а, сле­до­ва­тель­но, НОД яв­ля­ет­ся де­ли­те­лем числа причём по-преж­не­му не может со­дер­жать од­но­вре­мен­но 2 и 5. Если нас ин­те­ре­су­ет НОД, боль­ший 45, он дол­жен де­лить­ся на 9, и, более того, на 27. Зна­чит, число де­лит­ся на 9. При вы­пол­не­нии этого усло­вия, по при­зна­ку де­ли­мо­сти на 9, цифра a прак­ти­че­ски од­но­знач­но опре­де­ля­ет цифру b.

Таким об­ра­зом, в ка­че­стве имеет смысл рас­смот­реть толь­ко числа 171, 252, 333, 414, 585, 666, 747, 828, 909 и 999 (не­ко­то­рые из них не под­хо­дят, так как в част­но­сти, 999. Осталь­ные числа раз­би­ва­ют­ся на две ариф­ме­ти­че­ские про­грес­сии с раз­но­стью 81 каж­дая. По­сколь­ку 81 де­лит­ся на 27, нам до­ста­точ­но про­ве­рить, что 171 и 585 не де­лят­ся на 27 и осталь­ные числа также не будут де­лить­ся. Зна­чит, НОД не де­лит­ся на 27, и 45  — наи­боль­ший ва­ри­ант.

Ответ: 45.

За­ме­тим, что 18  — это наи­боль­ший общий де­ли­тель числе 828 и 882. Пред­по­ло­жим, что есть два числа, для ко­то­рых этот НОД боль­ше 18. За­ме­тим, что

де­лит­ся на это НОД. По­лу­ча­ем так что, чтобы НОД был боль­ше 9, он дол­жен со­дер­жать мно­жи­те­ли как из числа 9, так и из В част­но­сти, чтобы НОД был боль­ше 9, он дол­жен де­лить­ся на 3, а, зна­чит, ис­ход­ные числа де­лят­ся на 3.

Чтобы число де­ли­лось на 3, числа a и b долж­ны да­вать оди­на­ко­вые остат­ки при де­ле­нии на 3. Зна­чит, при­ни­ма­ет зна­че­ния 3, 6 или 9, а, сле­до­ва­тель­но, НОД яв­ля­ет­ся де­ли­те­лем 27, 54 или 81. Если нас ин­те­ре­су­ет НОД, боль­ший 18, он дол­жен де­лить­ся на 9, и, более того, на 27. Зна­чит, число де­лит­ся на 9. При вы­пол­не­нии этого усло­вия, по при­зна­ку де­ли­мо­сти на 9, цифра a прак­ти­че­ски од­но­знач­но опре­де­ля­ет цифру b.

Таким об­ра­зом, в ка­че­стве имеет смысл рас­смот­реть толь­ко числа 117, 225, 333, 441, 558, 666, 774, 882, 990 и 999 (не­ко­то­рые из них не под­хо­дят, так как в част­но­сти, 999. Осталь­ные числа раз­би­ва­ют­ся на две ариф­ме­ти­че­ские про­грес­сии с раз­но­стью 108 каж­дая). По­сколь­ку 108 де­лит­ся на 27, нам до­ста­точ­но про­ве­рить, что 117 и 558 не де­лят­ся на 27 и осталь­ные числа также не будут де­лить­ся. Зна­чит, НОД не де­лит­ся на 27. Таким об­ра­зом, 18  — наи­боль­ший ва­ри­ант.

Ответ: 18.

Ре­ше­ние 1 (пол­ная си­сте­ма вы­че­тов). Пусть p  — мень­шее из про­стых чисел. Тогда Рас­смот­рим целые числа от до Это p по­сле­до­ва­тель­ных чисел, по­это­му все они дают раз­лич­ные остат­ки при де­ле­нии на p. Умно­жим те­перь эти p чисел на q. По­ка­жем, что числа в новом на­бо­ре также будут да­вать раз­лич­ные остат­ки при де­ле­нии на p. Если qa и qb (при дают оди­на­ко­вые остат­ки при де­ле­нии на p, то на­ту­раль­ное число де­лит­ся на p, а зна­чит, и де­лит­ся на p, что не­воз­мож­но, ибо по­ло­жи­тель­но и мень­ше p. Итак, числа в новом на­бо­ре дают раз­лич­ные остат­ки при де­ле­нии на Но по­сколь­ку их всего p, среди них най­дет­ся число, да­ю­щее оста­ток Сле­до­ва­тель­но, мы до­ка­за­ли, что су­ще­ству­ет такое число k, что де­лит­ся на p и Тогда

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

Если то нам по­дой­дут числа и В про­тив­ном слу­чае нам по­дой­дут числа и

Ре­ше­ние 2 (ки­тай­ская тео­ре­ма об остат­ках). Пусть p  — мень­шее из про­стых чисел. По ки­тай­ской тео­ре­ме об остат­ках най­дет­ся такое число a, ко­то­рое де­лит­ся на q и дает при де­ле­нии на p оста­ток 1. За­ме­тим, что любое число вида при целом k также удо­вле­тво­ря­ет этому усло­вию. Под­бе­рем k так, что Тогда число де­лит­ся на q и ре­зуль­тат де­ле­ния мень­ше p, по­это­му наи­боль­ший про­стой де­ли­тель q равен Кроме того, де­лит­ся на p, по­это­му если то наи­боль­ший про­стой де­ли­тель равен p и мы на­пы­ли тре­бу­е­мые числа. Пусть Тогда рас­смот­рим на­ту­раль­ное число Оно де­лит­ся на q и ре­зуль­тат де­ле­ния мень­ше p, по­это­му на­боль­ший про­стой де­ли­тель c равен q. Кроме того

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

Ре­ше­ние 3 (ли­ней­ное пред­став­ле­ние наи­боль­ше­го об­ще­го де­ли­те­ля). Пусть p  — мень­шее из про­стых чисел. По­сколь­ку p и q вза­им­но про­сты, су­ще­ству­ют такие числа a и b, что Но тогда

при любом целом k. Под­бе­рем k так, что Тогда число де­лит­ся на q и мень­ше По­это­му у него нет про­стых де­ли­те­лей, боль­ших Если не имеет про­стых де­ли­те­лей, боль­ших p, то мы нашли тре­бу­е­мую пару чисел: и В про­тив­ном слу­чае за­ме­тим, что и

Тогда число де­лит­ся на q и не пре­вос­хо­дит pq. По­это­му у него нет про­стых де­ли­те­лей, боль­ших q. Если не имеет про­стых де­ли­те­лей, боль­ших p, то мы нашли тре­бу­е­мую пару чисел: и Если же тре­бу­е­мая пара чисел еще не най­де­на, то числа и имеют про­стые де­ли­те­ли, боль­шие p, а, зна­чит,

Про­ти­во­ре­чие.

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

Рас­смот­рим наи­мень­ший про­стой де­ли­тель p числа (это воз­мож­но, т. к. Число вза­им­но про­сто с чис­ла­ми

До­ка­жем, что при и Ис­поль­зу­ем ин­дук­цию по k. База при оче­вид­на. Пе­ре­ход:

При по­след­ний НОД равен 1 и как и тре­бо­ва­лось. При этот НОД равен и

что и тре­бо­ва­лось. Итак, член по­сле­до­ва­тель­но­сти с но­ме­ром ровно в два раза пре­вос­хо­дит свой номер, что про­ти­во­ре­чит пред­по­ло­же­нию.

Мой до­ро­гой Ват­сон, вы не по­ни­ма­е­те, как можно до­га­дать­ся рас­смат­ри­вать наи­мень­ший про­стой де­ли­тель числа Ра­зу­ме­ет­ся, ге­ни­аль­ных до­га­док для ре­ше­ния не тре­бу­ет­ся  — до­ста­точ­но ис­сле­до­вать по­сле­до­ва­тель­ность, сде­лав не­сколь­ко шагов после

На­при­мер,

и видно, что зна­че­ние за­ви­сит от того, де­лит­ся ли на 2. Если де­лит­ся, то   — и это член, ко­то­рый мы ис­ка­ли! Если же нет, то Смот­рим даль­ше:

При­гля­ди­тесь, до­ро­гой друг: от чего за­ви­сит этот НОД? Что Вы го­во­ри­те? От того, де­лит­ся ли на 3? Что ж, Вы правы! Сде­лав еще пару ходов, мы по­лу­чим во­про­сы, де­лят­ся ли на 4, на 5 и так далее. Но го­раз­до при­ят­нее иметь дело с де­ли­мо­стью од­но­го и того же числа, чем кучи раз­ных! Наши де­ли­мо­сти легко пе­ре­фор­му­ли­ро­вать: де­лит­ся ли на 2, на 3, на 4, на 5 и так далее. Пер­вый ответ «да» встре­тит­ся при де­ли­мо­сти на ми­ни­маль­ный про­стой де­ли­тель числа Оста­лось стро­го до­ка­зать по­лу­чен­ную за­ко­но­мер­ность по ин­дук­ции, что и сде­ла­но в ре­ше­нии.

За­ме­ча­ние. При утвер­жде­ние за­да­чи не­вер­но: если то а затем и т. д., при всех В этой по­сле­до­ва­тель­но­сти лишь пер­вые два члена равны своим удво­ен­ным но­ме­рам.

Пред­по­ло­жим, что числа на­пи­сан­ные из­на­чаль­но на доске, пре­вра­ти­лись в три оди­на­ко­вых числа. За­ме­тим, что НОД, при­бав­лен­ный к числу a, яв­ля­ет­ся де­ли­те­лем чисел b и c, а зна­чит, и их раз­но­сти Сле­до­ва­тель­но, он не пре­вос­хо­дит а зна­чит, за­ве­до­мо мень­ше раз­но­сти После при­бав­ле­ния этого НОДа к a по­лу­чи­лось число, мень­шее c, и оно не могло сов­пасть с чис­лом, по­лу­чен­ным из c.

Ответ: не могли.

Пусть d  — наи­боль­ший общий де­ли­тель чисел a и b. По­ло­жим и Тогда числа a₁ и b₁ вза­им­но про­сты,

а де­ли­мость на вле­чет де­ли­мость числа

на и, в част­но­сти, де­ли­мость на d. Сле­до­ва­тель­но, a₁b₁ де­лит­ся на d. За­ме­тим, что n де­лит­ся на a₁ и, зна­чит, де­лит­ся на a₁. Но по­сколь­ку числа a₁ и b₁ вза­им­но про­сты, d де­лит­ся на a₁. Ана­ло­гич­но про­ве­ря­ет­ся, что d де­лит­ся на b₁. Снова ис­поль­зуя вза­им­ную про­сто­ту чисел a₁ и b₁, по­лу­ча­ем, что d де­лит­ся на a₁b₁. Таким об­ра­зом, Стало быть,

Раз­ло­жим числа на про­стые мно­жи­те­ли, так как 3³ встре­ча­ет­ся толь­ко в сле­до­ва­тель­но, ана­ло­гич­но по­лу­ча­ем, что от­сю­да

За­ме­ча­ем, что

Учи­ты­вая три факта:

по­лу­ча­ем, что на­при­мер, при и или на­при­мер, при и

Ответ: 675 или 4725.

Знаем, что (не­чет­ное), сле­до­ва­тель­но, a  — чет­ное, b  — не­чет­ное. Тогда

Сумма чисел не де­лит­ся на 3, сле­до­ва­тель­но, толь­ко одно из чисел может иметь мно­жи­те­ли 3. Толь­ко одно из чисел, чет­ное, может иметь мно­жи­те­ли 2. Оба числа могут иметь мно­жи­тель 17. Таким об­ра­зом, и

Ответ: 68 и 53.

За­ме­тим, что и так как ис­ко­мые числа не де­лят­ся друг на друга, то эти числа могут быть толь­ко и

Ответ: 90 и 126.

Так как и то наи­боль­шее ко­ли­че­ство по­дар­ков равно

Ответ: 66.

Обо­зна­чим и Тогда урав­не­ние за­пи­шет­ся в виде

На­пи­шем еще одно со­от­но­ше­ние, вер­ное для любых целых а и b. По­лу­чим си­сте­му

Оче­вид­но, что ре­ше­ни­ем этой си­сте­мы может быть толь­ко

или

По­сколь­ку НОК все­гда не мень­ше НОДа, вто­рой слу­чай не­воз­мо­жен. Оста­ет­ся

что рав­но­силь­но тому, что b де­лит­ся на a. Тогда

Из этого ра­вен­ства видно, что будет де­лить­ся на тогда и толь­ко тогда, когда яв­ля­ет­ся де­ли­те­лем 10. Зна­чит,

Ответ:

Оче­вид­но, что и по­это­му по­лу­ча­ем три­ви­аль­ную оцен­ку свер­ху. Эта оцен­ка до­сти­га­ет­ся на чис­лах

Ответ:

Пусть су­ще­ству­ют такие раз­лич­ные на­ту­раль­ные числа и b, что Так как

и

то и Сле­до­ва­тель­но, и но та­ко­го быть не может в виду того, что Пред­по­ло­жим те­перь, что и рас­смот­рим числа

Все эти числа раз­лич­ны и их наи­мень­шее общее крат­ное равно Най­дем те­перь их сумму

Ответ: при всех на­ту­раль­ных

Если в каком-то ряду наи­боль­ший общий де­ли­тель равен n, то в нем есть че­ты­ре числа, де­ля­щих­ся на n, a, зна­чит, число, не мень­шее, чем 4n. По­сколь­ку наи­боль­шие общие де­ли­те­ли во всех рядах раз­лич­ны, один из них за­ве­до­мо не мень­ше 8. Тогда в со­от­вет­ству­ю­щем ему ряду долж­но быть число, не ме­ны­шее 32. При­ве­дем те­перь при­мер таб­ли­цы, в ко­то­рой все числа не боль­ше 32. Наи­боль­шие общие де­ли­те­ли по стро­кам равны 5, 6, 7 и 8, а по столб­цам равны 1, 2, 3 и 4.

За­ме­ча­ние. Наи­боль­шие общие де­ли­те­ли за­ве­до­мо долж­ны быть чис­ла­ми от 1 до 8, а ряды с НО­Да­ми 6, 7 и 8 долж­ны быть со­став­ле­ны из тех чисел, ко­то­рые стоят в со­от­вет­ству­ю­щих рядах в таб­ли­це из при­ме­ра (воз­мож­но в дру­гом по­ряд­ке).

Ответ: 32.

Пусть сна­ча­ла За­ме­тим, что y не может де­лить­ся на x, иначе наи­мень­шее общее крат­ное x и y равно y, а это мень­ше В част­но­сти,

Далее, наи­мень­шее общее крат­ное x и y де­лит­ся на x и по­это­му де­лит­ся на x и y, а зна­чит де­лит­ся на y и де­лит­ся на x. Из де­ли­мо­сти на y сле­ду­ет что вме­сте с пред­по­ло­же­ни­ем влечёт Тогда из де­ли­мо­сти на x и сле­ду­ют де­ли­мость 4 на x и воз­мож­но­сти Про­вер­ка по­ка­зы­ва­ет, что ре­ше­ни­ем в этом слу­чае яв­ля­ет­ся

Те­перь рас­смот­рим слу­чай из де­ли­мо­сти на x сле­ду­ет или Если то де­лит­ся на y, тогда 3 де­лит­ся на y и яв­ля­ет­ся ре­ше­ни­ем за­да­чи.

Если то y нечётно, Тогда долж­но де­лить­ся на зна­чит, де­лит­ся на что не­воз­мож­но.

Ответ: или

Если оба числа x и y.одной чётно­сти, то все че­ты­ре сла­га­е­мых x, y, (x, y) и [x, y] имеют ту же чётность и их сумма чётна. Если они имеют раз­ную чётность, то (x, y) нечётно, а [x, y] чётно, по­то­му в сумме будет два чётных и два нечётных числа и она снова будет чётна. Каж­дое её сла­га­е­мое не мень­ше од­но­го, по­это­му вся сумма не мень­ше 4. Сле­до­ва­тель­но, от­ве­том за­да­чи может быть толь­ко чётное число, боль­шее двух. С дру­гой сто­ро­ны, для про­из­воль­но­го чётного по­ло­жив по­лу­чим и от­ку­да   — пред­став­ля­ет­ся в тре­бу­е­мом в усло­вии виде.

Ответ: все чётные числа, боль­шие двух.

При­ве­дем дру­гое ре­ше­ние.

Если обо­зна­чить то где x₁, y₁ вза­им­но про­сты, зна­чит, одно из них обя­за­тель­но нечётно. Тогда

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

Среди этих чисел все­гда найдётся число не мень­шее, чем то есть не мень­ше 41, сле­до­ва­тель­но, наи­мень­шее общее крат­ное всех этих чисел все­гда не мень­ше 41. Если оно равно 41, то, ввиду про­сто­ты числа 41, все эти числа долж­ны быть равны 41 или 1. Но

а зна­чит, та­ко­го быть не может и наи­мень­шее общее крат­ное всех этих чисел не мень­ше 42. При­мер для 42 таков: наи­мень­шее общее крат­ное 42 и 21 равно 42, так как 42 де­лит­ся на 21.

Ответ: 42.

Пред­по­ло­жим, что ука­зан­ная в усло­вии си­ту­а­ция воз­мож­на. За­ме­тим, что числа 30!, 40! и 50! де­лят­ся на 9 оче­вид­ным об­ра­зом, числа 234 и 666 де­лят­ся на 9 по при­зна­ку, так как их суммы цифр де­лят­ся на 9, а вот 111 де­лит­ся на 3, но не де­лит­ся на 9. От­сю­да сле­ду­ет, что числа 40! + 234 и 50! + 666 де­лят­ся на 9, а число 30! + 111 не де­лит­ся на 9. Таким об­ра­зом, наи­боль­шие общие де­ли­те­ли пар чисел b и c, c и а де­лят­ся на 9, от­ку­да сле­ду­ет де­ли­мость на 9 чисел a и b. По­след­нее влечёт де­ли­мость на 9 их наи­боль­ше­го об­ще­го де­ли­те­ля, рав­но­го 30! + 111, ко­то­рое, как мы уста­но­ви­ли, на 9 не де­лит­ся  — про­ти­во­ре­чие. Сле­до­ва­тель­но, ука­зан­ная в усло­вии си­ту­а­ция не­воз­мож­на.

Ответ: нет, не могут.