ทฤษฎีบทเฟอร์ม่าสุดท้าย (Fermat's Last Theorem) ใน C++

ทฤษฎีบทเฟอร์ม่าสุดท้าย

สำหรับจำนวนเต็ม n > 2 ไม่มีจำนวนเต็มบวก a, b, c ที่ทำให้ a^n + b^n = c^n

สำหรับ n = 2 มีคำตอบมากมาย (Pythagorean Triples) เช่น 3,4,5

โจทย์

ได้รับช่วง [L, R] และกำลัง power ตรวจสอบว่ามีคำตอบในช่วงนั้นหรือไม่

ตัวอย่าง

• L=4, R=12, power=2 -> พบ 5,12,13
• L=4, R=12, power=4 -> ไม่พบ

แนวทางแก้ปัญหา

ถ้า power ≥ 3 -> ไม่มีคำตอบ (ตามทฤษฎีบท)

ถ้า power = 2 -> ค้นหา a,b ในช่วง ตรวจสอบว่า sqrt(a^2+b^2) เป็นจำนวนเต็มและอยู่ในช่วง

โปรแกรมตัวอย่าง

#include <iostream>
#include <cmath>
using namespace std;

void checkFermatsLastTh(int L, int R, int n) {
    if (n >= 3) { cout << "No example found!"; return; }
    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 << ", " << (int)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!