Để chứng minh rằng hai số \(5n + 3\) và \(7n + 8\) là hai số nguyên tố cùng nhau, ta có thể sử dụng Định lý Euclid về ước số chung lớn nhất (GCD).

GCD (ước số chung lớn nhất) của hai số là số lớn nhất mà chia cả hai số đó mà không để lại số dư.

Ta giả sử \(d\) là GCD của \(5n + 3\) và \(7n + 8\).

\(d\) chia hết cho cả \(5n + 3\) và \(7n + 8\), điều này có nghĩa là \(d\) cũng chia hết cho \(7n + 8\) trừ đi \(7n + 8 - (5n + 3) = 2n + 5\).

Từ \(d\) chia hết cho \(5n + 3\) và \(2n + 5\), ta thấy rằng \(d\) cũng chia hết cho \(2n + 5\) trừ đi \(2n + 5 - 2(5n + 3) = -1\).

Do đó, GCD của \(5n + 3\) và \(7n + 8\) chính là GCD của \(2n + 5\) và \(-1\). Nhưng GCD của một số và -1 luôn là 1, do đó hai số \(5n + 3\) và \(7n + 8\) là số nguyên tố cùng nhau.