Число целых чисел до 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
Пересчитать в калькуляторе
Эти ссылки открывают подходящий калькулятор с уже введёнными числами этой задачи. Строка выше — то, что должен показать экран; проверьте сами.