题目大意就是给出一个奇素数,求出他的原根的个数,定义$n$的原根$x$ 满足条件$0 < x < n $,并且有集合$\{ (x_i \bmod n) \mid 1 <= i <=n-1 \}$ 和集合$\{ 1, …, n-1 \}$相等
关于这道题。如果知道欧拉函数的话,看出的答案是$\phi(n-1)$其实也不难
定理:如果$p$有原根,则它恰有$\phi(\phi(p))$个不同的原根
如果$p$为素数,则$\phi(p)=p-1$,因此本题答案就是有$phi(p-1)$个原根
关于证明我也不会,这些都是在Discuss里搜索到的,证明过程也算来自那吧!
对于给出的素数p,首先要明确一点:p的原根必然是存在的(这一点已由Euler证明,此处不再赘述),因此,不妨设其中的一个元根是$a_0(1 \leq a_0 \leq p-1)$
按照题目的定义,$a^i_0 \bmod p (1 \leq i \leq p-1) $的值是各不相同的,再由$p$是素数,联系Fermat小定理可知:$q^{p-1} \bmod p=1(1 \leq q \leq p-1)$(这个在下面有用)
下面证明,如果$b$是$p$的一个异于$a$的元根,不妨令$b$与$a^t_0$关于$p$同余,那么必然有$gcd(t,p-1)=1$,亦即$t$与$p-1$互质;反之亦然;
证明:
若$d=gcd(t,p-1)>1$,令$t=k_1 \times d$,$p-1=k_2 \times d$,则由Fermat可知$(a^{k_1d}_0)^{k_2} \bmod p=(a^{k_2*d}_0)^{k_1} \bmod p = (a^{p-1}_0)^{k_1} \bmod p = 1$
再由$b=a^t_0 (\bmod p)$,结合上面的式子可知:$(a^{k_1d}_0)^{k_2} \bmod n = b^{k_2} \bmod p=1$;
然而$b^0 \bmod p=1$,所以$b^0=b^{k_2} (\bmod p)$,所以$b^i \bmod p$的循环节$=k_2 < p-1$,因此这样的$b$不是原根;
再证,
若$d=gcd(t,p-1)=1$,即$t$与$p-1$互质,那么$b$必然是原根;
否则假设存在$1 \leq j < i \leq p-1$,使得$b^j=b^i (\bmod p)$,即$a^{jt}_0=a^{it}_0 (\bmod p)$,由$a_0$是元根,即$a_0$的循环节长度是$(p-1)$可知,$(p-1) | (it-jt) \rightarrow (p-1) | (i-j)t$,由于$p$与$t$互质,所以$(p-1) | (i-j)$,但是根据假设,$0 < i-j < p-1$,得出矛盾,结论得证;
由上面的两个证明可知$b=a^t_0 (\bmod p)$,是一个元根的充要条件是$t$与$p-1$互质,所有的这些$t$的总个数就是$\phi(p-1)$;具体参见http://poj.org/showmessage?message_id=158630
然后直接套用那个求欧拉函数的模板1A了,我发现我最近好喜欢套模板啊,没办法,知道的太少了
1 |
|