MathLabs

第5問

0<a<c−10<a<c-1 および 1<b<c1<b<c を満たす整数 a,b,ca,b,c を取る。各 kk (0≤k≤a0\le k\le a) に対し、kbkb を cc で割った余りを rkr_k (0≤rk<c0\le r_k<c) とする。2つの集合 {r0,r1,r2,…,ra}\{r_0,r_1,r_2,\ldots,r_a\} と {0,1,2,…,a}\{0,1,2,\ldots,a\} が異なることを証明せよ。
ステップ 2/5: 余りを符号化する
前のステップ次のステップ
f(x)=∑j=0axjb−∑j=0axj,xc−1∣f(x)f(x)=\sum_{j=0}^{a}x^{jb}-\sum_{j=0}^{a}x^j,\quad x^c-1\mid f(x)
詳しい解説

f(x)=1+xb+⋯+xab−(1+x+⋯+xa)f(x)=1+x^b+\cdots+x^{ab}-(1+x+\cdots+x^a) と置く。余り集合の一致により各指数 jbjb を cc を法とする余りに置き換えられるので、xc−1x^c-1 は f(x)f(x) を割り切る。