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

1. 페르마의 소정리(Fermat's little Theorem)

 

1-1) p가 소수이고, a가 p의 배수가 아니면( = a와 p가 서로소이면  = gcd(a,p) = 1)이면,

 

$$a^{p-1} \equiv 1 (mod p)$$ 이다.

 

1-2) p가 소수이면, 모든 정수 a에 대하여 $$a^{p} \equiv a (mod p)$$

 

응용하는 방법은 여러가지가 있겠지만, 하나하나 다 나열할 수도 없고, 접한지 얼마 안되었으니 나도 다 모르고

 

증명도 굳이 할 필요없을 것 같고, 받아들이면서

 

문제를 풀면서 익혀보기로 하자

 

 

2. 응용 - 합성수 판정

 

페르마의 소정리 역은 성립하지 않는다.

 

즉, a와 p가 서로소일때, $$a^{p-1} \equiv 1 (mod p)$$ 가 성립한다면, p는 소수이다는 거짓이다.

 

즉, a,p가 서로소이면서 p가 합성수인데 $$a^{p-1} \equiv 1 (mod p)$$ 를 만족하는 수는 무한히 많다는 것이 증명되어 있다.

 

페르마의 소정리 대우는 

 

어떤 수 n이 적당한 a에 대해 $$a^{n} \not\equiv a (mod n)$$ 이면, n은 합성수이다.

 

그러므로, n이 합성수라는 것은 확실하게 판정할 수 있다.

 

 

3. 응용 - 모듈로 곱셈의 역원

 

사실 페르마 소정리의 가장 중요한 응용중 하나로 반드시 익혀야 하는 부분인데,

 

먼저 합동식에서 양변에 같은 수를 곱해도 성립한다

 

즉, $a \equiv b (mod m)$이면, 어떤 정수 c에 대하여 $ac \equiv bc (mod m)$는 항상 성립한다.

 

여기서 중요한건 c가 정수라는 것임

 

그러니까 c가 실수면 성립하지 않아

 

자꾸 실수하는 부분..

 

합동식하면 기본적으로 정수만 다룬다는 점을 생각해야함

 

곱했는데 왜 나머지가 달라지지? 실수를 곱한건 아닌지 생각해보자.

 

------------------------------------------------------------------------------------------------------------------

 

이거의 연장선상으로 합동식에서 양변을 어떤 수로 나누는 것은 일반적으로 성립하지 않는다.

 

즉, $ac \equiv bc (mod m)$이라고 해서, 어떤 정수 c에 대해 $a \equiv b (mod m)$은 성립하지 않는다.

 

그러면 합동식에서 어떤 정수 a로 나눌려면 어떤 경우에 가능한가?

 

$$a \times a^{-1} \equiv 1 (mod m)$$

 

를 만족하는 $a^{-1}$가 존재해야, mod m에 대한 연산에서 정수 a로 나눌 수 있다.

 

그것이 가능할려면, a와 m이 서로소인경우에만 가능한 것이 알려져있다.

 

----------------------------------------------------------------------------------------------------------------------

 

그러면 $a^{-1}$를 어떻게 구하는지가 하나의 관심사이다.

 

가장 기본 형태는 m이 소수일때 페르마의 소정리를 이용하는 것이다.

 

m이 소수이고 a와 m이 서로소이면 완벽하게 페르마의 소정리에 의해 $a^{m-1} \equiv 1 (mod m)$이다.

 

그러므로, $$a \times a^{m-2} \equiv 1 (mod m)$$

 

따라서, $a^{-1} = a^{m-2}$

 

그러므로, m이 소수이고 a,m이 서로소이면 합동식의 양변을 a로 나누는 것은 양변에 $a^{m-2}$를 곱하는 것과 같다.

 

 

4. 연습문제

 

24059번: Function (acmicpc.net)

24059번: Function

 

$f(0) = a_{0}$이고, $f(i) = a_{i}^{f(i-1)}$일때, f(n)을 m으로 나눈 나머지를 구하는 문제

 

 

5. 풀이

 

n이 0,1,2 3가지밖에 없다.

 

n이 0이면 단순히 $f(0) = a_{0}$이므로, $a_{0} mod m$을 구하면 된다.

 

n이 1이면 $f(1) = a_{1}^{a_{0}}$이므로, 거듭제곱을 하면서, 나머지를 취하는 방식으로 빠르게 나머지를 구할 수 있다

 

from sys import stdin

#분할정복을 이용한 거듭제곱
def power(a,f,m):
    
    result = 1

    while f >= 1:
        
        if f % 2 == 1:
            
            result *= a
        
        a *= a

        a %= m

        f = f // 2
    
    return result % m

n = int(stdin.readline())

a_list = list(map(int,stdin.readline().split()))

m = int(stdin.readline())

if n == 0:
    
    print(a_list[0] % m)

elif n == 1:
    
    print(power(a_list[1],a_list[0],m))

 

근데 문제는 n=2인 경우이다.

 

n=2인 경우, $f(2) = a_{2}^{f(1)}$이다.

 

그런데 a,n,m이 너무 커서 f(1)을 구해버리면 시간안에 당연히 못구함

 

여기서 m이 소수이기 때문에 페르마의 소정리를 생각해보자.

 

$a_{2}, m$이 서로소이면, $$a_{2}^{m-1} \equiv 1 (mod m)$$

 

그래서 $f(1) = a_{1}^{a_{0}}$을 m-1로 나눈 나머지 f(1) mod (m-1)은 로그 시간에 구할 수 있다는 것은 알고있다.

 

이것을 이용해보자.

 

f(1) mod(m-1)은 f(1)을 m-1로 나눈 나머지이다.

 

그렇다면, f(1)을 어떻게 표현할 수 있을까?

 

f(1)을 m-1로 나눈 몫을 p라고 하면, $$f(1) = (m-1)p + f(1) (mod(m-1))$$

 

따라서 우리가 구하고자 하는 값은..?

 

$$f(2) = a_{2}^{(m-1)p + f(1)(mod(m-1))}$$ 을 m으로 나눈 나머지이다.

 

이제 여기서 여러가지로 나뉜다.

 

만약에, f(1)이 m-1보다 작다면? 그러면 p=0이므로, f(2)를 m으로 나눈 나머지는..?

 

$$f(2) = a_{2}^{f(1)(mod(m-1))}$$ 을 m으로 나눈 나머지와 같다.

 

f(1)(mod(m-1))은 로그 시간에 구할 수 있어서, 마찬가지로 f(2)도 로그 시간에 구해진다.

 

이번엔 f(1)이 m-1보다 크다면? p가 1 이상이므로, $f(2) = a_{2}^{(m-1)p + f(1)(mod(m-1))}$을 구해야한다.

 

식을 조금 변형해보면..

 

$$f(2) = a_{2}^{(m-1)p} \times a_{2}^{f(1)(mod(m-1))}$$

 

그러면, f(2) mod m은... 합동식의 곱셈 성질로부터

 

$$[a_{2}^{(m-1)p} (mod m) \times a_{2}^{f(1)(mod(m-1))} (mod m)] (mod m)$$

 

 

$a_{2}^{f(1)(mod(m-1))} (mod m)$은 아주 빠른 시간에 구할 수 있고, 문제는 이제 $a_{2}^{(m-1)p} (mod m)$이다.

 

이제 여러가지 경우로 나뉜다.

 

만약에 $a_{2}$와 m이 서로소라면?

 

그러면 페르마의 소정리에 의해.. $a_{2}^{m-1} \equiv 1 (mod m)$이므로, 거듭제곱을 해도 변함없으므로,

 

$a_{2}^{(m-1)p} \equiv 1 (mod m)$이다.

 

서로소인 것을 어떻게 알 수 있을까?

 

m이 소수이므로, $a_{2}$가 m보다 큰지, 작은지 판단해야한다.

 

만약에 $a_{2}$가 m보다 크다면? $a_{2}$를 m으로 나눈 나머지가 0이 아니라면... 서로소라는 뜻이다.

 

하지만 나머지가 0이라면?

 

그러면 우리는 $$a_{2} \equiv 0 (mod m)$$ 를 얻는다.

 

그러므로 당연히, $a_{2}$를 양변에 계속 곱해서, $$a_{2}^{f(1)} \equiv 0 (mod m)$$ 이다.

 

 

그런데, $a_{2}$가 m보다 작거나 같을 수 있다.

 

그런 경우에는 m이 소수이므로, $a_{2}$가 m과 같으면 서로소가 아니고, m과 다르면 서로소가 된다.

 

이때, $a_{2}$가 m과 같다면?

 

그러면 $a_{2} \equiv 0 (mod m)$이므로, $$a_{2}^{f(1)} \equiv 0 (mod m)$$

 

따라서... 최종 코드는..

 

from sys import stdin

def power(a,f,m):
    
    result = 1

    while f >= 1:
        
        if f % 2 == 1:
            
            result *= a
        
        a *= a

        a %= m

        f = f // 2
    
    return result % m

n = int(stdin.readline())

a_list = list(map(int,stdin.readline().split()))

m = int(stdin.readline())

if n == 0:
    
    print(a_list[0] % m)

elif n == 1:
    
    print(power(a_list[1],a_list[0],m))

else:
    
    result = 1

    big = False
    
    #f(1)이 m-1보다 큰가 작은가?
    for _ in range(1,a_list[0]+1):
        
        result *= a_list[1]
        
        if result > m-1:
            
            big = True
            break
    
    f1mod = power(a_list[1],a_list[0],m-1)
    
    #f(1)이 m-1보다 작다.
    if big == False:
        
        print(power(a_list[2],f1mod,m))
    
    #f(1)이 m-1보다 크거나 같다
    else:
        
        #a2가 m보다 크다면?
        if a_list[2] > m:
            
            #a2랑 m이 서로소일려면, 나누어 떨어지지 않는다
            if a_list[2] % m != 0:
                
                print(power(a_list[2],f1mod,m))
            
            #a2랑 m이 서로소가 아님
            #a2는 m으로 나누어 떨어지므로 나머지가 0
            else:
                
                print(0)
        
        #a2가 m보다 작거나 같다면...
        else: 
            
            #a2와 m이 같다면 당연히 나머지가 0이다
            if a_list[2] == m:
                
                print(0)
            
            #m이 소수이므로, a2와 m이 서로소이다.
            else:
            
                print(power(a_list[2],f1mod,m))

 

참조

 

페르마의 소정리 - 나무위키 (namu.wiki)

페르마의 소정리 - 나무위키

 

정수론 (4) - 합동식에서의 나눗셈 (tistory.com)

정수론 (4) - 합동식에서의 나눗셈

 

 

나머지 연산의 곱셈 역원 (acmicpc.net)

나머지 연산의 곱셈 역원

 

합동식 - 나무위키 (namu.wiki)

합동식 - 나무위키