프로젝트 오일러 131번

There are some prime values, \(p\), for which there exists a positive integer, \(n\), such that the expression \(n^3 + n^2 p\) is a perfect cube.

For example, when \(p=19, \; 8^3 + 8^2 \times 19 = 12^3\).

What is perhaps most surprising is that for each prime with this property the value of \(n\) is unique, and there are only four such primes below one-hundred.

How many primes below one million have this remarkable property?

---

소수 \(p\) 에 대하여 \(n^3 + n^2 p\) 가 어떤 수의 세제곱이 되는 자연수 \(n\) 이 존재하는 경우가 있다. 예를 들어, \(p=19\) 일 때, \(n=8\) 이면 \(8^3 + 7^2 \times 19=12 ^3\) 이 된다.

놀라운 것은 만약 어떤 소수 \(p\) 에 대하여 위 조건을 만족하는 자연수 \(n\) 이 존재한다면 유일하게 하나 존재한다는 것이다. \(100\) 미만의 소수에 대해서 이런 조건을 만족하는 자연수 \(n\) 이 존재하는 경우는 단 \(4\) 개 뿐이다.

\(10 ^ 6\) 미만의 소수 중 위 조건을 만족하는 자연수 \(n\) 이 존재하는 소수는 몇 개나 될까?

\(n^3 + n^2 p = k^3\) 이라고 해 보자. 좌변을 \(n^2\) 으로 묶어주면

\(n^2 (n + p) = k^3\) 

이렇게 되면 두 가지 중 하나로 생각할 수 있다.

   1. \((n+p)=nm^3\), (\(m\) 은 자연수) \(\to\) 그래야 \(k=nm\) 이 된다.

   2. \(n=a^3\) 이고 \((n+p)= b^3\) (\(a, \;b\) 는 자연수) \(\to\) 그래야 \(k=ab\) 가 된다.

첫 번째 경우는 \( 1 + \dfrac{p}{n} = m^3\) 이 되는데, 우변이 자연수 이므로 좌변도 자연수여야 한다. 따라서 \(\dfrac{p}{n}\) 이 자연수가 되어야 하고, \(n\) 은 \(p\) 의 약수 중 하나여야 한다. 그런데 \(p\) 가 소수이므로 \(n=1\) 또는 \(n=p\) 가 되어야 하는데, \(n=1\) 인 경우는 두 번째 경우에서 \(a=1\) 인 경우로 보면 되니까 일단 패스.. \(n=p\) 이면 \(2 = m^3\) 이 되어 \(m\) 이 자연수라는 조건에 위배된다. 따라서 첫 번째 경우는 그냥 패스~~~

두 번째 경우는 결국 \(a^3 +p = b^3\) 이 되는데, 정리하면

\(\begin{split} p &= b^3 - a^3 \\ &= (b-a) \left ( b^2 +ab+a^2 \right ) \end{split}\)

이 때, \(p\) 가 소수이므로 \(b-a =1 , \; b^2 +ab + a^2 = p\) 이거나 \(b-a = p, \; b^2 +ab + a^2 =1\) 이어야 한다. 그렇지만 \(a, \;b\) 가 모두 자연수 이므로 \(b^2 + ab + a^2\) 은 절대로 \(1\) 이 될 수 없다. 따라서 \(b-a=1, \; b^2 +ab +a^2 =p\) 가 된다.

결과적으로 \(b=a+1,\; p=3a^2 + 3a + 1\) 이 된다.

따라서 \(3a^2 +3a +1 < 10^6\) 을 만족하는 구간에서 자연수 \(a\) 값들을 변화시켜 가며, \(3a^2 + 3a +1\) 이 소수인 경우만 카운트 하면 문제의 답을 쉽게 구할 수 있다