光滑剩余问题

manthanein

定义：给定素数\(p\)和素数幂\(q\)，素数幂是素数的正整数次方，素数幂包含素数，\(\gcd(p,q)=1\)。如果存在整数\(k\)使得\(\abs{kq+p}\)的任何一个素因子都小于\(p\)，那么称\(p\)是\(q\)的光滑剩余。

显然，2不是任何素数幂的光滑剩余，3是5的光滑剩余（取k=-1或1），3不是31的光滑剩余。当\(q\)是素数而\(p\)大于\(q\)的最小原根时，\(p\)是\(q\)的光滑剩余。5是23的原根，但5是23的光滑剩余（取k=-1）。

那么，对于更大的p，能否判定它是不是对应q的光滑剩余呢？比如说p=5，q=47，也就是说是否存在整数\(k\)使得\(\abs{47k+5}\)的任何素因子都小于5。

mathe

存在k使得|kq+p|的任何素因子都小于p，这个代表某个形如$p_1^{a_1}p_2^{a_2}...p_r^{a_r}$的数(其中$p_1,p_2,...,p_r$小于p)
可以表示为$kq\pm p$, 或者说$p_1^{a_1}p_2^{a_2}...p_r^{a_r}= \pm p (mod q)$
如果其中$p_1,p_2,...,p_r$有一个为q的原根，那么显然成立，但是即使不是，成立的概率也是非常大的。
回到|47k+5|的问题，由于2和3都是47的平方剩余，但是5不是平凡剩余，所以$47k+5$不可能表示为$2^a 3^b (mod 47)$的形式.
但是由于-5是47的平方剩余，所以这道题目还是能够找到，关键就在于要取k为负数，比如k=-11,我们得到|47\times (-11)+5|=512可以满足还比如可以取k=-305296

manthanein

那么出一题：找出最小的素数幂\(q\)，使得对于任意整数\(k\)，\(\abs{kq+5}\)都有大于3的素因数。