有无穷多伪素数的证明
https://primes.utm.edu/notes/proofs/a_pseudoprimes.htmlLet a > 1 be an integer. Recall that Fermat's (little) theorem shows that if p does not divide a, then ap-1 ≡ 1 (mod p).m is a probable-prime base a (an a-PRP) if am-1 ≡ 1 (mod m)."Most" such numbers m are prime, but if they are not, they are called pseudo-primes base a.The purpose of this note is to prove the following:
Theorem:
Let a be any integer greater than one.There is an infinite number of pseudoprimes with respect to the base a.
Proof: We will follow Ribenboim .
Choose any prime p which does not divide a(a2-1) (this condition can be weakened to p which does not divide a2-1, see ) and then define
m = (a2p-1)/(a2-1).
m is divisible by (ap-1)/(a-1), so m is composite.Also this m is different for each choice of p, so we need only show m is an a-PRP to complete the proof.
Rewrite the expression for m above:
(a2-1)(m-1) = a(ap-1-1)(ap+a).
Clearly the rightmost term is even and a2-1 divides ap-1-1 (as p-1 is even).Also, Fermat's theorem tells us that ap-1-1 is divisible by p, so
2p(a2-1) divides (a2-1)(m-1)
or just 2p divides m-1.Finally, by the definition of m we have a2p = 1 + m(a2-1) or just a2p ≡ 1 (mod m).It follows that am-1 is also one modulo m, completing the proof. 如果n是基2伪素数，则2^n-1也是，因此无限 无心人 发表于 2022-10-20 16:20
如果n是基2伪素数，则2^n-1也是，因此无限
那基3呢？？？？？？？ nyy 发表于 2022-10-21 15:51
那基3呢？？？？？？？
如果p是素数，n=(3^p-1)/2要么是素数，要么是基3伪素数
页:
[1]