20/09/06 23:43:53.20 HYDaJwjZ.net
(3^q +1)/q = m の素因数の１つをpとする。
3^{pq} + 1 = (qm-1)^p + 1
= -Σ[j=1,p] C(p,j) (-qm)^j
≡ (qm)^p (mod pqm) (*)
≡ 0 (mod pqm) (p|m)
よって
(3^{pq} + 1)/(pq) も mの倍数。
*) pが素数で 1≦j<p のとき C(p,j) はpの倍数。
例 (q,p) = (2,5) (5050, 5) (5050,101) (11810,5)