2017-10-16から1日間の記事一覧
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…
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…