MathLabs

第5题

设整数 a,b,ca,b,c 满足 0<a<c−10<a<c-1 且 1<b<c1<b<c。对每个 kk，0≤k≤a0\le k\le a，令 rkr_k 为 kbkb 除以 cc 的余数，0≤rk<c0\le r_k<c。证明集合 {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)。