Cho a và b là hai số nguyên tố cùng nhau. Chứng tỏ rằng các số sau cùng nguyên tố cùng nhau

Để chứng minh rằng 3a + 4b và 4a + 5b cũng là hai số nguyên tố cùng nhau, ta sẽ sử dụng định lý Euclid.

Giả sử (3a + 4b) và (4a + 5b) không nguyên tố cùng nhau. Điều này có nghĩa là chúng có một ước chung lớn hơn 1.

Gọi d là ước chung lớn nhất của (3a + 4b) và (4a + 5b). Khi đó, d cũng là ước chung của (3a + 4b) - 3(4a + 5b) = -7b và (4a + 5b) - 4(3a + 4b) = b.

Vì a và b là hai số nguyên tố cùng nhau, nên không có ước chung nào khác 1 ngoài 1. Do đó, d không thể chia hết cho b. Tuy nhiên, d chia hết cho b, vì vậy d phải chia hết cho b và không chia hết cho b. Điều này là mâu thuẫn, vì vậy giả định ban đầu là sai.

Vì vậy, 3a + 4b và 4a + 5b là hai số nguyên tố cùng nhau.