http://poj.org/problem?id=1284
答えはφ(p-1)個になります。証明しましょう。
準備.n(|p-1)についてx^n≡1(modp)はちょうどn個の解を持つ。
証明.p-1=nkとしたとき、
x^(p-1)-1=(x^n-1)(x^(n(k-1))+x^(n(k-1)-1)+...+1)であり、
x^(p-1)-1≡0(modp)の解はp-1=nk個。
x^n-1≡0(modp)の解はn個以下
x^(n(k-1))+x^(n(k-1)-1)+...+1≡0の解はn(k-1)個以下なので
x^n-1≡(modp)の解はn個でなければならない。
n個の解x1,...,xnについてx1^a≡1(modp)を満たす最小の自然数aを位数と定義すると、位数はnの約数しかありえないので、
位数aの解の個数をF(a)と置くと、Σ(a|n)F(a)=nとなる。これがp-1の任意の約数nについて成立している。
またF(1)=1
F(p)=p-1
F(p^2)=p^2-p(pは素数)
F(ab)=F(a)F(b)(aとbは互いに素)が容易に示せ、帰納的にF(a)=φ(a)が成立する。
よって位数p-1の解の個数はF(p-1)=φ(p-1)となる。
x^k≡1(modp)となる集合A(k)を包除原理して求めてもよい。φ(n)を求めるときと合同な集合が出てくる。
ちなみに任意の自然数についてはφ(φ(N))個となります。
ほかにもこの証明をする過程でいろいろ考えた定理を挙げておきます。
- AとNが互いに素の時、A^φ(N)≡1(modN)(証明はA*2A*...*φ(N)A≡1*2*...*φ(N)(modN)より)
(AとNが互いに素ではないときはgcd(A,N)に含まれている素因数を除いたA',N'について適応する)
- A|Bの時φ(A)|φ(B) (φ(A)=A*(p1-1)/p1*(p2-1)/p2から簡単に示せる)
- 十分大きなKをとればA^(K+φ(N))≡A^K(modN)(フェルマーの定理と中国剰余定理から)
これよりA^K(modN)の値はK modφ(N)に依存。
これを利用して原始根の数がφ(φ(N))となることを証明する方法もある。
- 原始根を効率よく見つけるアルゴリズムはない。(だから暗号とかがうまくいく)
int N; int phi[100010]; int main() { rep(i, 1, 100000) phi[i] = i; rep(i, 2, 100000) { if(phi[i] != i) continue; for(int j = i; j < 100000; j += i) { phi[j] -= phi[j] / i; } } while(scanf("%d", &N) != EOF) { printf("%d\n", phi[N - 1]); } }
