프로젝트 오일러 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