오일러 피(파이) 함수(Euler's phi function)

오일러 피(파이) 함수 ϕ(n)

1~n까지의 수 중에서 n과 서로소인 수의 갯수

※ 서로소 관계: 두 수 a, b의 공약수가 1뿐인 두 정수를 의미한다.

    ϕ(1) = 1 (1은 1과 서로소)

    ϕ(8) = { 1, 3, 5, 7 } = 4개

    ϕ(13) = = 12개

    ϕ(13) = = 12개

    ϕ(15) = = 8개 

 

성질

① pk에서 p가 소수이며, k가 1 이상의 자연수 일 때,

    ϕ(p) = p−1. 역으로, ϕ(n) = n−1 이면, n은 소수이다.

    ex)  ϕ(7) = = 7 - 1 = 6개

 

② a가 p의 배수이다 = pk와 a가 서로소가 아니다.

    pk이하의 p의 배수가 아닌 수는 pk-pk-1개 존재, 이것은 ϕ(pk ).

    → ϕ(pk ) = (p-1) × pk-1 = pk - pk-1

    ex) ϕ(9) = ϕ(3*3) = (3-1) * 3 = = 6개

 

③ m과 n이 서로소라면, ϕ(mn)=ϕ(m)ϕ(n)이다. 

    ex) ϕ(30) = ϕ(6)ϕ(5) = ϕ(2)ϕ(3)ϕ(5) = 1 * 2 * 4 = 8

    ex) ϕ(12) = ϕ(4)ϕ(3) = (4-2)*(3-1) = 2 * 2 = 4

    ex) ϕ(6) = ϕ(2)ϕ(3) = (2-1)*(3-1) = 1 * 2 = 2

 

※ 참고

 

관련 문제

[BOJ] 4355 서로소 → ϕ(N)을 구하는 문제

[BOJ] 백준 4355 서로소

[SWEA] 3954 파이의 합 → ϕ(1) ~ ϕ(N) 합을 구하는 문제

[SWEA] 3954 파이의 합