第5题

设整数

a,b,c

满足

0<a<c-1

且

1<b<c

。对每个

k

，

0\le k\le a

，令

r_k

为

kb

除以

c

的余数，

0\le r_k<c

。证明集合

\{r_0,r_1,r_2,\ldots,r_a\}

与

\{0,1,2,\ldots,a\}

不同。

第 5/5 步：导出矛盾

上一步下一步

b\not\equiv1,a+b+1\pmod c\Longrightarrow b\equiv ab+b\pmod c\Longrightarrow a\equiv0\pmod c

详细分析

在这两个同余多重集合中，b 不可能对应 1（因 1<b<c），也不可能对应 a+b+1（因 0<a+1<c）。故 b≡ab+b (mod c)。由于 gcd(b,c)=1，推出 a≡0 (mod c)，这与 0<a<c−1 矛盾。因此两余数集合不同。