오일러 피 함수 이론 정리

1. 오일러 피 함수란?

$$
φ(n) = n이하\;자연수\;중\;n과\;서로소인\;수의\;개수
$$

$φ(12) \; = \; 4$이다.

2. 사전 학습

오일러 피 함수의 증명을 위해서 다음 챕터에서 오일러의 곱 공식을 살펴볼 것인데, 사전에 학습해야할 내용이 있어서 미리 소개하겠다.

• 1️⃣ 소인수: 임의의 수 K의 소수이면서 인수인 수이다. 예를 들면 12의 소인수는 2와 3 이 있다.
• 2️⃣ 소인수 분해: 임의의 수 K를 소수로만 인수 분해하는 것이다. 예를 들어 12를 소인수 분해하면, $12\,=\,2^{2}\,*\,3$이다.
• 3️⃣ 서로소: A와 B가 서로소라는 뜻은, A와 B의 공약수가 1말고는 없다는 뜻이다.
• 4️⃣ $φ()$: 오일러 파이라고 읽는다.
• 5️⃣ $\prod_{p \mid N}$: 여러 값의 합을 나타내는 ∑ 처럼 여러 값의 곱셈을 나타내는 수학기호 이다.

3. 오일러의 곱 공식

(1) 정의

$$
\phi(N) = N \times \prod_{p \mid N} \left( 1 - \frac{1}{p} \right)
$$

(2) 해설

오일러의 곱 공식의 원리는 1부터 N까지의 숫자 중 소인수와 그 배수를 제외시켜서 결국 소수만 영역안에 남게 하는 것이다. 그리고 그 수를 센다.
위에서 나타낸 p는 N의 소인수를 뜻한다. 해당 식이 파이로 묶여 있으므로 p에는 N의 소인수가 차례대로 들어갈 것이다. 이제 하나씩 드릴링 해보자.

ⓐ N이하의 자연수 중 p의 배수의 개수는 몇 개일까?

그것은 N을 P로 나눈 몫과 같을 것이다. 예를 들어 1이상 12 이하에서 2의 배수의 개수는 6이다. 3의 배수는 4개일 것이다. 따라서 이를 변수화해서 나타낸다면, $\frac{N}{p} (내림)$ 로 나타낼 수 있다.

ⓑ 비율화 해서 나타내기

해당 공식에서는 계산하기 쉽게 N개 중에서 소인수의 배수가 아닌 수의 비율 을 구하고 거기에 N을 곱해 최종적으로 N 이하 N과 서로소인 배수를 구한다.
N이하 자연수 중 소인수 p의 배수가 아닌 수의 비율 을 표현하면 $1 - \frac{1}{p}$와 같을 것이다. 이를 상세히 설명하면 우리가 구하려는 것은
$$
비율\;=\;\frac{P의\;배수가\;아닌\;숫자의\;개수}{전체\;숫자의\;개수}
$$
즉,
$$
비율 = \frac{N - \frac{N}{P}}{N}
$$
분모를 정리하면
$$
비율 = 1 - \frac{1}{P}
$$
가 된다.

이제 하나의 $1 - \frac{1}{p}$의 뜻은 알겠다. 하지만 공식을 보니 파이 기호로 모든 소인수가 아닌 수의 비율을 곱하고 있다. 이건 왜 그럴까?

ⓒ 소인수의 배수가 아닌 수의 비율을 전부 곱하는 이유

이는 포함 배제의 원리 때문이다. 2의 배수와 3의 배수를 지우면서 6의 배수가 2번 지워졌다. 포함 배제의 원리는 집합시간에 배웠을텐데, 기억 안 나는 분이 많을테니 다시 기록하고 가겠다.
$$
∣A∪B∪C∣=∣A∣+∣B∣+∣C∣−∣A∩B∣−∣B∩C∣−∣C∩A∣+∣A∩B∩C∣
$$
즉 두번 중복해서 빼진 값을 한 번 더해서, 계산을 올바르게 유지하는 것이다. 이 포함 배제의 원리는 곱셈 공식에 자연스럽게 녹아 있다.

위의 공식 대로, $φ(12)$를 구해볼까?
$$
ϕ(12)=12×(1− \frac{1}{2})×(1− \frac{1}{3})
$$
여기서 곱 공식을 계산해보면
$$
12×(1 - \frac{1}{2} - \frac{1}{3} + \frac{1}{6})
$$
이다. 이를 글로 풀어보면,
$$
12×(100\% - 2의\,배수의\,비율 - 3의\,배수의\,비율 + 6의\,배수의\,비율)
$$
이다. 자연스럽게 포함 배제의 원리 가 들어가 있다. 따라서 파이를 써서 모든 비율을 곱해야 한다.

소결

이렇게 모든 소인수가 아닌 수의 비율을 곱하면 (즉 파이기호까지만 계산하면) N 이하의 수 중 N과 서로소인 수의 비율이 된다. 여기에 전체 개수인 N을 곱하여 서로소의 개수를 구하면 되는 것이다.
이제 오일러피 함수의 원리를 알아봤으니 이를 JAVA로 구현해보겠다.

4. JAVA로 구현하는 법

(1) 원리

위에서 구한 오일러 피 함수(φ(n))는 하나의 N에 대해서 그것과 서로소인 수의 개수를 구했다. 우리가 할 것은 1부터 N까지 자연수 각각의 φ(k)의 값을 구할 것이다.
이를 위해서 에라토스테네스의 체를 활용한다. 에라토스테네스의 체에서 소수의 배수를 소수 판정 배열에서 false로 바꾸던 것을 소수의 배수가 i이면 arr[i] = arr[i] - arr[i]/P (P는 소수, i는 소수의 배수) 로 바꾸어주면 된다.
이게 왜 가능할까? arr[i] = arr[i] - arr[i]/P1 는 $N×(1-\frac{1}{P_1})$를 풀어 쓴 것과 같다. 여기서 만약 소수 $P_2$도 i를 배수로 가진다면 arr[i] = arr[i] - arr[i]/P2 계산을 한번 더 할 것이다. 이는 $N×(1-\frac{1}{P_1})$ 이란 계산이 끝난 곳에, $(1-\frac{1}{P_2})$를 한번 더 곱하는 것이다. 즉 각 배열의 원소마다
$$
\phi(N) = N \times \prod_{p \mid N} \left( 1 - \frac{1}{p} \right)
$$
계산을 해주는 것이 된다.

(2) SUDO CODE

• 0️⃣ 어디까지 서로소의 개수 찾을 건지 N 입력 받기
• 1️⃣ 에라토스테네스의 체 구현해서 N개의 영역 내의 소수 찾기 ➜ 원래 하듯이 소수 판정 배열 만들기
• 2️⃣ 오일러의 피 수행
  • 2-1) 1번에서 완성한 소수 판정 배열 조회
  • 2-2) 임의의 소수 p를 만나면 해당 소수의 배수들(이하 k)에 대하여 euler_arr[k] = euler[k] - euler_arr[k]/p 해주기

(3) JAVA CODE

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;


public class Main {
    static int N;
    static boolean [] is_prime;
    static int [] euler_arr;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        is_prime = new boolean [N + 1];
        prime_sieve(N);
        euler_phi_f(N);
        System.out.println(Arrays.toString(euler_arr));
    }

    public static void prime_sieve(int n){
        Arrays.fill(is_prime, true);
        for (int i = 2; i <= Math.sqrt(n); i++) {
            if(is_prime[i]){
                for (int j = i*i; j <= n; j*=i) {
                    is_prime[j] = false;
                }
            }
        }
    }

    public static void euler_phi_f(int n){
        euler_arr = new int[n + 1];
        for (int i = 1; i <= N; i++) {
            euler_arr[i] = i;
        }

        for (int i = 2; i <= N; i++) {
            if(is_prime[i]){
                for (int j = i; j <= N; j+=i) {
                    euler_arr[j] = euler_arr[j] - euler_arr[j]/i;
                }
            }
            System.out.println("소수: "+i + "배열 상황: " + Arrays.toString(euler_arr));
        }
    }
}

 

매번 소수를 활용해 오일러의 피 전용 배열을 돌 때마다 콘솔에 찍도록 했으니, 한 줄 씩 확인하며 이해하길 바란다.