Пусть   — раз­ло­же­ние числа на про­стые мно­жи­те­ли. за­ме­тим, что среди чисел от 1 до n ровно крат­ны p₁, ровно крат­ны p₁p₂ и так далее. В таком слу­чае ко­ли­че­ство чисел, вза­им­но про­стых с n, можно найти по фор­му­ле вклю­че­ния и ис­клю­че­ния  — нужны те, ко­то­рые не крат­ны ни од­но­му из чисел p₁, p₂,  ... ,  p_s. Их име­ет­ся

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

будет целым.

а)  Если n не­чет­но, то чис­ли­тель этой дроби не­че­тен, а зна­ме­на­тель четен, по­сколь­ку все суть чет­ные числа (ведь все p_i не­чет­ны). Зна­чит, дробь не может быть целым чис­лом.

б)  Из пунк­та а) сле­ду­ет, что один из про­стых мно­жи­те­лей дол­жен быть двой­кой, а кроме него может быть мак­си­мум один не­чет­ный про­стой мно­жи­тель, иначе зна­ме­на­тель будет кра­тен 4, а чис­ли­тель не будет. То есть либо (для таких чисел либо и тогда

Итак, это част­ное не пре­вос­хо­дит трех и равно трем, на­при­мер, при

в)  Как видно из пунк­та б), хо­ро­ши­ми будут толь­ко числа вида при­чем   — целое число, от­ку­да Во­прос те­перь свел­ся к тому, сколь­ко чисел может быть в воз­рас­та­ю­щей ариф­ме­ти­че­ской про­грес­сии, если все они имеют вид Оче­вид­но, числа 2, 4, 6, 8 дают при­мер че­ты­рех чисел.

До­пу­стим, что есть при­мер из пяти чисел. Если все они четны  — по­де­лим их все на 2 и будем де­лить даль­ше, пока это воз­мож­но. Итак, можно счи­тать, что среди чисел есть не­чет­ное. Если все они не­чет­ны, то все они сте­пе­ни трой­ки. Возь­мем под­ряд три из них, 3^a, 3^b, 3^c. По свой­ству ариф­ме­ти­че­ской про­грес­сии

по­лу­ча­ем про­ти­во­ре­чие. Зна­чит, чет­ные среди них тоже есть. Тогда раз­ность про­грес­сии не­чет­на. Зна­чит, чет­ные и не­чет­ные числа в про­грес­сии че­ре­ду­ют­ся. Если не­чет­ных чле­нов три (пер­вый, тре­тий и пятый), то они сами тоже об­ра­зу­ют ариф­ме­ти­че­скую про­грес­сию, что, как мы ви­де­ли, не­воз­мож­но. Тогда их два и они стоят на вто­ром и чет­вер­том ме­стах. Итак, и В этом слу­чае раз­ность про­грес­сии равна и

по­сколь­ку и по­то­му

Ответ: а)  нет; б)  3; в)  4.

При­ме­ча­ние Дмит­рия Гу­щи­на.

Вни­ма­тель­ный чи­та­тель сразу узна­ет в функ­цию Эй­ле­ра. Эта функ­ция имеет важ­ное зна­че­ние в тео­рии чисел. На­зва­на в честь Лео­нар­да Эй­ле­ра, ко­то­рый ввел ее в се­ре­ди­не 18 века для до­ка­за­тель­ства малой тео­ре­мы Ферма и ее обоб­ще­ния  — тео­ре­мы са­мо­го Эй­ле­ра.