Bài 6: Chứng minh rằng với mọi số tự nhiên n thi các số sau nguyên tố cùng nhau: a) 7n+10 và 5n+7 b) 2n +1 và 6n+5 c) 2n+3 và 4n +8

a) Để chứng minh rằng hai số 7n + 10 và 5n + 7 là nguyên tố cùng nhau với mọi số tự nhiên n, ta có thể sử dụng thuật toán Euclid để tìm Ơclit của chúng.

Ta xét Ơclit của hai số này:

euclid(7n + 10, 5n + 7) = euclid(7n + 10 - (5n + 7), 5n + 7)
= euclid(2n + 3, 5n + 7)

Tiếp tục thực hiện thuật toán Euclid:

euclid(2n + 3, 5n + 7) = euclid(2n + 3, 5n + 7 - 2(2n + 3))
= euclid(2n + 3, n + 1)

Lặp lại để tìm Ơclit giữa n + 1 và 2n + 3:

euclid(n + 1, 2n + 3) = euclid(n + 1, 2n + 3 - 2(n + 1))
= euclid(n + 1, 1)

Và cuối cùng:

euclid(n + 1, 1) = 1

Do đó, hàm số nguyên tố cùng nhau của 7n + 10 và 5n + 7 là 1 với mọi số tự nhiên n.

b) Tương tự như vậy, ta cần chứng minh rằng 2n + 1 và 6n + 5 là nguyên tố cùng nhau.

Thực hiện:

euclid(2n + 1, 6n + 5) = euclid(2n + 1, 6n + 5 - 3(2n + 1))
= euclid(2n + 1, 2)

Khi n là một số tự nhiên, ta có:

- Nếu n là chẵn (n = 2k): 2n + 1 = 2(2k) + 1 = 4k + 1, tức là số lẻ.
- Nếu n là lẻ (n = 2k + 1): 2n + 1 = 2(2k + 1) + 1 = 4k + 3, tức là số lẻ.

Vì vậy, 2n + 1 luôn lẻ và Ơclit(2n + 1, 2) là 1.

Do đó, 2n + 1 và 6n + 5 là nguyên tố cùng nhau với mọi số tự nhiên n.

c) Cuối cùng, để chứng minh 2n + 3 và 4n + 8 là nguyên tố cùng nhau:

Ta có:

euclid(2n + 3, 4n + 8) = euclid(2n + 3, 4n + 8 - 2(2n + 3))
= euclid(2n + 3, 2)

Như đã phân tích ở trên, khi n là số tự nhiên, số 2n + 3 sẽ:

- Nếu n là chẵn: 2n + 3 sẽ là số lẻ.
- Nếu n là lẻ: 2n + 3 vẫn là số lẻ.

Như vậy, 2n + 3 luôn là số lẻ và Ơclit(2n + 3, 2) là 1.

Do đó, 2n + 3 và 4n + 8 là nguyên tố cùng nhau với mọi số tự nhiên n.