bulgakov

32. Функция Эйлера

Функция Эйлера φ(n)\varphi(n) считает, сколько чисел от 11 до nn взаимно просты с nn. Чтобы её найти, «вычёркиваем» числа, кратные простым делителям nn, — а сколько вычеркнуто, помогает посчитать принцип включений и исключений. Получается красивая формула: φ(n)=n(1−1p1)⋯(1−1pk)\varphi(n)=n\left(1-\dfrac1{p_1}\right)\cdots\left(1-\dfrac1{p_k}\right), где p1,…,pkp_1,\dots,p_k — простые делители nn.

Что пригодится из прошлого: включения и исключения через свойства — формула E(0)=w(0)−w(1)+w(2)−…E(0)=w(0)-w(1)+w(2)-\dots; формула для nn множеств. Нужно также знать, что такое простое число и разложение на простые множители — коротко напомним ниже. Если эти главы знакомы, читайте дальше. Если нет — загляните по ссылке, потом возвращайтесь.

Напомним слова

  • Числа aa и bb взаимно просты, если у них нет общих делителей, кроме 11 (то есть наибольший общий делитель равен 11). Например, 88 и 1515 взаимно просты, а 88 и 1212 — нет (общий делитель 44).
  • Простое число делится только на 11 и на себя: 2,3,5,7,11,…2,3,5,7,11,\dots
  • Каноническое разложение числа nn — запись n=p1α1p2α2⋯pkαkn=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k}, где p1,…,pkp_1,\dots,p_k — различные простые числа, а αi≥1\alpha_i\ge1 — их показатели. Например, 12=22⋅312=2^2\cdot3 (p1=2p_1=2, α1=2\alpha_1=2, p2=3p_2=3, α2=1\alpha_2=1).

Что такое φ(n)\varphi(n)

Рассмотрим числа 1,2,…,n1,2,\dots,n. Обозначим через φ(n)\varphi(n) количество среди них чисел, взаимно простых с nn (считаем φ(1)=1\varphi(1)=1). Функция φ\varphi называется функцией Эйлера. Для первых чисел:

nn 1 2 3 4 5 6 7 8 9 10 11 12
φ(n)\varphi(n) 1 1 2 2 4 2 6 4 6 4 10 4

Например, φ(8)=4\varphi(8)=4: числа 1,3,5,71,3,5,7; φ(7)=6\varphi(7)=6: все числа от 11 до 66 (у простого числа нет общих делителей ни с одним меньшим).

Идея: вычёркиваем кратные простым делителям

Ключевое наблюдение. Число xx не взаимно просто с nn тогда и только тогда, когда у них есть общий простой делитель (любой общий делитель >1>1 разлагается на простые). Но простые делители nn — это ровно p1,…,pkp_1,\dots,p_k. Поэтому

x взаимно просто с n  ⟺  x не делится ни на одно из p1,…,pk.x\text{ взаимно просто с }n\iff x\text{ не делится ни на одно из }p_1,\dots,p_k.

Для n=12=22⋅3n=12=2^2\cdot3 вычёркиваем числа, кратные 22 или 33, и смотрим, что осталось:

Число 1 2 3 4 5 6 7 8 9 10 11 12
кратно 2 × × × × × ×
кратно 3 × × × ×
осталось ✓ ✓ ✓ ✓

Остались 1,5,7,111,5,7,11, то есть φ(12)=4\varphi(12)=4.

Теорема

Если n=p1α1p2α2⋯pkαkn=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k} — каноническое разложение числа nn, то

φ(n)=n(1−1p1)(1−1p2)⋯(1−1pk)=n∏i=1k(1−1pi).\boxed{\varphi(n)=n\left(1-\frac1{p_1}\right)\left(1-\frac1{p_2}\right)\cdots\left(1-\frac1{p_k}\right)=n\prod_{i=1}^{k}\left(1-\frac1{p_i}\right)}.

(Для n=1n=1 разложение пустое, произведение равно 11, и формула даёт φ(1)=1\varphi(1)=1.)

Доказательство. Пусть S={1,2,…,n}S=\{1,2,\dots,n\}. Для 1≤i≤k1\le i\le k определим подмножества

Si={s∣s∈S и s делится на pi}.S_i=\{s\mid s\in S\text{ и }s\text{ делится на }p_i\}.

По ключевому наблюдению φ(n)\varphi(n) — это число элементов SS, не лежащих ни в одном SiS_i:

φ(n)=∣S1‾∩⋯∩Sk‾∣=∣S∣−∣S1∪⋯∪Sk∣.\varphi(n)=\bigl|\overline{S_1}\cap\dots\cap\overline{S_k}\bigr|=|S|-|S_1\cup\dots\cup S_k|.

Найдём размеры пересечений. Число pip_i делит nn: n=pi⋅mn=p_i\cdot m, поэтому среди 1,…,n1,\dots,n кратны pip_i числа pi⋅1, pi⋅2,…,pi⋅mp_i\cdot1,\,p_i\cdot2,\dots,p_i\cdot m — ровно m=npim=\dfrac n{p_i} чисел: ∣Si∣=npi|S_i|=\dfrac n{p_i}. Число делится на два различных простых pi1p_{i_1} и pi2p_{i_2} тогда и только тогда, когда делится на их произведение; а pi1pi2p_{i_1}p_{i_2} делит nn (оба простых входят в разложение). Поэтому

∣Si1∩Si2∣=npi1pi2, …,∣Si1∩⋯∩Sil∣=npi1⋯pil, …,∣S1∩⋯∩Sk∣=np1p2⋯pk.\begin{gathered} |S_{i_1}\cap S_{i_2}|=\frac{n}{p_{i_1}p_{i_2}},\ \dots,\\ |S_{i_1}\cap\dots\cap S_{i_l}|=\frac{n}{p_{i_1}\cdots p_{i_l}},\ \dots,\\ |S_1\cap\dots\cap S_k|=\frac n{p_1p_2\cdots p_k}. \end{gathered}

Применим принцип включений и исключений в форме E(0)=w(0)−w(1)+w(2)−…E(0)=w(0)-w(1)+w(2)-\dots:

φ(n)=n−∑i=1knpi+∑1≤i1<i2≤knpi1pi2−⋯+(−1)knp1p2⋯pk.\varphi(n)=n-\sum_{i=1}^{k}\frac n{p_i}+\sum_{1\le i_1<i_2\le k}\frac n{p_{i_1}p_{i_2}}-\cdots+(-1)^k\frac n{p_1p_2\cdots p_k}.

Вынесем nn:

φ(n)=n(1−∑i=1k1pi+∑i1<i21pi1pi2−⋯+(−1)k1p1⋯pk).\varphi(n)=n\left(1-\sum_{i=1}^{k}\frac1{p_i}+\sum_{i_1<i_2}\frac1{p_{i_1}p_{i_2}}-\cdots+(-1)^k\frac1{p_1\cdots p_k}\right).

В скобках записан результат раскрытия произведения (1−1p1)⋯(1−1pk)\left(1-\dfrac1{p_1}\right)\cdots\left(1-\dfrac1{p_k}\right): из каждой скобки берём либо 11, либо −1pi-\dfrac1{p_i} — получаются слагаемые по всем наборам индексов, со знаком (−1)число взятых дробей(-1)^{\text{число взятых дробей}}. Значит,

φ(n)=n(1−1p1)(1−1p2)⋯(1−1pk).□\varphi(n)=n\left(1-\frac1{p_1}\right)\left(1-\frac1{p_2}\right)\cdots\left(1-\frac1{p_k}\right).\qquad\square

Примеры

1. n=12=22⋅3n=12=2^2\cdot3: φ(12)=12⋅(1−12)(1−13)=12⋅12⋅23=4\varphi(12)=12\cdot\left(1-\frac12\right)\left(1-\frac13\right)=12\cdot\frac12\cdot\frac23=4. Через включения и исключения: 12−(6+4)+2=412-(6+4)+2=4.

2. n=30=2⋅3⋅5n=30=2\cdot3\cdot5: φ(30)=30⋅12⋅23⋅45=8\varphi(30)=30\cdot\frac12\cdot\frac23\cdot\frac45=8: числа 1,7,11,13,17,19,23,291, 7, 11, 13, 17, 19, 23, 29.

3. Простое число: φ(p)=p(1−1p)=p−1\varphi(p)=p\left(1-\frac1p\right)=p-1.

4. Степень простого: φ(pα)=pα(1−1p)=pα−pα−1\varphi(p^{\alpha})=p^{\alpha}\left(1-\frac1p\right)=p^{\alpha}-p^{\alpha-1}. Например, φ(8)=8−4=4\varphi(8)=8-4=4, φ(27)=27−9=18\varphi(27)=27-9=18.

5. Несократимые дроби. Сколько существует дробей k15\dfrac k{15} с 1≤k≤151\le k\le15, которые нельзя сократить? Это числа kk, взаимно простые с 1515: φ(15)=15⋅23⋅45=8\varphi(15)=15\cdot\frac23\cdot\frac45=8.

Частые ошибки

  • Использовать повторяющиеся простые. В формуле каждое простое число входит один раз, независимо от показателя: φ(12)=12(1−12)(1−13)\varphi(12)=12\left(1-\frac12\right)\left(1-\frac13\right), а не с двумя множителями для 22.
  • Применять формулу к составным pip_i. p1,…,pkp_1,\dots,p_k — именно простые делители.
  • Забыть, что число nn само не взаимно просто с собой (при n>1n>1): в ряду 1,…,n1,\dots,n число nn не считается взаимно простым с nn.
  • Считать φ(1)=0\varphi(1)=0. По определению φ(1)=1\varphi(1)=1.

Проверь себя

1. Найдите φ(100)\varphi(100).

Решение

100=22⋅52100=2^2\cdot5^2, простые делители 22 и 55: φ(100)=100⋅12⋅45=40\varphi(100)=100\cdot\frac12\cdot\frac45=40.

2. Найдите φ(35)\varphi(35).

Решение

35=5⋅735=5\cdot7: φ(35)=35⋅45⋅67=24\varphi(35)=35\cdot\frac45\cdot\frac67=24.

3. Покажите, что φ(p2)=p(p−1)\varphi(p^2)=p(p-1) для простого pp, и вычислите φ(49)\varphi(49).

Решение

φ(p2)=p2(1−1p)=p2−p=p(p−1)\varphi(p^2)=p^2\left(1-\frac1p\right)=p^2-p=p(p-1). При p=7p=7: φ(49)=7⋅6=42\varphi(49)=7\cdot6=42.

4. Сколько существует несократимых дробей k20\dfrac k{20} при 1≤k≤201\le k\le20?

Решение

20=22⋅520=2^2\cdot5: φ(20)=20⋅12⋅45=8\varphi(20)=20\cdot\frac12\cdot\frac45=8.

Итог

  • φ(n)\varphi(n) — число чисел от 11 до nn, взаимно простых с nn; φ(1)=1\varphi(1)=1.
  • Число взаимно просто с nn тогда и только тогда, когда не делится ни на один простой делитель nn.
  • Принцип включений и исключений даёт φ(n)=n−∑npi+∑npipj−⋯=n∏(1−1pi)\varphi(n)=n-\sum\frac n{p_i}+\sum\frac n{p_ip_j}-\dots=n\prod\left(1-\frac1{p_i}\right).
  • φ(p)=p−1\varphi(p)=p-1, φ(pα)=pα−pα−1\varphi(p^\alpha)=p^\alpha-p^{\alpha-1}.
ПрактикаЗагружаем тест…