Двенадцать из чисел меньше 36 не имеют с ним общего множителя

φ-функция Эйлера как произведение по простым, и те же 12 через включения-исключения в одну строку.

Арифметика и функции · Уровень: Классический результат · Обновлено 2026-11-10

Число целых чисел до 36, не имеющих с ним общего множителя, равно 12. Рецепт произведения берёт 36 и отбрасывает доли, делящиеся на каждый простой множитель: умножьте на (1 − 1/2), чтобы убрать чётные числа, на (1 − 1/3), чтобы убрать кратные трём, и калькулятор покажет 12. Поскольку 36 = 2²·3², эти два простых — единственные, на которые можно делить.

Вторая ссылка считает то же иначе, включениями и исключениями: восемнадцать кратных 2, двенадцать кратных 3 и шесть кратных 6, которые вычтены дважды и потому один раз прибавлены обратно — 36 − 18 − 12 + 6 = 12. Оба рецепта обязаны совпасть, и причина, по которой они совпадают, в том, что «делится на 2 или 3» — это ровно «не взаимно просто с 36». φ — число, на котором работает арифметика RSA: теорема Эйлера говорит a^φ(n) ≡ 1 (mod n) для любого a, взаимно простого с n, так что размер этого подсчёта — размер цикла.

Ответ

12

Как его читать

36·(1 − 1/2)(1 − 1/3) на калькуляторе. Вторая ссылка — подсчёт включениями-исключениями, а третья — разложение 2²·3², которое говорит, какие простые считаются.

Источник

Euler's totient φ(36) = 36(1 − 1/2)(1 − 1/3) = 12, from his 1763 memoir on the function; the product form φ(n) = n·∏(1 − 1/p) over the primes dividing n is the standard result behind RSA key arithmetic

Пересчитать в калькуляторе

Эти ссылки открывают подходящий калькулятор с уже введёнными числами этой задачи. Строка выше — то, что должен показать экран; проверьте сами.

Это независимый сторонний информационный сайт. Он не связан с Casio, Texas Instruments или их дистрибьюторами, не спонсируется ими и не имеет их авторизации. Названия моделей и продуктов — товарные знаки соответствующих правообладателей; они приведены здесь только для идентификации устройств.

Последовательности нажатий клавиш в этих справочниках составлены на основе собственных данных о раскладке этого сайта — тех же данных, которые отображает онлайн-калькулятор, — а также общедоступных сведений о продуктах. Характеристики и региональные конфигурации проверяются на реальном устройстве и по последним материалам производителя.