如何判读一个数的倍数全有8组成

troy

给点一个正整数，如何判断他的倍数全由8组成，找到最小的那个数。也可能找不到这个数！！
比如3，它的最小的倍数就是888.

gxqcn

只要给定的数与10互素即一定存在。

由欧拉定理，$10^varphi(n) -= 1 (mod n)$
在 $varphi(n)$ 因子中选一个最小的整数 x，使 $10^x -= 1 (mod n)$ 成立，
则 x 个8即为n的最小符合要求的倍数。

troy

那n=2的时候也存在啊！

无心人

应该是不含有素因子5

gxqcn

考虑到“8”本身的因子的贡献，除1、2、4、8外，
其它的数当且仅当该数不含2、5的因子时才存在，计算方法见2楼。

无心人

呵呵
你给分析透了

怎么没回家？

gxqcn

晚上6:30的车，明早天不亮到武汉，再转车。
10月6号早上返回到苏。

troy

$varphi(n)$ 如何计算？

gxqcn

欧拉函数，见 http://zh.wikipedia.org/wiki/%E6%AC%A7%E6%8B%89%E5%87%BD%E6%95%B0

若 $n = p_1^{k_1} p_2^{k_2} \cdots p_r^{k_r}$，则

$\varphi(n) = \prod_{p|n} p^{\alpha_p-1}(p-1) = n\prod_{p|n}(1-\frac{1}{p})$

troy

原帖由 gxqcn 于 2008-9-29 14:10 发表
只要给定的数与10互素即一定存在。

由欧拉定理，10^varphi(n) -= 1 (mod n)
在 $varphi(n)$ 因子中选一个最小的整数 x，使 $10^x -= 1 (mod n)$ 成立，
则 x 个8即为n的最小符合要求的倍数。

在 $varphi(n)$ 因子中选一个最小的整数 x，使 $10^x -= 1 (mod n)$ 成立。
我是用C 语言去实现的，这里求解x的时候，是不是要用大数，或有更好的方法？