오일러의 정리를 배우고 거듭제곱의 나머지를 구하는 방법 익히기

1. 오일러의 정리(Euler's theorem)

 

a와 n이 서로소인 양의 정수이면, 다음이 성립한다

 

$$a^{\varphi(n)} \equiv 1 (mod n)$$

 

여기서 $\varphi(n)$은 n에 대한 오일러 phi 함수이다.

 

서로소가 아니라면 다음과 같이 쓸 수 있다.

 

$$a^{\varphi(n) + 1} \equiv a (mod n)$$

 

n이 소수 p이면, $\varphi(p) = p-1$이므로, a,p가 서로소이면 $a^{p-1} \equiv 1 (mod p)$이다.

 

페르마의 소정리는 오일러의 정리의 특수한 케이스이다.

 

 

2. 거듭제곱을 어떤 정수로 나눈 나머지

 

$a^{n}$을 어떤 정수 p로 나눈 나머지는 어떻게 구할 수 있을까?

 

$a^{n}$을 직접 계산한 다음에, p로 나눈 나머지를 구하는게 가장 쉬운 방법이지만.. a,n이 너무 크다면 시간이 매우 오래 걸린다는 것은 이미 공부한 사실

 

 

2-1) modular exponentiation

 

a,n이 너무 크다면, 시간이 매우 오래걸린다.

 

분할정복을 이용한 거듭제곱방법에서 매번 a를 곱해나갈때, p로 나눈 나머지를 곱해나간다.

 

이는 $ab (mod p) \equiv (a (mod p) \times b (mod p)) (mod p)$를 이용하는 것이다.

 

def power(a,n,mod):
    
    result = 1
    
    while n >= 1:
        
        if n % 2 == 1:
            
            result *= a
            
            result %= mod
        
        a *= a
        
        a %= mod
        
        n = n//2
    
    return result

 

 

혹은 파이썬에서 내장함수로 pow()함수는 세번째 인자로 mod를 제공하는데..

 

pow(a,n,mod)

 

로 사용해도 동일한 결과를 내놓는다..

 

 

2-2) 오일러의 정리 활용

 

n이 너무 크다면 더 효과적인 방법이 있는데 다음과 같다.

 

지수 n을 $\varphi(p)$로 나눈 나머지는 $n (mod \varphi(p))$

 

나머지를 알면, n을 다음과 같이 바꿔쓸수 있다.

 

$$n = \varphi(p) \times q + n (mod \varphi(p))$$

 

물론 q는 1이상의 정수이다.

 

 

1) 여기서 q가 0이라면 $n < \varphi(p)$이고, 이 경우에는 2-1)의 modular exponentiation 방법을 이용해 구해야한다.

 

물론 이진수를 이용해 고속 거듭제곱 방법이 있다는데 당장 필요한 것 같지는 않으니 생략하고

 

 

2) q가 1이상이라면, $n >= \varphi(p)$이다. 그래서 다음 방법은 $n >= \varphi(p)$일때만 성립한다.

 

$a^{n} (mod p)$은 다음과 같이 쓸 수 있다.

 

$$a^{\varphi(p) \times q + n (mod \varphi(p))} (mod p)$$

 

지수법칙에 의해 곱셈으로 바꿀 수 있다.

 

$$a^{\varphi(p) \times q} \times a^{n (mod \varphi(p))} (mod p)$$

 

그러면 $$a^{n (mod \varphi(p))} (mod p)$$는 2-1) modular exponentiation을 이용해 빠른 시간에 구할 수 있고

 

이제 문제는 $$a^{\varphi(p) \times q} (mod p)$$이다.

 

만약 a,p가 서로소이면 오일러의 정리에 의해

 

$$a^{\varphi(p)} \equiv 1 (mod p)$$이 성립하므로 $$a^{\varphi(p) \times q} \equiv 1(mod p)$$

 

그런데 a,p가 서로소가 아니라면?

 

임의의 자연수 a,p에 대하여 $$a^{\varphi(p)} \equiv a^{2\varphi(p)} (mod p)$$라고 한다.

 

공부 저장소 :: 백준 온라인 저지 - 13970. Power towers (tistory.com)

백준 온라인 저지 - 13970. Power towers

 

"중국인의 나머지 정리"를 이해해야해서 이거는 아직 공부하지 않았으니..

 

증명은 생략하고 아쉽지만 일단 받아들이기로... 언젠가 기회가 있겠지.?

 

p가 소수일때는 다음과 같이 생각은 해본적 있으니까 일단 여기에 만족

 

페르마의 소정리 문제 풀어보면서 익히기 (tistory.com)

페르마의 소정리 문제 풀어보면서 익히기

 

아무튼 결국에 임의의 자연수 a,p,q에 대하여 다음이 성립할 것이다.

 

$$a^{\varphi(p)} \equiv a^{2\varphi(p)} \equiv a^{3\varphi(p)} ... \equiv a^{q\varphi(p)}$$

 

따라서 다음과 같이 정리할 수 있다.

 

임의의 자연수 a,n,p에 대하여 $a^{n} (mod p)$를 구하는 문제는 다음과 같이 해결해볼 수 있다.

 

 

$n >= \varphi(p)$라면, 

 

$$a^{n} \equiv a^{\varphi(p) + n (mod \varphi(p))} (mod p)$$

 

$n < \varphi(p)$라면, 

 

$$a^{n} \equiv a^{n (mod \varphi(p))} (mod p)$$

 

 

3. 연습문제

 

24009번: Huge Numbers (acmicpc.net)

24009번: Huge Numbers

 

$a^{n!}$을 p로 나눈 나머지를 구하는 문제

 

 

4. 풀이

 

먼저 생각한 풀이는 $a^{n!}$은, n!이 $1\times2 \times3 \times...\times n$이므로,

 

$(((((a^{1})^{2})^{3})...)^{n})$으로 나눌 수 있고 그래서 $a^{i}$을 p로 나눈 나머지를 i = 1부터 i=n까지 반복적으로 구하면 된다고 생각했다.

 

from sys import stdin

def power(a,n,mod):
    
    result = 1
    
    while n >= 1:
        
        if n % 2 == 1:
            
            result *= a
            
            result %= mod
        
        a *= a
        
        a %= mod
        
        n = n // 2
    
    return result % mod
    

T = int(stdin.readline())

for t in range(1,T+1):

    a,n,p = map(int,stdin.readline().split())

    value = 1

    for i in range(1,n+1):
        
        value = power(a,i,p)
        
        a = value % p

    print(f'Case #{t}: {a}')

 

value = power(a,1,p)를 구하면.. $a^{1}$ mod p인데.. 이걸 다시 a에 넣어서 다음 반복문에 i = 2를 넣어서 power구하면..

 

$((a^{1})^{2})$ mod p겠지..

 

이걸 n까지 하면 $a^{n!}$이 될 것이다.

 

직접 만든 power 대신에 pow함수 쓰면 조금 더 빠르다

 

from sys import stdin

T = int(stdin.readline())

for t in range(1,T+1):

    a,n,p = map(int,stdin.readline().split())

    value = 1

    for i in range(1,n+1):
        
        value = pow(a,i,p)
        
        a = value % p

    print(f'Case #{t}: {a}')

 

이번엔 오일러 phi함수를 이용해서 한번 해보자

 

오일러 phi함수는 이전에 공부한대로 구현하고

 

from sys import stdin

def phi(n):
    
    result = n

    p = 2

    while p*p <= n:
        
        if n % p == 0:
            
            while n % p == 0:
                
                n = n//p
            
            result -= result // p
        
        p += 1
    
    if n > 1:
        
        result -= result // n
    
    return result

 

다음에 a,n,p를 받고 p의 phi값을 구한다음에, n!을 구해야하는데.. 

 

$n >= \varphi(p)$라면, 

 

$$a^{n} \equiv a^{\varphi(p) + n (mod \varphi(p))} (mod p)$$

 

$n < \varphi(p)$라면, 

 

$$a^{n} \equiv a^{n (mod \varphi(p))} (mod p)$$

 

에 따라 나뉘잖아

 

그래서 매번 phi(p)로 나눠주면서 곱해나가서 n!을 구하면 뭐가 더 큰지 알 수 없겠지

 

그러니까 n!을 구하기 위해 1부터 n까지 일단 곱해

 

그런데 곱하는 중에 n!이 phi(p) 이상인 순간이 온다면... 크다는 지표값을 True로 바꿔주고,

 

크면 이제 phi(p)로 나눠주자

 

그리고 크다는 지표값이 True라면, phi(p)값을 더해주고, 아니라면 안더해주면 그만

 

그리고 pow함수를 이용해서 나머지를 구해주면 끝

 

 

T = int(stdin.readline())

for t in range(1,T+1):
    
    a,n,p = map(int,stdin.readline().split())

    phi_p = phi(p)

    n_factorial = 1

    big = False

    for i in range(1,n+1):
        
        n_factorial *= i

        #n!을 구하는 와중에 n! >= phi(p)라면...

        if n_factorial >= phi_p:
            
            big = True

            n_factorial %= phi_p
    
    #n! >= phi(p)라면.. phi_p를 더해줘야함
    if big:
        
        n_factorial += phi_p
    
    print(f'Case #{t}: {pow(a,n_factorial,p)}')

 

 

참조

 

 

페르마(Fermat), 오일러(Euler) 정리 / Primality test - Miller-Rabin Algorithm 설명 및 Python 코드 구현 (tistory.com)

페르마(Fermat), 오일러(Euler) 정리 / Primality test - Miller-Rabin Algorithm 설명 및 Python 코드 구현

 

오일러 정리 - 나무위키 (namu.wiki)

오일러 정리 - 나무위키

 

Modular exponentiation - Wikipedia

Modular exponentiation - Wikipedia

 

공부 저장소 :: 백준 온라인 저지 - 13970. Power towers (tistory.com)

백준 온라인 저지 - 13970. Power towers

 

4. 페르마 소정리, 오일러 정리 및 활용 :: rkm0959 (tistory.com)

4. 페르마 소정리, 오일러 정리 및 활용