Cho $n>1$ là một số nguyên lẻ, ta viết $n=2^{s}d+1$ trong đó $s\ge 1$ và $d$ là số nguyên dương lẻ. Với mỗi số nguyên $a$ thỏa mãn $\gcd (a,n)=1$, ta nói $a$ có liên hệ với $n$ nếu $a^d\equiv 1(\mathrm{mod}n)$ hoặc trong dãy $a^d,a^{2d},a^{4d},\dots ,a^{2^{s-1}d}$ có đúng một số hạng đồng dư với $-1$ theo modulo $n$. Chứng minh rằng $n$ là số nguyên tố khi và chỉ khi với mọi số nguyên $a$ thỏa mãn $\gcd (a,n)=1$ đều có liên hệ với $n$.

Trước hết, giả sử $n$ là số nguyên tố. Theo định lý Fermat nhỏ, ta có
$$a^{2^{s}d}=a^{n-1}\equiv 1(\mathrm{mod}n).$$
Nếu $a^d\equiv 1(\mathrm{mod}n)$ thì xong, còn nếu không, gọi $t$ là số nhỏ nhất trong $\{1,2,\dots ,s\}$ sao cho $a^{2^{t}d}\equiv 1(\mathrm{mod}n)$. Khi đó $a^{2^{t-1}d}\equiv -1(\mathrm{mod}n)$ là số duy nhất thoả mãn do $n\in \mathbb{P}$, do đó $a$ có liên hệ với $n$.
Ngược lại, giả sử $n$ là hợp số. Ta sẽ chứng minh tồn tại $a$ không liên hệ với $n$.
Nếu $n$ có ít nhất hai ước nguyên tố phân biệt, viết $n=p^{\alpha }m$, trong đó $p\nmid m$ và $m>1$.
Theo CRT, tồn tại số nguyên dương $a$ sao cho
$$a\equiv 1(\mathrm{mod}{p}^{\alpha }),a\equiv -1(\mathrm{mod}m).$$
Khi đó $\gcd (a,n)=1$. Vì $d$ lẻ, $a^d\equiv -1(\mathrm{mod}m)$, nên $a^d\not\equiv 1(\mathrm{mod}n)$. Mặt khác, mọi số $a^{2^{j}d}$ đều đồng dư với $1$ modulo $p^{\alpha }$, nên không số nào trong chúng có thể đồng dư với $-1$ modulo $n$.
Vậy $a$ không có liên hệ với $n$.
Nếu $n=p^{\alpha }$ với $p$ là số nguyên tố lẻ và $\alpha \ge 2$. Chọn $a=1+p^{\alpha -1}$.
Ta có $p\nmid d$ vì $d$ là ước của $n-1$. Với mọi $j\ge 0$, khai triển nhị thức cho
$$a^{2^{j}d}\equiv 1+2^{j}d{p}^{\alpha -1}(\mathrm{mod}{p}^{\alpha }).$$
Vế phải không đồng dư với $1$ modulo $p^{\alpha }$, đồng thời lại đồng dư với $1$ modulo $p$, nên cũng không thể đồng dư với $-1$ modulo $p^{\alpha }$. Do đó $a$ không có liên hệ với $n$.
Trong các trường hợp, $n$ là hợp số thì điều kiện của đề bài không thể đúng nên có điều phải chứng minh.