백준 13319번 해설

II-eugene-II Note

백준 13319번 - 가짜 소수

백준 13319번 문제 링크
문제 이름 : 가짜 소수
주 언어 : Python
추가 언어 : TEXT
태그 : 수학 / 정수론 / 구성적 / 소수 판정 / 런타임 전의 전처리 / 페르마의 소정리
solved.ac 등급 : Gold I (2023/02/11 확인)

문제 보기

문제 :

지구이는 우연히 오일러 프로젝트에서 100억 정도의 매우 큰 숫자가 소수인지 판별해야만 풀리는 문제를 보게 되었다. 지구이는

$2$ 부터

$\sqrt{N}$ 까지 모든 숫자로 나누는 방법으로 코딩했지만, 1시간이 지나도 결과가 나오지 않았다. 결국 구글신에게 물어본 결과 “페르마 소정리”를 찾을 수 있었다. 페르마 소정리는 다음과 같다.

“소수

$p$ 와

$\gcd(a, p) = 1$ 인 모든 자연수

$a$ 에 대하여,

$a^{p - 1} \equiv 1 \pmod{p}$ 이다.”

지구이는 이것을 응용해서

$n$ 이 소수인지 확인하기 위해

$2^{n - 1} \equiv 1 \pmod{n}$ 이면 소수라고 판별하기로 했다. 하지만 지구이의 코드는

$561$ 을 소수로 분류했고, 결국 또 틀리고 말았다. 이대로 포기할 수 없었던 지구이는 이것을 응용해서

$2$ 부터

$500$ 까지의 모든 숫자

$a$ 에 대하여

$a^{p-1} \equiv 1 \pmod{p}$ 을 만족할 때만 소수로 판별하기로 했다. 백만까지 컴퓨터로 확인을 해본 지구이는 자신만만하게 답을 제출했지만, 빨간 X표시가 반겨줄 뿐이었다.
지구이에게 반례 데이터를 알려주자!
지구이의 소수판별 코드는 여기에 있다.

입력 :

입력은 없다.

출력 :

첫 번째 줄에 자연수

$n$ (

$500 < n \leq 10^{15}$ )과

$n$ 의 소인수

$m$ (

$1 < m < n$ )을 출력한다. (출력 예시는 답이 아님에 주의하라.)

문제에서 $2^{n - 1} \equiv 1 \pmod{n}$ 을 만족하는 가장 작은 합성수인 Poulet Number $341$ 대신 가장 작은 카마이클 수 $561$ 을 예시로 준 지점에서 힌트를 얻을 수 있습니다.
$\gcd(a, n) = 1$ 인 모든 $a$ 에 대하여 $a^{n - 1} \equiv 1 \pmod{n}$ 인 합성수 $n$ 이 카마이클 수 이므로, 문제에서 $2 \leq a \leq 500$ 인 모든 $a$ 에 대하여 $a^{n - 1} \equiv 1 \pmod{n}$ 이려면 카마이클 수 $n$ 의 가장 작은 소인수가 $500$ 보다 커야한다는 것을 알 수 있습니다.
카마이클 수인지를 판단하기 위해서 코셀트 판정법 을 응용하여 $6m + 1$ , $12m + 1$ , $18m + 1$ 이 모두 소수 라면 $(6m + 1) (12m + 1) (18m + 1)$ 은 카마이클 수라는 정리를 이용해줍니다.
이 때는 $6m + 1 > 500$ 이면 되므로, 편의상 $m = 100$ 인 경우인 $601$ , $1201$ , $1801$ 이 소수인지 WolframAlpha에 검색해봤는데 (검색창에 N is prime? 이라고 치면 N이 소수인지 아닌지 알려줍니다.)
601 is Prime? / 1201 is Prime? / 1801 is Prime?
한번에 그냥 모두 소수로 나와서 당황했습니다.
$6m + 1 > 500$ 일 때 $6m + 1$ , $12m + 1$ , $18m + 1$ 이 모두 소수인지 일일히 소수판별법으로 판단해야하나 싶었는데 다행히도 그럴 일이 없었고, 다음과 같은 코드로 13319번을 통과했습니다.

print(601*1201*1801, 601)

view raw BOJ13319.py hosted with ❤ by GitHub

1299963601 601

view raw BOJ13319.txt hosted with ❤ by GitHub

가장 짧은 정답은 "9자리수" "3자리수" 인 듯 한데, 한번 이 수를 찾아보시는 재미도 있을 듯 합니다.

N번째 푼 문제 (2022/XX/XX)