95%는 못푼다는 과일 문제 해설

들어가기에 앞서) 이거 나는 하고 싶지 않았어. 하지만 누군가가 궤령부에 이 문제를 올려버렸더군. 당신들의 호기심이 이 거대한 판도라의 상자를 열어버린거야.

먼저 사과를 a, 바나나를 b, 파인애플을 c라고 치환하고, 양변에 (a+b)(a+c)(b+c)를 곱하면

a(a+b)(a+c) + b(a+b)(b+c) + c(a+c)(b+c) = 4(a+b)(a+c)(b+c)가 됩니다. 이를 잘 쪼물락(?)대면

a^3+b^3+c^3 - 3(a^2b+ab^2+a^2c+ac^2+b^2c+bc^2) - 5abc = 0 이라는 식이 됩니다. (이 식을 식 (1)이라고 합시다.)

이 식을 만족하는 a,b,c가 모두 자연수인 해를 찾아야 합니다.

이 식에 대한 몇 가지 관찰을 해보면

1. 총 3개의 변수가 있다.
2. 모든 항들의 차수가 같으며, 그 차수는 3이다. (이를 동차다항식이라 부른다.)
3. 만약 a에 1, b에 -1, c에 0을 대입하면 식을 만족한다. (물론 a,b,c 모두 자연수인 값을 찾는 것이므로, 이 값은 답이 될 수 없다.)

여기까지 본 대수기하학자 + 타원곡선학자들은 바로 이런 생각을 합니다.

이 방정식으로 정의된 공간은 뭐지? 변수가 3개지만 동차다항식(Homogeneous Polynomial)으로 전체 공간은 2차원 사영공간(Projective Space)이면 충분하겠지? 즉 방정식 하나로 정의되어있으니, 이 방정식이 정의하는 공간은 1차원이겠군! 어랍쇼, 거기에 차수는 3이잖아? 이러면 종수(genus, 차돌짬뽕 아님)는 종수-차수 정리에 따라 1이 되는데. 게다가 이를 만족하는 유리수 해 (1,-1,0)도 있잖아?! 그럼 이건 더도 볼 것도 없이 타원곡선이다!

네 맞습니다. 우린 타원곡선에 당도하게 됩니다. (제 전공분야입니다 예에에에~!!)

모든 타원 곡선은 y^2 = x^3 + Ax^2 + Bx + C 라는 꼴(바이어스트라스 형식)로 표현이 가능합니다.

위의 식에서도 a, b, c를 도 x, y로 적절히 치환하면 이렇게 변환이 가능한데, 그 방식이란

a = (56-x+y)/(56-14x), b = (56-x-y)/(56-14x), c = (-28-6x)/(28-7x) 입니다. (이를 식 (2)이라고 합시다.)

저가요… 어떻게 했냐면요, 수학자들은 컴퓨터를 이용했답니다. MAGMA나 SAGE가 이런 연산은 끝내주게 잘합니다. (근데 저는 코딩알못이라 여기서 이미 나가리입니다.)

그렇게 치환하면 y^2 = x^3 + 109x^2 + 224x 라는 타원곡선이 나옵니다. 이 타원곡선을 편의상 E라고 할게요.

자 그렇다면 이 타원곡선 E의 유리수해 (x,y)를 찾기 시작하면 됩니다. 왜냐?! 그 유리수해 x,y를 위의 식 (2)에 대입하면 a, b, c 값을 구할 수 있습니다.

이렇게 구한 a, b, c 역시 유리수입니다. 왜냐하면 유리수의 합, 차, 곱, 비는 여전히 유리수이기 때문입니다.

원래 주어진 식은 동차다항식이었죠? 만악 (a,b,c)가 어느 동차다항식의 해가 된다면, d가 어떤 자연수든간에 (da, db, dc)역시 이 동차다항식의 해가 됩니다. 각 항의 차수가 모두 3차로 일치하기 때문에, a,b,c 각각에 d가 곱해지는 것은, 전체 식에 d^3을 곱하는 것과 진배없기 때문입니다.

식 (1)에 (da, db, dc)를 대입하면 

(da)^3+(db)^3+(dc)^3 - 3((da)^2(db)+(da)(db)^2+(da)^2(dc)+(da)(dc)^2+(db)^2(dc)+(db)(dc)^2) - 5(da)(db)(dc) = 0 가 되는데

모든 항들이 d^3을 포함하고 있기 때문에 양변에 d^3을 나눔으로서 다시 원래 식 (1)을 얻을 수 있습니다.

즉, (a,b,c)가 유리수해더라도 문제가 없습니다. 그 분모의 최소공배수 d를 모두 곱해버림으로서 정수해 (da,db,dc)를 구할 수 있습니다.

그러므로 남은 문제는 유리수해 (a,b,c)를 찾되, a,b,c가 모두 양수인 해를 찾는 방법이군요.

그런데 타원곡선의 유리수해는 굉장히 특이한 성질을 갖고 있습니다. 무엇이냐?!

바로 유리수해끼리 연산을 취해줄 수 있다는 뜻입니다. 유리수해끼리의 덧셈을 정의할 수 있는데, 이러면 또다른 새로운 유리수해가 나옵니다.

좀 더 쉬운 비유를 들자면, 자연수 1과 덧셈을 이용하면 1+1, 1+1+1과 같이 새로운 자연수 2와 3을 생성해낼 수 있는 것처럼

타원곡선의 유리수해 역시 덧셈으로 표기하지만 실제로는 더하기가 아닌 특별한 연산을 취해 새로운 유리수해들을 생성해낼 수 있습니다. 

즉 유리수해를 하나만이라도 발견한다면, 그 것을 P로 둔다면, P+P, P+P+P, … 를 해줌으로서 더 많은 유리수해들을 찾아낼 수 있습니다.

이렇게 P를 n번 ‘더한’ 것을 nP라고 표기하곤 합니다.

(조금 어려운 내용이지만, 대개 타원곡선 E의 유리수해들의 구조를 E(Q)로 표기하는데, Mordell-Weil theorem에 의해 E(Q) 는 finitely generated abelian group입니다. 만약 위에서 찾은 P가 꼬임부(torsion part)에 해당하는 원소라면, P를 더하다가 원하는 해도 찾지 못한채 항등원에 도달하는 참사가 벌어집니다. 하지만, Mazur's theorem에 의해 E(Q)의 꼬임부가 가질 수 있는 형태가 총 15개밖에 없음을 증명했습니다. 이를 기반으로 임의의 유리수해 P가 있을 때 2P, 3P, …, 12P까지 E(Q)의 identity element가 아니라면, 이 P는 free part가 non-trivial 하다고 보셔도 좋고, 얼마든지 스스로 더해 무한히 많은 유리수해를 생성해낼 수 있습니다.)

유리수해 찾기 알고리즘을 적용한 결과 x = -100, y = 240이라는 E의 해를 찾을 수 있었습니다. 이를 P라고 두고

앞서 말했던 것 처럼, 2P, 3P, …를 계산하기 시작합니다. 방식은 이렇습니다.

P의 x, y값을 식 (2)에 넣었을 때 나오는 a,b,c가 모두 양수인가? 아니라면, 2P를 구한다.

2P의 x, y값을 식 (2)에 넣었을 때 나오는 a,b,c가 모두 양수인가? 아니라면, 3P를 구한다.

이를 반복해본 결과 정말 감사하게도!! 9P만에 a,b,c가 모두 양수인 해가 나왔습니다.

9P의 x값은 -66202368404229585264842409883878874707453676645038225/13514400292716288512070907945002943352692578000406921

y값은 58800835157308083307376751727347181330085672850296730351871748713307988700611210/1571068668597978434556364707291896268838086945430031322196754390420280407346469

이를 식 (2)에 대입한 뒤, 분모부의 최소공배수를 곱해주면 우리가 원하던 값이 나옵니다. 그 값이 바로

a=154476802108746166441951315019919837485664325669565431700026634898253202035277999,  
b=36875131794129999827197811565225474825492979968971970996283137471637224634055579,  
c=4373612677928697257861252602371390152816537558161613618621437993378423467772036 

이죠.

물론 이 값이 가장 작은 해라는 것을 증명하는 건 또 다른 영역의 문제입니다. 저한테 물어봐도 몰라요.

어쨌든 굉장히 심오한 현대수학이 필요하고, 그 해답을 구하는 과정은 괴상망측하게 어렵다는 것으로 글을 마무리하겠습니다.