제곱의 차가 큰 수를 쪼갠다

모눈종이 한 장과 가위를 손에 쥐어 봅니다. 가로와 세로가 각각 10칸인 커다란 정사각형을 그리면, 칸의 개수는 모두 개입니다.

이제 오른쪽 맨 위 모서리에서 가로 1칸, 세로 1칸짜리 작은 정사각형 하나를 가위로 오려 냅니다. 오려 낸 조각은 개이므로, 남아 있는 모눈의 칸수는 개가 됩니다.

이 99개의 칸을 반듯한 직사각형 하나로 다시 만들 수 있을까요? 방금 1칸이 떨어져 나가 세로로 9칸만 남은 오른쪽 가장자리 한 줄(가로 1칸 × 세로 9칸)을 가위로 반듯하게 잘라 냅니다. 그러면 왼쪽에 남은 덩어리는 가로 9칸 × 세로 10칸이 됩니다. 잘라 낸 조각을 옆으로 눕히면 가로 9칸 × 세로 1칸이 되는데, 이것을 왼쪽에 남은 덩어리의 아래쪽에 나란히 이어 붙입니다.

원래 정사각형과 비교하면 가로는 1만큼 줄어 9칸이 되었고, 세로는 아래쪽에 1칸 두께의 줄이 더해져 11칸이 되었습니다. 곧 가로는 1만큼 줄고, 세로는 1만큼 늘어난 것입니다. 손으로 종이 조각을 옮겨 붙였을 뿐인데, 구멍 뚫린 사각형이 가로 9칸, 세로 11칸인 반듯한 직사각형으로 변신했습니다. 99칸짜리 종이가 정확히 직사각형이 된 것입니다.

모퉁이에서 2칸짜리를 오려 내면 어떻게 될까요? 오른쪽 맨 위 모서리에서 가로 2칸, 세로 2칸짜리 정사각형을 오려 내면 빠진 칸수는 개이고, 남은 칸수는 개입니다. 이번에는 비어 있는 오른쪽 맨 끝 2줄(가로 2칸 × 세로 8칸)을 잘라 눕힌 뒤(가로 8칸 × 세로 2칸) 아래쪽에 붙여 봅니다. 가로는 2만큼 줄어 8칸이 되고, 세로는 2만큼 늘어나 12칸이 됩니다. 이번에도 남은 96개의 칸이 가로 8칸, 세로 12칸인 직사각형으로 딱 들어맞습니다.

더 큰 종이로 해 보아도 원리는 똑같습니다. 한 변이 100칸인 큰 정사각형(10,000칸)에서 한 변이 3칸인 정사각형(9칸)을 오려 내면 9,991칸이 남고, 이것도 가로는 3이 줄고 세로는 3이 늘어난 직사각형으로 다시 붙습니다.

큰 정사각형에서 작은 정사각형을 빼내고 남은 모눈 조각은, 항상 두 변의 길이가 다른 직사각형으로 다시 붙일 수 있습니다. 이것을 수식으로 적으면 가 됩니다.

모눈종이를 자르고 붙이며 확인한 규칙을 수학에서는 문자로 적습니다. 중학교에 올라오면 두 식의 곱을 전개하는 곱셈공식을 배웁니다.

이 식을 왼쪽에서 오른쪽으로 읽으면 두 괄호를 곱해 괄호를 푸는 전개이지만, 거꾸로 오른쪽에서 왼쪽으로 읽으면 놀라운 일이 일어납니다.

빼기로 이어진 두 제곱수를 두 식의 곱으로 묶어 내는 것, 이것이 바로 중학교 3학년에서 배우는 인수분해입니다. 어떤 수가 두 제곱수의 차이로 표현되기만 하면, 복잡한 나눗셈을 하지 않아도 곧바로 두 수의 곱으로 갈라집니다.

예를 들어 91이라는 수가 소수인지 아니면 합성수인지 알고 싶다고 해 봅시다. 91보다 살짝 큰 제곱수를 떠올려 봅니다. 10의 제곱은 100입니다. 100에서 91을 빼면 9가 나오는데, 9는 마침 3의 제곱입니다.

제곱의 차가 완성되었으니 곱셈공식을 거꾸로 적용하기만 하면 끝납니다.

91이 소수가 아니라 7과 13의 곱이라는 사실이 순식간에 드러납니다.

143도 마찬가지입니다. 143 바로 위의 제곱수는 144()이고, ()입니다.

조금 더 큰 수인 221은 어떨까요? 221보다 큰 제곱수인 225()를 골라 빼 보면 이 됩니다.

어떤 홀수를 둘로 쪼개고 싶을 때, 그 수보다 큰 제곱수들을 하나씩 떠올려 보며 뺀 결과가 제곱수가 되는 짝을 찾기만 하면, 인수분해 공식이 단숨에 그 수를 쪼개 줍니다.

페르마는 이 생각을 큰 수에 쓰는 방법으로 편지에 적어 보냈다고 전해집니다.

어떤 홀수 을 쪼갤 때, 출발점은 의 제곱근보다 크거나 같은 정수 입니다. 를 이 값부터 하나씩 올려 가며 이 정수의 제곱 이 될 때까지 계산합니다. 제곱수가 나오는 순간 로 쪼개집니다.

이 방법의 속도는 두 인수 와 ()의 거리에 달렸습니다. , 이므로, 두 인수가 가까울수록 가 작아져 몇 걸음 만에 끝납니다.

3,599처럼 두 인수가 가까우면 단 1걸음에 끝나지만, 3,027처럼 인수가 멀면 451걸음이 걸립니다.

페르마의 편지에 실린 큰 수 은 에서 시작합니다. 를 12번 올려 이 되면 제곱수가 나타납니다.

따라서 , 이며, 두 인수는 , 이 되어 로 갈라집니다.

3부터 홀수로 나누면 가장 작은 소인수 44021까지 22,010번 나누어야 하지만, 페르마의 방법은 단 12걸음 만에 해답을 찾아냅니다.

현대 암호학의 핵심인 RSA 암호는 거대한 두 소수 와 를 곱한 합성수를 공개키로 사용합니다. 곱하는 일은 눈 깜짝할 사이에 끝나지만, 거대한 합성수를 다시 두 소수로 쪼개는 일은 오늘의 컴퓨터로도 현실적인 시간 안에 해낼 수 없기 때문입니다. 제4장에서 다루듯 곱하기는 쉽고 나누기는 어렵다는 비대칭성이 암호의 자물쇠가 됩니다.

그러나 만약 암호를 만들 때 고른 두 소수 와 가 서로 너무 가까운 수라면 치명적인 구멍이 생깁니다. 페르마의 인수분해법은 두 소수가 가까울수록 압도적으로 빠르게 작동하기 때문에, 보통의 컴퓨터로도 순식간에 두 소수를 알아낼 수 있습니다. 그래서 현대 암호 시스템에서는 두 소수가 충분히 멀리 떨어지게 무작위로 고르는 것이 보통입니다.

나아가 현대의 정수론 학자들이 거대한 수를 인수분해하기 위해 만든 최신 알고리즘들도 페르마의 생각을 바탕으로 합니다. 두 제곱수의 차이가 의 배수가 되도록 짝을 맞춰 나가는 이차 체법과 수체 체법이 모두 같은 생각에서 이어진 후손입니다.