Bài toán: “Những số nguyên tố khi chia cho 4 dư 1 thì luôn biểu diễn được dưới dạng tổng của 2 số chính phương”. Kiểm tra N có nguyên tố hay không? Nếu N nguyên tố, kiểm tra xem có thể phân tích N thành tổng của hai số chính phương a và b hay không? Nếu được hãy tìm a và b.
Để kiểm tra xem một số N có phải là số nguyên tố hay không, bạn có thể sử dụng các thuật toán kiểm tra số nguyên tố như sàng Eratosthenes hoặc kiểm tra liệu N có chia hết cho các số nguyên tố nhỏ hơn nó không.
Nếu N được xác định là một số nguyên tố, chúng ta có thể kiểm tra xem liệu N có thể phân tích thành tổng của hai số chính phương a và b không. Để làm điều này, chúng ta có thể thực hiện các bước sau đây:
- Kiểm tra các số chính phương nhỏ hơn hoặc bằng N để xác định các số chính phương có thể là a và b. Số chính phương là số mà căn bậc hai của nó là một số nguyên. Ví dụ: 1, 4, 9, 16, …
- Với mỗi số chính phương a, kiểm tra xem N – a có phải là số chính phương hay không. Nếu là số chính phương, ta đã tìm được hai số chính phương a và b sao cho N = a + b.
Dưới đây là một đoạn mã Python minh họa để kiểm tra điều này:
import math
def is_prime(n):
if n <= 1:
return False
for i in range(2, int(math.sqrt(n)) + 1):
if n % i == 0:
return False
return True
def find_square_sums(n):
if not is_prime(n):
return "N không phải là số nguyên tố."
for a in range(1, int(math.sqrt(n)) + 1):
b = n - a
if math.isqrt(b)**2 == b:
return f"{n} = {a}^2 + {b}^2"
return "Không tìm thấy phân tích của N thành tổng của hai số chính phương."
# Ví dụ sử dụng:
N = 17
print(find_square_sums(N))
Kết quả sẽ là “17 = 1^2 + 16^2”, vì 17 là số nguyên tố và có thể phân tích thành tổng của hai số chính phương là 1 và 16.