Функция Эйлера φ(n) считает, сколько чисел от 1 до n взаимно просты с n. Чтобы её найти, «вычёркиваем» числа, кратные простым делителям n, — а сколько вычеркнуто, помогает посчитать принцип включений и исключений. Получается красивая формула: φ(n)=n(1−p11)⋯(1−pk1), где p1,…,pk — простые делители n.
Что пригодится из прошлого:включения и исключения через свойства — формула E(0)=w(0)−w(1)+w(2)−…; формула для n множеств. Нужно также знать, что такое простое число и разложение на простые множители — коротко напомним ниже. Если эти главы знакомы, читайте дальше. Если нет — загляните по ссылке, потом возвращайтесь.
Напомним слова
Числа a и bвзаимно просты, если у них нет общих делителей, кроме 1 (то есть наибольший общий делитель равен 1). Например, 8 и 15 взаимно просты, а 8 и 12 — нет (общий делитель 4).
Простое число делится только на 1 и на себя: 2,3,5,7,11,…
Каноническое разложение числа n — запись n=p1α1p2α2⋯pkαk, где p1,…,pk — различные простые числа, а αi≥1 — их показатели. Например, 12=22⋅3 (p1=2, α1=2, p2=3, α2=1).
Что такое φ(n)
Рассмотрим числа 1,2,…,n. Обозначим через φ(n) количество среди них чисел, взаимно простых с n (считаем φ(1)=1). Функция φ называется функцией Эйлера. Для первых чисел:
n
1
2
3
4
5
6
7
8
9
10
11
12
φ(n)
1
1
2
2
4
2
6
4
6
4
10
4
Например, φ(8)=4: числа 1,3,5,7; φ(7)=6: все числа от 1 до 6 (у простого числа нет общих делителей ни с одним меньшим).
Идея: вычёркиваем кратные простым делителям
Ключевое наблюдение. Число x не взаимно просто с n тогда и только тогда, когда у них есть общий простой делитель (любой общий делитель >1 разлагается на простые). Но простые делители n — это ровно p1,…,pk. Поэтому
xвзаимнопростосn⟺xнеделитсянинаодноизp1,…,pk.
Для n=12=22⋅3 вычёркиваем числа, кратные 2 или 3, и смотрим, что осталось:
Число
1
2
3
4
5
6
7
8
9
10
11
12
кратно 2
×
×
×
×
×
×
кратно 3
×
×
×
×
осталось
✓
✓
✓
✓
Остались 1,5,7,11, то есть φ(12)=4.
Теорема
Если n=p1α1p2α2⋯pkαk — каноническое разложение числа n, то
(Для n=1 разложение пустое, произведение равно 1, и формула даёт φ(1)=1.)
Доказательство. Пусть S={1,2,…,n}. Для 1≤i≤k определим подмножества
Si={s∣s∈Sиsделитсянаpi}.
По ключевому наблюдению φ(n) — это число элементов S, не лежащих ни в одномSi:
φ(n)=S1∩⋯∩Sk=∣S∣−∣S1∪⋯∪Sk∣.
Найдём размеры пересечений. Число pi делит n: n=pi⋅m, поэтому среди 1,…,n кратны pi числа pi⋅1,pi⋅2,…,pi⋅m — ровно m=pin чисел: ∣Si∣=pin. Число делится на два различных простыхpi1 и pi2 тогда и только тогда, когда делится на их произведение; а pi1pi2 делит n (оба простых входят в разложение). Поэтому
В скобках записан результат раскрытия произведения (1−p11)⋯(1−pk1): из каждой скобки берём либо 1, либо −pi1 — получаются слагаемые по всем наборам индексов, со знаком (−1)числовзятыхдробей. Значит,
φ(n)=n(1−p11)(1−p21)⋯(1−pk1).□
Примеры
1.n=12=22⋅3: φ(12)=12⋅(1−21)(1−31)=12⋅21⋅32=4. Через включения и исключения: 12−(6+4)+2=4.
2.n=30=2⋅3⋅5: φ(30)=30⋅21⋅32⋅54=8: числа 1,7,11,13,17,19,23,29.
3. Простое число: φ(p)=p(1−p1)=p−1.
4. Степень простого: φ(pα)=pα(1−p1)=pα−pα−1. Например, φ(8)=8−4=4, φ(27)=27−9=18.
5. Несократимые дроби. Сколько существует дробей 15k с 1≤k≤15, которые нельзя сократить? Это числа k, взаимно простые с 15: φ(15)=15⋅32⋅54=8.
Частые ошибки
Использовать повторяющиеся простые. В формуле каждое простое число входит один раз, независимо от показателя: φ(12)=12(1−21)(1−31), а не с двумя множителями для 2.
Применять формулу к составным pi.p1,…,pk — именно простые делители.
Забыть, что число n само не взаимно просто с собой (при n>1): в ряду 1,…,n число n не считается взаимно простым с n.
Считать φ(1)=0. По определению φ(1)=1.
Проверь себя
1. Найдите φ(100).
Решение
100=22⋅52, простые делители 2 и 5: φ(100)=100⋅21⋅54=40.
2. Найдите φ(35).
Решение
35=5⋅7: φ(35)=35⋅54⋅76=24.
3. Покажите, что φ(p2)=p(p−1) для простого p, и вычислите φ(49).
Решение
φ(p2)=p2(1−p1)=p2−p=p(p−1). При p=7: φ(49)=7⋅6=42.
4. Сколько существует несократимых дробей 20k при 1≤k≤20?
Решение
20=22⋅5: φ(20)=20⋅21⋅54=8.
Итог
φ(n) — число чисел от 1 до n, взаимно простых с n; φ(1)=1.
Число взаимно просто с n тогда и только тогда, когда не делится ни на один простой делитель n.
Принцип включений и исключений даёт φ(n)=n−∑pin+∑pipjn−⋯=n∏(1−pi1).