合同式の応用の中でも特に重要なものとして、与えられた整数が素数であるかどうかを判定する問題がある。
もちろん、素数・合成数は整除性に基いて定義されているのだから、合同式と関連があるのは当然であるが、そのような自明なことを超えて、より深い応用が存在する。
フェルマーの小定理によれば p が素数で a が p の倍数ではない整数ならば
a^{p-1}\equiv 1\pmod{p} である。しかし、以前に述べたように、これだけで与えられた整数 N が素数であるかどうかを判定することはできない。というのは
2^{340}\equiv 1\pmod{341} のように N が合成数でも a^{N-1}\equiv 1\pmod{N} となる場合があるからである。
さらに厄介なことに、 \gcd(a, N)=1 となる任意の a に対し a^{N-1}\equiv 1\pmod{N} となる合成数 N （カーマイケル数）が存在することも
先に述べた通りである。
一方、ウィルソンの定理は N が素数であることの必要十分条件を与えているが、階乗を計算するための計算量が非常に大きいため、実用的ではない。
しかし、フェルマーの小定理の変形により、特殊な状況においては N が素数であることを比較的簡単に確認できる場合がある。
合成数を法とする剰余類の構造より a\pmod{N} の位数は \lambda(N) 以下である。ところで \lambda(N)\leq N-1 が必ず成立し、かつ等号は N が素数であるとき、そのときに限り成り立つ。
より単純に、フェルマー・オイラーの定理から、a\pmod{N} の位数は高々 \varphi(N) であるが、やはり
\varphi(N)\leq N-1 が必ず成立し、等号は N が素数であるとき、そのときに限り成り立つ。
したがって \varphi(N)=N-1 は N が素数であるための必要十分条件である。
さらに N が素数であるための必要十分条件は位数 N-1 の剰余類が存在することだということがわかる（必要性は原始根の存在から導かれる）。
位数の法則から次の定理が導かれる。
N が素数であるための必要十分条件は
となる a が存在することである。
この判定法はLucasが発見したもので、合同式に基づく素数判定法の中でも基本的なものである。これを一般化したものがメルセンヌ素数に対するLucas Testである。さて、この判定法は次のように拡張できる。
N が素数であるための必要十分条件は、 N-1 のすべての素因数 q に対して
となる a が存在することである（a は各 q に対して異なっていてもよい）。
証明
N-1=\prod q_i^{r_i} と素因数分解する。各 q_i に対応する a=a(q_i) の位数は N の約数だが N/q の約数ではないので
q_i^{r_i} の倍数でなければならない。ということは \varphi(N) も q_i^{r_i} の倍数でなければならない。これが各 q_i に対して成り立つことから
\varphi(N)=N-1 である。
さらに、特殊な形の数に対しては N-1 の素因数分解を完全に知る必要はない場合がある。最も単純な判定法として、次のものがある。
N=h\cdot 2^n+1 としたときに h<2^n となっているとする。このとき N が素数であるための必要十分条件は
となる a が存在することである（a は各 q に対して異なっていてもよい）。
証明
N が素数で a を原始根とすると原始根の応用例 (1) から上記の式が成り立つから、必要性は成り立つ。
一方 N が合成数であるとするとN の素因数 p<\sqrt{N} がとれる。
ここで a^{(N-1)/2}\equiv -1\pmod{N} ならば p | N | (a^{(N-1)/2}+1) より a^{(N-1)/2}\equiv -1\pmod{p} も成り立たなければなければならない。
すると a^{N-1}\equiv 1\pmod{p} より a\pmod{p} の位数は N-1 の約数でなければならないが (N-1)/2 の約数ではないので
2^n の倍数でなければならないことがわかる。よって p\equiv 1\pmod{2^n} であるが
このとき
となり、矛盾が起きる。
よって a^{(N-1)/2}\equiv -1\pmod{N} のとき N は素数でなければならない。
この判定法はProthが発見したもので、この形の素数に対する単純な判定法を与えている。そのため、現在知られている巨大な素数の多くは h\cdot 2^n+1 の形のものである。
例 N=7\times 2^{120}+1, a=5 に対して
\equiv -1\pmod{7\times 2^{120}+1}
となるので 7\times 2^{120}+1 は素数である。
なお、この数 7\times 2^{120}+1 の素数性は次のように示すこともできる。
\equiv -1\pmod{7\times 2^{120}+1}
より 2\pmod{7\times 2^{120}+1} の位数は 2^{118} に一致する。よって位数の法則より、 7\times 2^{120}+1 の素因数は k\cdot 2^{118}+1 の形でなければならない。ここで 7\times 2^{120}+1 が合成数と仮定すると
となって矛盾するので 7\times 2^{120}+1 は素数である。
+1 の素因数なので F_{117} が素数ではないこともわかる）