프로젝트 오일러 134번

Consider the consecutive primes \(p_1=19\) and \(p_2=23\). It can be verified that \(1219\) is the smallest number such that the last digits are formed by \(p_1\) whilst also being divisible by \(p_2\).

In fact, with the exception of \(p_1-3\) and \(p_2=5\), for every pair of consecutive primes, \(p_2 > p_1\), there exist values of \(n\) for which the last digits are formed by \(p_1\) and \(n\) is divisible by \(p_2\). Let \(S\) be the smallest of these values of \(n\).

Find \(\sum S\) for every pair of consecutive primes with \(5 \le p_1 \le 1000000\).

---

연속적인 소수 \(p_1=19, \; p_2=23\) 에 대하여 \(1219\) 는 다음과 같은 성질이 있다. 끝자리가 \(p_1\) 으로 끝나며 \(1219\) 자체는 \(p_2\) 로 나누어 떨어진다.

사실 \(p_1 = 3, \; p_2 = 5\) 을 제외한 모든 연속적인 소수 쌍 \(p_1, \; p_2 \;\;(p_2 >p_1 )\) 에 대해서 끝자리가 \(p_1\) 으로 끝나고, \(p_2\) 로 나누어 떨어지는 자연수 \(n\) 이 존재한다. \(S\) 는 이런 \(n\) 의 최솟값이라고 한다. 

\(5 \le p_1 \le 1000000\) 에 해당하는 연속적인 소수 쌍 \(p_1,\; p_2\) 에 대하여 \( \sum S\) 를 구하시오.

\(p_1\)이 \(d\) 자리 자연수라고 한다면 우리가 찾는 \(n\) 은 다음과 같은 형태로 표현이 가능하다.

\[10^d \times x + p_1 = p_2 \times k\;\; (단,\; k\;는 \; 정수)\]

\[10^d \times x = p_2 \times k - p_1\]

결국 \(10^d \times x\) 는 \(p_2\) 로 나누었을 때의 나머지가 \(- p_1\) 이란 뜻이 된다. 나머지를 \([0, \;p_2)\) 범위에서 생각하려면 \[10^d \times x = p_2 \times k + (p_2 - p_1)\] 의 형태로 바꾸면 된다. 이를 합동식으로 표현하면 다음과 같다. \[ 10^d \times x \equiv p_2-p_1 \;({\rm mod}\; p_2)\] 

합동식 풀이법을 사용하여 위 식을 만족하는 \(x\) 를 구해내면 된다. 

반드시 위 합동식 풀이법 링크를 따라가서 내용을 숙지하고 와야 한다. 

이 풀이법에서 사용된 확장 유클리드 알고리즘을 나타내는 함수만 공개하도록 하겠다.

def extnded_euclidean(a, b):
    (fx, x) = (1, 0)
    (fy, y) = (0, 1)
    while b != 0:
        q = a // b
        
        temp = b
        b = a % b
        a = temp

        temp = x
        x = fx - q * x
        fx = temp

        temp = y
        y = fy - q * y
        fy = temp
    return fx