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\} 不同。
第 1/5 步：假设余数集合相等
上一步下一步
{r0,…,ra}={0,…,a}⟹gcd⁡(b,c)=1\{r_0,\ldots,r_a\}=\{0,\ldots,a\}\Longrightarrow\gcd(b,c)=1
详细分析

假设两集合相等，则余数 r_0,…,r_a 两两不同，所以 gcd(b,c)=1；否则模 c 乘以 b 会在该范围结束前重复余数。