https://arca.live/b/math/40190858?p=1

라면가이더... 아니 가면라이더 빌드의 한 에피소드. 어째선지 에피소드 번호가 수식으로 쓰여 있다. 몇 화인지 알고 싶으면 위 화면의 문제를 풀면 된다.

[Q. 어떤 자연수 n에 대해 (2^n + 1)/(n^2) 은 자연수이다. 이 때 가능한 n의 값을 모두 구하시오.(단, n>1)]

...뭐야 왜 어려워요?

사실 이 문제의 정체는 90년도 국제수학올림피아드 3번 문제로, 만점률 약 5%정도인 고난도 문제였다. 전세계의 고등학생들을 괴롭힌 이 문제의 답을 알아보자. (해설 원본: https://su-hai.hatenablog.com/entry/11560740 )

우선 분자인 2^n + 1 은 홀수이기 때문에 분모도 홀수여야 하며, 따라서 n 역시 홀수이다.

이 때 n의 가장 작은 소인수를 p라고 하자. n이 홀수이므로 p≥3이며, (2^n + 1)/(n^2) 이 자연수이니 2^n ≡ -1 (mod p)라고 할 수 있다.

즉 4^n ≡ 1 (mod p).

또한 페르마의 소정리(소수 p에 대해 a가 p의 배수가 아니면 a^(p-1)≡1 (mod p)가 성립함) 에 따라 4^(p-1) ≡ 1 (mod p) 이다.

따라서 n과 p-1의 공약수 z에 대해 4^z ≡ 1 (mod p)인데, p는 n의 최소 소인수임을 가정했으므로 gcd(n, p-1)=z=1이다. 그렇다면 4 ≡ 1 (mod p)이므로 p=3임을 알 수 있다. 즉, n은 3의 배수가 된다.

이 때 LTE 보조정리가 등장한다.(스마트폰 아님 ㅎ)

0이 아닌 정수 n과 소수 p에 대해 음이 아닌 정수 d가 존재하여 n이 p^d의 배수이지만 p^(d+1)의 배수는 아닐 때 d=v(p, n)으로 나타내면

v(p, x^n - y^n) = v(p, x-y) + v(p, n)이 성립한다는 내용의 정리이다.

위의 식에 p=3, x=2, y=-1을 대입하면 v(3, 2^n + 1) = v(3, n) + 1 로 간단하게 줄어든다.

또한 v의 정의에 따라 v(3, n^2) = 2 v(3, n) 이다.

여기서 처음의 식으로 돌아가면 (2^n + 1)/(n^2) 이 자연수이므로 v(3, 2^n + 1) ≥ v(3, n^2) 이고, 위에서 유도한 식을 대입하면 v(3, n) + 1 ≥ 2 v (3, n). 이항하면 1 ≥ v(3, n).

그런데 n은 3의 배수이므로 v(3, n) = 1이 된다.

우선 n=3을 테스트해보면  (2^n + 1)/(n^2) = (2^3 + 1)/(3^2) = 9/9 = 1 이 되므로 식이 성립한다. 그렇다면 n>3으로 가정하고, n의 두 번째로 작은 소인수 q에 대해 위와 같은 방식으로 풀어보자.(p=3이므로 q≥5)

4^n ≡ 1 (mod q), 4^(q-1) ≡ 1 (mod q). 따라서 n과 q-1의 공약수 z에 대해 4^z ≡ 1 (mod q)를 만족하는데, q는 n의 두 번째로 작은 소인수이므로 gcd(n, q-1)은 3보다 클 수 없고 따라서 gcd(n, q-1) = 1 또는 3이다.

그런데 z=1로 가정하면 4^z ≡ 1 (mod q)에서 q=3이 되므로 모순. 따라서 z=3이고 4^3 ≡ 1 (mod q)를 만족하는 q를 찾으면 되는데 이러한 q는 7뿐이다.(64 ≡ 1 (mod 3 or 7), 그러나 q>3이므로 q=3은 불가)

그러나 위에서 n이 3의 배수라고 하였으므로 n=3k로 나타내면  mod 7에서 2^n + 1 ≡ 2^(3k) + 1  ≡  8^k + 1  ≡  1^k + 1  ≡  2 (mod 7)이 되고, n이 7의 배수라면 n^2는 7의 배수임이 자명하므로 (2^n + 1)/(n^2)∈N 을 만족시킬 수 없다.

따라서 n>3 가정은 잘못되었고,  v(3, n) = 1 이라고 하였으므로 이를 만족시키는 n은 3 뿐이며 따라서 위 가면라이더 에피소드는 제 3화임을 알 수 있다.