페르마 소인수분해법

페르마 소인수분해법(Fermat's factorization method)은 홀수 자연수를 제곱의 차를 이용하여 소인수분해하는 알고리즘이다. 피에르 드 페르마가 고안한 방법이다.

이 알고리즘은 제곱합동식$x^{2}\equiv y^{2}{\pmod {N}}$을 이끌어내는 가장 기초적인 방법으로, 이를 응용 및 개량하여 연분수 소인수분해법, 이차 체, 수체 체 등 빠른 소인수분해법이 20세기 말에 개발되었다.

아이디어

모든 홀수 자연수는 두 자연수의 제곱의 차로 나타낼 수 있다.

$N=mn=\left({\frac {m+n}{2}}\right)^{2}-\left({\frac {m-n}{2}}\right)^{2}=x^{2}-y^{2}(m>n,N:{\text{odd}})$

홀수를 자연수의 곱으로 나타내면 두 수는 반드시 홀수여야만 한다. 그러므로 $x,y={\frac {m\pm n}{2}}$는 필연적으로 자연수가 된다. 만약 주어진 자연수가 합성수이면, $N=x^{2}-y^{2},x-y\geq 3$인 순서쌍 $(x,y)$가 존재한다.

따라서 함수 $f(x)=x^{2}-N$을 지정해서 $f(x)=y^{2}$, 즉 함숫값이 제곱수가 되는 조건을 찾는다면 $N=x^{2}-y^{2}=(x+y)(x-y)$ 꼴로 만들 수 있게 된다.

기본 접근

먼저 기준값$a=\lceil {\sqrt {N}}\rceil$을 찾는다. 만약 ${\sqrt {N}}$이 자연수로 딱 떨어진다면 소인수분해는 그 자리서 끝난다. 하지만 상당한 경우 주어진 수는 제곱수가 아니며 이 경우 아래 방법을 따른다.

$f(x)=x^{2}-N,x\in \{a,a+1,\cdots \}$의 값들을 차례대로 계산해서 제곱수를 발견할 때까지 반복한다.

이를테면 $N=161423$을 소인수분해하려고 한다면, $\lceil {\sqrt {N}}\rceil =402$이므로 $x\geq 402$에 대해서 $f(x)=x^{2}-N$을 계산한다.

$f(402)=181,f(403)=986,f(404)=1793,f(405)=2602,f(406)=3413,f(407)=4226,f(408)=5041,\cdots$

위 함숫값들 중 제곱수가 되는 식은 $f(408)=408^{2}-N=71^{2}$이다. 따라서 $N=408^{2}-71^{2}=(408-71)(408+71)=337\cdot 479$임을 알 수 있다.

만약 나누어진 두 수 중 하나라도 여전히 합성수이면 소인수분해를 계속하지만, 둘 다 소수임이 판명나면 소인수분해는 끝난다. 위의 예시에서는 337, 479 모두 소수이다. 만약 직접 나누기를 시도했다면 337 이하의 소수들에 대해 노가다를 행했겠지만, 페르마 소인수분해법으로는 좀 더 수월한 방법으로 풀린다.

직접 나누기 방법은 어떤 합성수의 1보다 큰 가장 작은 약수를 우선순위로 찾는다. 반면 페르마 소인수분해법은 주어진 수의 제곱근(${\sqrt {N}}$)에 가장 가까운 약수를 중심으로 찾으므로 시작점이 전혀 다르다.

참고로 이 알고리즘은 어떤 수가 크기가 비슷한 약수끼리 곱해져 있을 때 아주 쉽게 해를 찾을 수 있다. 가령 $2021=2025-4=45^{2}-2^{2}=43\cdot 47$의 경우, 두 소인수의 차가 작아서 제곱의 차 모양을 한 방에 찾을 수 있다.

물론 $2019=338^{2}-335^{2}=3\cdot 673$과 같이 소인수의 크기가 극과 극으로 벌어져 있으면 직접 나누기보다도 속도가 느려진다. 그러므로 어떤 수를 소인수분해하려 할 때, 먼저 일정 기준 이하의 작은 소수들로 나누어지는지를 확인하고, 그 다음 이 방법을 적용하는 것이 좋다.

다른 접근

사실 여기서 $g(y)=y^{2}+N(y>0)$을 지정해서 함숫값이 제곱수가 되는 경우를 찾아갈 수도 있다. 그렇게 해서 $g(y)=x^{2}$인 $x$를 찾는다면 $N=x^{2}-y^{2}$을 마찬가지로 유도할 수 있다.

하지만 만약 어떤 합성수의 약수가 해당 수의 제곱근에 가까울 경우 위의 기본 접근 방식이 더 빠르다. 이유는 $f(x)=x^{2}-N(\geq 0),g(y)(\geq N)$의 목표는 제곱수를 찾는 것인데, 일반적으로 임의의 자연수는 크기가가 작을 때 제곱수가 출몰할 확률이 크기 때문이다.

만약 위에서 든 예시를 이 변형된 함수로 제곱수 조건을 추적한다면, $g(1)\cdots g(71)$에 이르러서 해가 나온다. 이처럼 페르마 소인수분해법에서는 대개 큰 쪽인 $x$를 독립 변수로 잡는다.

경우의 수 추리기

그런데 위와 같이 제곱수 찾기를 시행할 때, 모든 $x>{\sqrt {N}}$에 대해 일일이 $f(x)$의 값을 조사할 필요는 없다. 이차잉여를 이용하면 제곱수가 불가능한 경우들을 미리 쳐낼 수 있다.

가령 4로 나눈 나머지를 생각할 때, 주어진 홀수 합성수의 경우 나머지가 1 또는 3 두 경우를 생각할 수 있다. 그리고 어떤 자연수의 제곱을 4로 나눈 나머지는 0 또는 1이다. 이를 토대로 아래와 같이 조건을 세울 수 있다.

${\begin{cases}N\equiv 1{\pmod {4}}\Rightarrow x\equiv 1,y\equiv 0{\pmod {2}}\\N\equiv 3{\pmod {4}}\Rightarrow x\equiv 0,y\equiv 1{\pmod {2}}\end{cases}}$

바로 위 문단에서 살핀 예시에서는 161423을 4로 나눈 나머지가 3이므로, (짝수)²-(홀수)² 형태만 알아보면 되므로 실제로 조사할 경우의 수는 절반으로 줄어든다.

이러한 경우의 수 추리기는 소수 또는 소수의 거듭제곱이 기준인 이차잉여를 이용하여 제한 조건을 여러 개 찾을 수 있다. 특히 거듭제곱의 차수가 올라가면 경우의 수를 더 줄일 수 있지만, 제한 조건의 식은 그만큼 복잡해진다.

먼저 이차잉여의 집합인 $R_{m}=\{0\leq r<m:r\equiv x^{2}{\pmod {m}},x\in \mathbb {Z} \}$을 구한다. 그 다음 $N\equiv n{\pmod {m}}$인 나머지$n$을 집합의 각 원소에 더한 새 집합인 $R_{+n,m}=\{0\leq r'<m:r'\equiv r+n{\pmod {m}},r\in R_{m}\}$을 구한다. 그러면 $R_{x^{2},m}=R_{m}\cap R_{+n,m}$이고, 이것이 $x^{2}\equiv y^{2}+N{\pmod {m}}$을 만족할 $x^{2}$의 조건이다.

2의 거듭제곱

2의 거듭제곱 중 제곱수(즉 4의 거듭제곱)를 법으로 하는 이차잉여는 아래 규칙을 따른다.

• $\mod 4:0,1$ (2개)
• $\mod {16}:0,4,8k+1$ (4개)
• $\mod {64}:0,16,32k+4,8k+1$ (12개)
• 0이 아닌 이차잉여는 $4^{n}(8k+1)$ 형태로 써진다.
• $a^{2}\equiv 4^{n}{\pmod {8\cdot 4^{n}}}(n\geq 0)$이면 $a\equiv 2^{n}{\pmod {2\cdot 2^{n}}}$이 성립한다.
• $2\nmid b$일 때, $a^{2}\equiv b^{2}{\pmod {4\cdot 4^{n}}}$이면 $a\equiv \pm b{\pmod {2\cdot 4^{n}}}$이다.

법 64를 예로 들어보자. 모든 나머지 연산은 환 $\mathbb {Z} /64\mathbb {Z}$내에서 이루어진다.

• $N=161423\equiv 15{\pmod {64}}$
• $x^{2}\mod {64}$의 가능한 값은 $R_{64}=\{0,16,4,36,1,9,17,25,33,41,49,57\}$이다.
• $y^{2}+N\mod {64}$의 경우 위 집합의 각 원소에서 각각 15씩을 더하면 된다: $R_{+15,64}=\{15,31,19,51,16,24,32,40,48,56,0,8\}$
• 그러므로 $x^{2}\mod {64}$의 후보는 바로 위 두 집합의 교집합이다.
• $R_{x^{2},64}=R_{64}\cap R_{+15,64}=\{0,16\}$
• 따라서 $x^{2}\equiv 0{\text{ or }}16{\pmod {64}}$과 같이 쓸 수 있다. 그리고 이를 다시 정리하면 $x\equiv 0{\text{ or }}4{\pmod {8}}$이 된다. 좀 더 간단히 쓰면 $x\equiv 0{\pmod {4}}$이다.

이 조건을 이끌어 냄으로써 경우의 수를 4분의 1로 추릴 수 있다. 실제로 $N\equiv 7{\pmod {8}}$이면 $4\mid x$라는 사실은 변하지 않는다. 추가로 $N\equiv 3{\pmod {8}}$이면 $R_{x^{2},64}=\{4,36\}$ 즉 $x^{2}\equiv 4{\pmod {32}}$이며, 이는 $x\equiv 2{\pmod {4}}$와 동치이다.

$y$의 경우 경우의 수가 좀 더 많이 추려진다. 앞서 $R_{x^{2},64}=\{0,16\}$임을 이끌어냈을 때, 각 원소에서 15를 빼면 $R_{y^{2},64}=\{49,1\}$이 나온다. 법 64에 대한 제곱근을 구하면 $R_{y,32}=\{\pm 7,\pm 1\}$ (32개 중 4개 꼴)이 나와서, 경우의 수는 8분의 1로 줄어든다.

참고로 $N\equiv 1{\pmod {4}}$이면 위의 $x,y$의 홀짝이 서로 반대가 되며, 경우의 수도 반대로 각각 8분의 1, 4분의 1로 줄어든다.

3의 거듭제곱

3의 거듭제곱 중 제곱수(즉 9의 거듭제곱)를 법으로 하는 이차잉여는 아래 규칙을 따른다.

• $\mod 9:0,3k+1$ (4개)
• $\mod {81}:0,27k+9,3k+1$ (31개)
• $\mod {729}:0,243k+81,27k+9,3k+1$ (274개)
• 0이 아닌 이차잉여는 $9^{n}(3k+1)$ 형태로 써진다.
• $a^{2}\equiv 9^{n}{\pmod {3\cdot 9^{n}}}(n\geq 0)$이면 $a\equiv \pm 3^{n}{\pmod {3\cdot 3^{n}}}$이 성립한다.
• $3\nmid b$일 때, $a^{2}\equiv b^{2}{\pmod {9^{n}}}$이면 $a\equiv \pm b{\pmod {9^{n}}}$이다.

여기서는 $\mathbb {Z} /81\mathbb {Z}$을 기준으로 접근한다. 2의 거듭제곱 문단과 같은 방법을 쓴다.

• $N=161423\equiv 71{\pmod {81}}$
• $x^{2}\mod {81}$의 가능한 값은 $R_{81}=\{0,9,36,63,1,4,7,\cdots 79\}$이다.
• $y^{2}+N\mod {81}$의 경우 위 집합의 각 원소에서 각각 71씩을 더하면 된다: $R_{+71,81}=\{71,80,26,53,72,75,78,\cdots 69\}$
• 마찬가지로 교집합을 셈해서 $x^{2}\mod {81}$의 후보를 구한다.
• $R_{x^{2},81}=R_{81}\cap R_{+79,81}=\{0,9,36,63\}$
• 따라서 $x^{2}\equiv 0{\pmod {81}}{\text{ or }}x^{2}\equiv 9{\pmod {27}}$과 같이 쓸 수 있다. 그리고 이를 다시 정리하면 $x\equiv 0{\pmod {9}}{\text{ or }}x\equiv \pm 3{\pmod {9}}$가 된다. 좀 더 간단히 쓰면 $x\equiv 0{\pmod {3}}$이다.

위 예시와 같이 $N\equiv 2{\pmod {3}}$이면 $3\mid x$이라는 일정한 결론을 얻을 수 있다. 이는 법의 3의 차수를 올려서 조건을 살펴도 마찬가지다.

반면 $y$의 경우 경우의 수가 꽤 많이 줄어든다. $R_{x^{2},81}=\{0,9,36,63\}$의 각 원소에서 71을 빼면 $R_{y^{2},81}=\{10,19,46,73\}$을 도출한다. 이를 다시 쓰면 $y^{2}\equiv 10{\pmod {81}}{\text{ or }}y^{2}\equiv 19{\pmod {27}}$이며, 제곱근을 구하면 $y\equiv \pm 35{\pmod {81}}{\text{ or }}y^{2}\equiv \pm 10{\pmod {27}}$이 나온다. 즉 경우의 수는 81개 중 8개 꼴로 추려진다.

참고로 $N\equiv 1{\pmod {3}}$이면 위의 $x,y$의 3의 배수 여부는 서로 반대가 되며, 경우의 수도 반대로 각각 81분의 8, 3분의 1로 줄어든다.

5와 20, 100

소수가 커지면 조건식도 복잡해지며, 차수를 올림으로써 경우의 수를 줄이는 이점은 적어진다. 그래서 큰 소수의 이차잉여는 1차 내에서 조건식을 간단히 하는 편이 낫다. 물론 5의 경우 십진법의 특수성을 활용하여 법 20 또는 법 100을 편리하게 활용할 수 있다.

• $\mod 5:0,1,4$ (3개)
• $\mod {20}:0,5,1,4,9,16$ (6개)
• $\mod {100}:0,25,20k+1,20k+4,20k+9,20k+16$ (18개)
• $a^{2}\equiv 0{\text{ or }}25{\pmod {100}}\Leftrightarrow a\equiv 0{\text{ or }}5{\pmod {10}},(5\nmid b)a^{2}\equiv b^{2}{\pmod {20}}\Leftrightarrow a^{2}\equiv \pm b{\pmod {10}}$

$N=161423\equiv 3{\pmod {20}}$이라는 사실에 착안해서 앞선 문단과 같은 방법으로 제한 조건을 찾는다. 그러면 $x^{2}\equiv 4{\pmod {20}},y^{2}\equiv 1{\pmod {20}}$이 되어 $x\equiv \pm 2{\pmod {10}},y^{2}\equiv \pm 1{\pmod {10}}$이 된다.

이처럼 20으로 나눈 나머지를 활용하면 $x,y\mod {10}$, 즉 일의 자리를 도출할 수 있다. 그런데 만약 $N\equiv \pm 1{\pmod {5}}$이면, 경우의 수는 더 줄어든다.

이를테면 $N\equiv 29{\pmod {100}}$이면 $N\equiv 9{\pmod {20}}$이므로 $R_{(x^{2},y^{2}),20}=\{(9,0),(5,16)\}$이 나온다. 첫째 경우, $y^{2}\equiv 0{\pmod {20}}\Rightarrow y^{2}\equiv 0{\pmod {100}}$이다. 그러므로 $x^{2}\equiv 29{\pmod {100}}\Rightarrow x\equiv 23{\pmod {50}}$임을 알 수 있다. 둘째 경우, $x^{2}\equiv 5{\pmod {20}}\Rightarrow x^{2}\equiv 25{\pmod {100}}$이며 여기서는 $x\equiv 5{\pmod {10}}$ 이 된다.

이렇게 놓고 보면 $R_{x,50}=\{23,27,5,15,25,35,45\}$가 되어 경우의 수는 50개 중 7개 꼴로 줄어든다. 한편 같은 방법으로 접근하면 $y^{2}\equiv 0{\text{ or }}96{\pmod {100}}$이며, $y\equiv 0{\pmod {10}}{\text{ or }}y\equiv \pm 14{\pmod {50}}$라는 사실을 알 수 있다.

그 밖의 소수

법 7, 11, 13에 대한 이차잉여는 아래와 같다.

• $\mod 7:0,1,2,4$ (4개)
• $\mod 11:0,1,3,4,5,9$ (6개)
• $\mod 13:0,1,3,4,9,10,12$ (7개)

홀수 소수$p$를 법으로 하는 이차잉여로 경우의 수를 줄인다면 $x,y\mod p$의 가짓수는 ${\frac {p\pm 1}{2}}$개가 된다.

즉 제한 조건을 하나를 추가할 때마다 경우의 수는 대략 절반씩 줄어든다는 사실을 알 수 있다.

적용 예

앞서 아이디어 문단에서 든 예시에서 수 크기를 올려보자. $N=1724881$을 제곱의 차를 이용하여 소인수분해를 한다. 이 예시는 위에서 소개한 이차잉여를 이용한 경우의 수 추리기가 진가를 발휘한다.

먼저 독립변수의 시작점은 $x\geq \lceil {\sqrt {N}}\rceil =1314$부터 셈한다.

• $N\equiv 17{\pmod {64}}$. 이차잉여의 교집합을 구하면 $R_{x^{2},64}=R_{64}\cap R_{+17,64}=\{0,16,4,36,1,9,17,\cdots 57\}\cap \{17,33,21,53,18,26,34,\cdots 10\}=\{17,33\}$. 따라서 $x^{2}\equiv 17{\text{ or }}33{\pmod {64}}$이고, 법 64에 대한 제곱근을 구하면 $x\equiv \pm 9{\text{ or }}\pm 15{\pmod {32}}$임을 알 수 있다. (①)
• $N\equiv 67{\pmod {81}}$. 마찬가지로 이차잉여의 교집합을 구한다. $R_{x^{2},81}=R_{81}\cap R_{+67,81}=\{0,9,36,63,1,4,7,\cdots 79\}\cap \{67,76,22,49,68,71,74,\cdots 65\}=\{67,76,22,49\}$ 그러므로 $x^{2}\equiv 67{\pmod {81}}{\text{ or }}x^{2}\equiv 22{\pmod {27}}$임을 알 수 있으며, 이를 풀면 $x\equiv \pm 38{\pmod {81}}{\text{ or }}x\equiv \pm 7{\pmod {27}}$이다. (②)
• $N\equiv 81{\pmod {100}}$. 위에서 소개한 법 100 관련 문단을 이용하면 $x^{2}\equiv 81{\text{ or }}25{\pmod {100}}$임을 알 수 있고, 이는 곧 $R_{x,50}=\{9,41,5,15,25,35,45\}$임을 뜻한다. (③)

여기서 7, 11, 13으로 나눈 나머지 등으로 조건을 더 세울 수 있지만, 여기서는 위 세 조건으로 경우의 수를 걸러본다.

• 앞서 구한 $x\geq 1314$와 조건 ③을 먼저 조합하면 $x$의 후보는 다음과 같다.
• $x\in \{1315,1325,1335,1341,1345,1355,1359,1365,1375,1385,1391,1395,1405,1409,\cdots \}$
• 그 다음 조건 ①을 불러와서 32로 나눈 나머지가 9, 15, 17 또는 23인 값들만을 추린다.
• $x\in \{1335,1359,1385,1391,1425,1455,1495,1545,1559,1585,1591,1609,1615,1641,1655,\cdots \}$
• 그리고 조건 ②를 이용하여 81로 나눈 나머지가 38 또는 43이거나, 27로 나눈 나머지가 7 또는 20인 경우만을 고른다.

이렇게 목록을 추리다 보면 남는 후보 중 가장 작은 수는 $x=1559$이다. 그런데 이 경우 $f(x)=x^{2}-N\Rightarrow f(1559)=1559^{2}-1724881=705600$인데 마침 이 값은 840의 제곱이다! $x$의 후보를 이차잉여로 거르고 나서 함숫값을 대입했더니 한 방에 해를 찾은 케이스다. 물론 자연수의 크기가 커지면 함숫값 대입을 여러 번 하는 경우도 많아진다.

이와 같이 해를 찾고 나면 $N=1559^{2}-840^{2}\Rightarrow 1724881=719\cdot 2399$임을 알 수 있다. 719와 2399는 둘 다 소수이므로, 소인수분해는 여기서 종료한다.

소수 판정

이 소인수분해법을 변형하면 소수판정법으로 구성할 수 있다. 직접 나누기로 소인수분해 및 소수 판정이 모두 가능한 것과 같은 맥락이다.

어떤 홀수 자연수가 임의의 상수 $c$에 대해 $N=x^{2}-y^{2},x-y\geq c$인 자연수 $x,y$의 해가 존재하지 않으면 $c\leq a\leq {\sqrt {N}},a\mid N$인 약수 $a$도 존재하지 않는다.

홀수 자연수의 경우 1 다음으로 가장 작은 약수는 3 이상이다. 그러므로 $N=x^{2}-y^{2},x-y\geq 3$인 자연수 해가 존재하지 않으면 주어진 자연수는 홀수임을 알 수 있다. $x-y\geq 3\Rightarrow x+y={\frac {N}{x-y}}\leq {\frac {N}{3}}$이므로 $x$의 허용 범위는 $x\leq {\frac {3}{2}}+{\frac {N}{6}}\approx {\frac {N}{6}}$이다.

하지만 이렇게만 접근하면 효율은 떨어진다. $N$이 커질수록 허용 범위도 자연수 크기에 비례하여 넓어지기 때문. 가령 $N=250013$이 소수인지 알아보려면 $501\leq x<41671$ 범위에 대해 조사를 해야 한다. 그런데 주어진 홀수가 3, 5, 7, 11, 13의 배수가 아니라는 사실은 직접 나누기 내지는 배수판정법 등으로 쉽게 알 수 있을 것이다. 이에 착안해서 "가능한 가장 작은 약수는 그 다음 소수인 17"로 조건을 내린다면, $x-y\geq 17,x+y\leq {\frac {N}{17}}\Rightarrow x\leq {\frac {17}{2}}+{\frac {N}{34}}$가 되므로 허용 범위를 $501\leq x<7362$과 같이 사전에 좁힐 수 있다. 그리고 직접 나누는 소수의 범위를 넓히면 $x$의 범위는 더 좁아진다.

다시 말해 3 이상의 적절한 상수 $c$를 잡아서, $3\leq a\leq c$ 구간에서는 직접 나누기로, $c<a\leq {\sqrt {N}}$ 구간에서는 제곱의 차로 약수의 존재성을 조사하면 된다. 그리고 두 구간에서 모두 약수를 찾을 수 없게 되면, 주어진 자연수는 소수임이 판명난다.

소수 판정 예시

위의 예시($N=250013$)에서 $c=47$로 잡고 이 상수 이하의 소수로는 나누어떨어지지 않음을 알고 있다고 간주하자. 그러면 47 다음 소수는 53이므로 $53\leq a\leq {\sqrt {N}}<501$범위에서 약수가 전무함을 보이면 된다.

$x-y\geq 53,x+y\leq {\frac {N}{53}}\Rightarrow x<2386$이므로, $x\in \{501,502,\cdots 2385\}$(ⓐ) 내에서 후보들을 소거해 나간다.

다음 단계는 이차잉여를 이용한 제한 조건 찾기이다. 앞서 '적용 예' 문단과 같은 방법으로 경우의 수를 추린다.

• $N\equiv 29{\pmod {64}},R_{64}=\{0,16,4,36,1,9,17,\cdots 57\},R_{+29,64}=\{29,45,33,1,30,38,46,\cdots 22\},R_{x^{2},64}=\{33,1\}$이므로 $x^{2}\equiv 33{\text{ or }}1{\pmod {64}}\Rightarrow x\equiv \pm 15{\text{ or }}\pm 1{\pmod {32}}$이다. 정리하면 $R_{x,32}=\{1,15,17,31\}$
• $N\equiv 2{\pmod {3}}$이면 $x\equiv 0{\pmod {3}}$이라는 정보만을 알 수 있다.
• 위의 두 조건을 연립하면 $R_{x,96}=\{3,45,51,93\}$임을 알 수 있다. (①)
• $N\equiv 13{\pmod {20}}\Rightarrow x\equiv \pm 3{\pmod {10}}$이다. 즉 일의 자리는 3 또는 7. (②)
• $N\equiv 1{\pmod {7}},R_{7}=\{0,1,2,4\},R_{+1,7}=\{1,2,3,5\},R_{x^{2},7}=\{1,2\}$이므로 위와 같은 방법으로 $R_{x,7}=\{1,3,4,6\}$을 도출한다. (③)
• $N\equiv 5{\pmod {11}},R_{11}=\{0,1,3,4,5,9\},R_{+5,11}=\{5,6,8,9,10,1\},R_{x^{2},11}=\{1,5,9\}$이므로 $R_{x,11}=\{1,3,4,7,8,10\}$이다. (④)

이제 위 조건들을 토대로 ⓐ에서 구한 x의 후보를 소거해간다.

• 조건 ①을 만족하는 값들을 남기면 $x\in \{525,531,573,579,621,\cdots 2355\}$
• 조건 ②를 만족하는 값들은 $x\in \{573,627,717,723,813,\cdots 2307\}$
• 다음으로 조건 ③, ④를 이어서 적용하면 남는 후보는 $x\in \{573,813,1053,1107,1203,1917,2157,2307\}$이다.
• 남는 후보들을 $f(x)=x^{2}-N$에 대입하여 제곱수 여부를 알아본다. 하지만 확인해보면 어떤 함숫값도 제곱수가 아님을 알 수 있다.

이로써 $N=(x-y)(x+y),53\leq x-y\leq 501$을 만족하는 자연수 $x,y$는 존재하지 않음을 알 수 있다. 그리고 맨 처음에 둔 전제인 '3 이상 47 이하의 약수는 없다'는 조건까지 포함하면, 250013은 소수임을 알 수 있다.

같이 보기

• 오일러 소인수분해법