1. 将整除问题转化为同余方程
已知 19x=n个99⋯9,其中 x 是自然数,也就是说,由 n 个 9 组成的数能够被 19 整除。
由于 99⋯9=10n−1,且 gcd(9,19)=1,故 9(10n−1) 能被 19 整除等价于 10n−1 能被 19 整除。
因此,问题转化为求最小的正整数 n,使得:
10n≡1(mod19)
2. 利用数论性质(费马小定理)缩小 $n$ 的范围
因为 19 是质数,且 gcd(10,19)=1,由费马小定理可得:
1018≡1(mod19)
根据同余的性质,使 10n≡1(mod19) 成立的最小正整数 n(即 10 模 19 的阶)必须是 18 的正因数。
18 的正因数有:1,2,3,6,9,18。
3. 通过检验确定最小的 $n$ 值
依次检验 18 的小于 18 的因数:
- 当 n=1 时,101=10≡1(mod19);
- 当 n=2 时,102=100≡5≡1(mod19);
- 当 n=3 时,103=10×102≡10×5=50≡12≡1(mod19);
- 当 n=6 时,106=(103)2≡122=144≡11≡1(mod19);
- 当 n=9 时,109=106×103≡11×12=132≡18≡−1≡1(mod19)。
由于以上较小的因数均不满足条件,故最小的满足条件的正整数 n=18。