小さい数で $p - 1$ 法を考えると少し仕組みがわかりやすい。

$p - 1$ 法において $n$ の約数を見つけるとき、境界値 $b\in \mathbb{N}$ を動かし $k = \textrm{lcm}(1, 2, \cdots, b)$ として

$$\gcd(a^k - 1,\ n)$$

を計算する。ここで $b$ （すなわち $k$）が大きいとうまくいかない。

例 1

2 つの素因数をもつ $n = 15$ について考える。$a = 2,\ b = 4$ のとき $k = \textrm{lcm}(1, 2, 3, 4) = 12$ であり

$$\gcd(2^{12} - 1,\ 15) = 15$$

となってしまい、非自明な約数を得ることができない。$15 = 3 \times 5$ であり、$3 - 1 \mid 12,\ 5 - 1 \mid 12$ より

$$2^{12} \equiv 1 \pmod{3},\ 2^{12} \equiv 1 \pmod{5}$$

が成り立つ（フェルマーの小定理）。よって

$$2^{12} \equiv 1 \pmod{15}$$

となってしまい、$\gcd(2^{12} - 1, 15) = 15$ となる。

そこで $b = 2$ とすると $k = \textrm{lcm}(1,\ 2) = 2$ であり、$3 - 1 \mid 2,\ 5 - 1 \nmid 2$ となる。よって

$$2^{2} \equiv 1 \pmod{3},\ 2^{2} \not \equiv 1 \pmod{5}$$

だから

$$\gcd(2^{2} - 1,\ 15) = 3$$

となり、非自明な約数を得ることができる。

例 2

次に 3 つの素因数をもつ $n = 105 = 3 \times 5 \times 7$ について考える。$k = \textrm{lcm}(1, 2, 3, 4) = 12$ のとき $k$ が大きすぎるためうまくいかない。例 1 と同様に $3 - 1,\ 5 - 1,\ 7 - 1$ のいずれも $12$ を割ってしまうからだ。そこで $k$ を小さくとると

$$\gcd(2^2 - 1,\ 105) = 3,\\ \gcd(2^4 - 1,\ 105) = 15$$

となりうまくいく（2 行目は $p - 1$ 法を適用した結果は必ずしも素数になるとは限らない例）。