1.以所有前n个素数为底的伪素数q(不考虑强伪素数),q值的下限范围?
2.(1)全部以a为底的奇伪素数c(排除Carmichael数),其素因子是否遍历与a互素的所有奇素数?证明或证否
(2)全部Carmichael的素因子,能否遍历所有奇素数?证明或证否
(3)是否一定存在Carmichael数n能被,以a为底的无平方因子的奇伪素数d整除?d不考虑Carmichael数

2.(1)如果不考虑p=3的情形, 可以证明是真命题
对于与a互素且大于3的素数p, 只要构造出形如pq或p^2的a-伪素数就可以
2.(2)的一个更一般的猜想是:
若正整数n满足n与2phi(n)互素, 其中phi(n)为欧拉函数, 则存在能被n整除的Carmichael数
除了D. Larsen在一篇arxiv文章中声称证明了这个猜想之外, 好像还没有其他文献提过相关已知结论
2.(3)对一般的a是不对的, 因为由Korselt准则可以推出上面的猜想中的条件gcd(n, 2phi(n)) = 1是必要的,
因此像21, 55这种数不可能是某个Carmichael数的因子, 再找到以这类数为a-伪素数的正整数a就能构造出反例了
比如8^20≡1(mod 21), 说明21是一个以8为底的伪素数

以下是证明2.(1)的具体过程 (结果在命题5) :
除了有限多组例外, 总可以用以下的几个结论构造出形如p^2或pq的以a为底的伪素数:
----
命题1 (P. Erdős, 1949)
若n,a是大于1的互素整数, 并且a^(n-1)≡1(mod n), 素数p是a^(n-1)-1的素因子且满足p≡1(mod n-1), p>n, 则np是一个以a为底的伪素数
----
命题2 (W. Feit, 1988)
若整数a,n满足a>1,n>2, 并且(a,n)不在以下集合中:
S = {(2,4),(2,6),(2,10),(2,12),(2,18),(3,4),(3,6),(5,6)}
则a^n-1 总存在素因子p满足:
(i) 对任意正整数k<n, p不整除a^k-1
(ii) 要么p^2整除a^n-1, 要么p>n+1
----
命题3
若正整数a≠1,2,3,5,7,17, 则a^2-1有大于3的素因子
----
由上面的结论可以证明:
命题4:
若a是大于1的整数, p是与a互素的素数, 并且(a,p)不属于以下集合:
K = {(3,2),(2,3),(5,3),(7,3),(2,5),(3,5),(2,7),(2,13)}
则存在素数q≥p, 使得pq是以a为底的伪素数
----
命题4的证明: 可以按p=2,p=3,p>3的情形分类讨论
(1) p=2
当正整数a≡1(mod 4)且a>1时, 4是以a为底的伪素数
当正整数a≡3(mod 4)且a>3时, a-1有奇素因子p, 由命题1可知2p是以a为底的伪素数
(2) p=3
当正整数a与3互素且a≠1,2,5,7,17时, 由命题3可知a^2-1总有大于3的素因子q, 再由命题1可知3q一定是以a为底的伪素数
另外当a=17时, 9是以17为底的伪素数
(3) p>3
当正整数a>1且与p互素, 并且(a,p-1)不在S当中时, a^(p-1) - 1总存在一个满足命题2中(i)(ii)的素因子q
由阶的性质可知q≡1(mod p-1), 则q≥p
所以若q≠p (此时q一定大于p), 由命题1可知pq是以a为底的伪素数
若q=p, 由(ii)可知p^2整除a^(p-1)-1, 那么p^2也是以a为底的伪素数, 这是因为
a^(p^2 - 1) = (a^(p-1))^(p+1) ≡ 1^(p+1) = 1 (mod p^2)
另外当a=3, p=7时, q=13是a^(p-1) - 1的因数且满足q>p,q≡1(mod p-1), 由命题1可知pq是以a为底的伪素数
当a=5, p=7时, q=31是a^(p-1) - 1的因数且满足q>p,q≡1(mod p-1), 由命题1可知pq是以a为底的伪素数
当a=2, p=11时, q=31是a^(p-1) - 1的因数且满足q>p,q≡1(mod p-1), 由命题1可知pq是以a为底的伪素数
当a=2, p=19时, q=73是a^(p-1) - 1的因数且满足q>p,q≡1(mod p-1), 由命题1可知pq是以a为底的伪素数
综上所述就证明了命题4

由命题4可以证明:
命题5
若整数a>1, p是与a互素的奇素数, 则存在以a为底的奇伪素数n, 满足n被p整除且n不是Carmichael数
----
因为Carmichael数至少有3个素因子, 形如pq的伪素数一定不是Carmichael数, 按照命题4, 只需要搜索检验当(a,p)∈K 且p>2的情形:
当a=2, p=3时, n = 645 = 3*5*43 是以a为底的奇伪素数而不是Carmichael数, 并且被p整除
当a=5, p=3时, n = 7449 = 3*13*191 是以a为底的奇伪素数而不是Carmichael数, 并且被p整除
当a=7, p=3时, n = 13665 = 3*5*911 是以a为底的奇伪素数而不是Carmichael数, 并且被p整除
当a=2, p=5时, n = 645 = 3*5*43 是以a为底的奇伪素数而不是Carmichael数, 并且被p整除
当a=3, p=5时, n = 2665 = 5*13*41 是以a为底的奇伪素数而而不是Carmichael数, 并且被p整除
当a=2, p=7时, n = 11305 = 5*7*17*19 是以a为底的奇伪素数而不是Carmichael数, 并且被p整除
当a=2, p=13时, n = 13741 = 7*13*151 是是以a为底的奇伪素数而不是Carmichael数, 并且被p整除
这样就证明了命题5
----
注:
(1) 上面的做法没办法证明存在无穷多个满足要求的n, 因为当a,p给定时, 使得pq是a-伪素数的素数q只可能存在有限多个, 这可以由以下结论推出:
命题6 (D. H. Lehmer, 1936 ; P. Erdős, 1949)
若p,q是不相等素数, a是大于1且与pq互素的整数, 则pq是以a为底的伪素数的充分必要条件是
a^(p-1)≡1 (mod q), a^(q-1)≡1 (mod p)
----
(2) A. Rotkiewicz 有一个和命题4有关的猜想:
猜想(A. Rotkiewicz, 1962)
对任意整数a>1, 素数p>13, 总存在素数q>p满足
a^(pq)≡a (mod pq)
----
如果只考虑p与a互素的情形, 上面的猜想相当于将命题4中的要求q≥p加强为q>p. Rotkiewicz证明了在a = 2时这个猜想是成立的
----
(3) 命题1和命题6比Erdős 和 Lehmer的原文中的论述更一般, 但证明方法差不多一样
----
参考文献:
[1] D. H. Lehmer. (1936). On the converse of Fermat's theorem. The American Mathematical Monthly. 43(6), 347-354.
[2] P. Erdős. (1949). On the converse of Fermat's theorem. The American Mathematical Monthly. 56(9), 623-624.
[3] A. Rotkiewicz. (1962). Sur les nombres premiers p et q tels que pq | 2^(pq) - 2. Rendiconti del Circolo Matematico di Palermo. 11, 280-282.
[4] W. Feit. (1988). On Large Zsigmondy primes. Proceedings of the American Mathematical Society. 102(1), 29-36.

当a与k互素,且ord_k(a)与k不互素时,一定不存在被k整除的以a为底的伪素数j.