오일러 피 함수 ϕ(n) | 약수와 서로소의 관계

https://youtu.be/1jE9g3WG9pI

 

재밌는 사실 하나 보여드리겠습니다.

숫자를 하나 가져옵니다.

이 수의 모든 약수를 적습니다.

이 약수보다 작거나 같은 서로소들을 모두 적습니다.

이때 서로소인 수들의 개수는 항상 처음 가져온 수와 같습니다.

 

12

1 - 1

2 - 1

3 - 1, 2

4 - 1, 3

6 - 1, 5

12 - 1, 5, 7, 11

 

안 믿으실까봐 다른 숫자들도 가져오면

모든 숫자가 다 됩니다.

 

9

1 - 1

3 - 1, 2

9 - 1, 2, 4, 5, 7

 

7

1 - 1

7 - 1, 2, 3, 4, 5, 6

 

신기하죠?

 

정수론에서 오일러 피 함수(Euler’s phi(totient) function)는 정수환의 몫환의 가역원을 세는 함수입니다. 즉, n이 양의 정수일 때, ϕ(n)은 n과 서로소인 1부터 n까지의 정수의 개수와 같습니다. 예를 들어, 1부터 6까지의 정수 가운데 1, 5 둘만 6과 서로소이므로, ϕ(6) = 2입니다. 1부터 10까지의 정수는 모두 11과 서로소이며, 11은 자기 자신과 서로소가 아니므로, ϕ(11) = 10입니다. 1은 자기 자신과 서로소이므로, ϕ(1) = 1입니다. 오일러 피 함수는 곱셈적 함수이므로 ϕ(mn)=ϕ(m)ϕ(n)을 만족합니다.