[정수론] 두 소수의 상호 거듭 제곱으로 만들 수 있는 모든 소수

종강 후, 시간 버리듯 유튜브에서 영상을 보다가 재밌는 문제를 봤다.

이 링크에서 본 문제였는데, 2016년 도쿄대 이과 2번에서 등장한 문제라고 한다.

문제 답을 알고 보면 참으로 합리적이고 쉬운데 이걸 시험장에서 본 사람이라면 얼마나 심란했을까하는 생각에 새해가 되었지만 나이 먹은 내가 싫지 않았다.

각설하고 문제는 이와 같다.

문제

소수 $p, q$를 이용해 $p^q + q^p$으로 표현할 수 있는 소수를 모두 구하라.

풀이

일단, 2를 제외한 모든 소수는 홀수라는 점을 기억하자.
그리고, 홀수의 거듭제곱은 항상 홀수이고 짝수의 거듭제곱은 0을 제외한 정수에 대해서 짝수이다.

$p,q$가 모두 2인 상황에서 주어진 수식은 2를 만들지 못하므로, $p^q + q^p$가 소수일 때에 그 소수는 홀수이다.

그렇기에 $p, q$ 중 하나는 무조건 2(짝수)이고 나머지는 홀수여야 한다.

그렇다면 하나의 소수를 구해보기 위해서 $p = 2, q = 3$을 넣어본다.
$2^3 + 3^2 = 17$로 소수를 간단하게 찾을 수 있다.

그리고 3 대신 다른 소수를 $q$에 대입한다고 할 때, 우리는 이 소수가 당연히 3의 배수가 아니란 것을 알기에 3으로 나눈 나머지가 1이나 2인 소수로 분류할 수 있고 따라서 $3k+1, 3k+2$를 $q$에 대입할 수 있다.

1) 3으로 나눈 나머지가 1인 소수를 대입

$p^q + q^p = (3-1)^{3k+1} + (3k+1)^2$

$(3-1)^{3k+1}$의 마지막 항을 제외한 모든 항은 $3$의 배수이며, 마지막 항은 $(-1)^{3k+1}$인데, $3k+1$은 우리가 설정한 소수로 홀수이므로 그 값은 $-1$이다.

$(3k+1)^2$ 또한 마지막 항을 제외하고는 모두 3의 배수이고, 마지막 항은 $1^2$이므로 그 값은 $1$이다.

결국 3으로 나눈 나머지가 1인 소수를 대입 시에, 생성된 식의 결과값은 항상 3의 배수이므로 소수를 찾을 수 없다.

2) 3으로 나눈 나머지가 2인 소수를 대입

$p^q + q^p = (3-1)^{3k+2} + (3k+2)^2$

이 식도 1)에서의 풀이와 같이 각 항의 마지막 항을 따져보면 된다.

$(3-1)^{3k+2}$의 마지막 항은 1)과 같은 논리로 $-1$이다.

$(3k+2)^2$의 마지막 항은 $2^2=4$이다.

따라서 이 두 항의 마지막 항의 합은 3으로 3으로 나눈 나머지가 2인 소수를 대입했을 때에대 마찬가지로 식이 생성하는 값은 항상 3의 배수다.

따라서 문제에서 요구하는 '모든 소수를 찾으라'에 대한 답으로 제시할 수 있는 소수는 오직 $17$뿐이다.

답 : 17