오일러 파이 함수

오일러 파이 함수란

 = 1부터 n까지의 양의 정수 중에 n과 서로소인 것의 개수를 나타내는 함수이다

로 정의되는 함수이다.

이러한 파이 함수에는 여러가지 성질이 발견되는데

우선 곱의 함수라는 점이다.

이에 대한 증명은 에라토스테네스의 채와 비슷하게 정수들을 쭉 나열한 다음, 서로소가 아닌 수들을 지워나가면 규칙을 찾을 수 있다.

이러한 파이 함수의 값을 구하는 방법에는 여려가지가 있겠지만,

우선 특정 N에 대해 구한다고 생각하면

N의 소인수들을 다 구한 다음  이 공식을 사용하면 된다.

1~ 까지 파이 함수의 값을 구하기 위해서는,

소수판별을 할때 에라토스테네스의 채 기법을 사용한다.

pi[i] = i;

for (int i=2;i<=N;i++) {

if (pi[i] == i)  { // 소수인 경우

pi[i] = i - 1;

for (int j=i+i;j<=N;j+=i) pi[j] = pi[j] * (i-1) / i;

}

}

와 같이 구할 수 있다.

시간복잡도는 n lg lg n이다.

이러한 파이 함수와 관련된 법칙이 있는데, 바로 오일러의 정리이다.

만약 a와 n이 서로소이고 n이 자연수이면 다음이 성립한다.

특히 n이 소수일때는 pi(n) = n-1 이기때문에 페르마 소정리 a^(p-1) = 1 (mod p)가 성립한다.

이를 통해서 서로소인 a와 n에 대해 모듈러 inverse을 계산 할 수 있다.

서로소인 a와 n에 대해 모듈러 인버스를 다른 방식으로 계산 할 수 있는 방법도 있는데, 이는 확장유클리드 알고리즘을 이용한 방식이다.

확장 유클리드란

ax + by = gcd(a,b)를 만족하는 정수해 x,y 를 찾기 위한 알고리즘으로 

이를 위의 식에 적용시키면

a*x + n*y = gcd(a, n) = 1 을 만족시키는 정수해를 찾을 수 있고

양변을 모듈러 n연산을 씌우면

a*x = 1 (mod n)이라는 식이 만들어 진다.

여기서 x는 법 n에 대해 a의 곱셈에대한 역원이 된다.

임의의 수 N에 대해 pi를 구하는 방법

imsi = N;

for (j=2;j*j<=imsi;j++) if (imsi % j == 0) {

while(!(imsi %j)) imsi /= j;

pi = pi / j * (j-1)

}

if (imsi > 1) { // 소수

pi = pi / imsi * (imsi - 1)

}