페르마의 마지막 정리란?
수론에서 유명한 페르마의 마지막 정리(Fermat's Last Theorem)는 '페르마의 추측'이라고도 불리는 정리로, 거듭제곱 n이 2보다 클 때 세 자연수 a, b, c가 다음 식을 만족하는 경우가 존재하지 않는다는 내용입니다.
an + bn = cn
즉, n ≤ 2일 때는 위 조건을 만족하는 값들이 존재하지만, n ≥ 3인 경우에는 어떤 자연수 조합으로도 성립하지 않습니다.
n = 2일 때의 예시
- 3, 4, 5 → 32 + 42 = 9 + 16 = 25 = 52
- 5, 12, 13 → 52 + 122 = 25 + 144 = 169 = 132
참고로 두 번째 예시에서 원문에 49라는 값이 언급되었는데, 이는 122 = 144가 올바른 계산 결과입니다.
문제 정의
이 문제에서는 세 개의 값 L, R, pow가 주어집니다. 각각 범위 [L, R]과 거듭제곱 지수를 의미하며, 주어진 범위와 지수에 대해 페르마의 마지막 정리를 검증하는 것이 과제입니다.
예제 1
- 입력: L = 4, R = 12, power = 2
- 출력: 5, 12, 13
예제 2
- 입력: L = 4, R = 12, power = 4
- 출력: 해당하는 값을 찾을 수 없음
해결 접근 방법
해결 로직은 다음과 같습니다.
- 먼저 거듭제곱 n이 2보다 큰지 확인합니다. n ≥ 3이라면 페르마의 마지막 정리에 따라 해가 존재할 수 없으므로 즉시 '값을 찾을 수 없다'는 메시지를 출력합니다.
- n이 2 이하라면, 범위 [L, R] 내의 모든 a, b 조합에 대해 an + bn = cn을 만족하는 값이 있는지 탐색합니다.
C++ 구현 코드
아래는 위 접근 방식을 실제로 구현한 C++ 프로그램입니다.
#include <iostream>
#include <math.h>
using namespace std;
void checkFermatsLastTh(int L, int R, int n) {
if (n >= 3)
cout<<"No example found!";
else {
for (int a = L; a <= R; a++)
for (int b=a; b<=R; b++)
{
int sum = pow(a, n) + pow(b, n);
double c = pow(sum, 1.0/n);
int cpowN = pow((int)c, n);
if (cpowN == sum)
{
cout<<"Example found with value : "<<a<<", "<<b<<", "<<c;
return;
}
}
cout << "No example found!";
}
}
int main() {
int L = 3, R = 15, power = 2;
cout<<"Run 1 \n";
checkFermatsLastTh(L, R, power);
L = 5, R = 42; power = 5;
cout<<"\n\nRun 2\n";
checkFermatsLastTh(L, R, power);
return 0;
}실행 결과
Run 1 Example found with value : 3, 4, 5 Run 2 No example found!
코드 설명 및 핵심 포인트
첫 번째 실행(Run 1)에서는 범위 [3, 15]와 지수 2가 주어졌기 때문에, 피타고라스 정리를 만족하는 (3, 4, 5) 조합을 찾아 출력합니다. 반면 두 번째 실행(Run 2)에서는 지수가 5로 3 이상이므로, 페르마의 마지막 정리에 의해 해가 존재하지 않는다는 메시지가 출력됩니다.
코드의 핵심은 pow(sum, 1.0/n)을 통해 sum의 n제곱근을 계산하고, 그 값을 정수로 변환한 뒤 다시 n제곱하여 원래의 sum과 일치하는지 확인하는 방식입니다. 이를 통해 c가 정확히 정수인지 판별할 수 있습니다.
흥미롭게도 페르마는 1637년 책 여백에 이 정리를 적어두면서 '이에 대한 놀라운 증명을 발견했지만, 여백이 좁아 적을 수 없다'라고 남겼습니다. 이후 무려 358년이 지난 1995년에야 앤드루 와일스(Andrew Wiles)가 최종 증명에 성공했습니다.