youproof.orgDeep Math. Human Access.

23.8. Tétel

Miller-Rabin-szorzat

Legyenek adottak valamilyen tetszőleges e≥1e\geq 1 és k≥1k\geq 1 egész számok. Ekkor bármilyen aa egész szám esetén teljesül az alábbi összefüggés:

a2e⋅k−1=(ak−1)⋅(ak+1)⋅(a2k+1)⋅(a4k+1)⋅…⋅(a2e−1k+1)a^{2^e\cdot k}-1 = (a^k-1)\cdot (a^k+1)\cdot (a^{2k}+1)\cdot (a^{4k}+1)\cdot \ldots \cdot (a^{2^{e-1}k}+1)

♣