Math Labs

Bài 5

Cho a,b,ca,b,c là các số nguyên thỏa mãn 0<a<c−10<a<c-1 và 1<b<c1<b<c. Với mỗi kk, 0≤k≤a0\le k\le a, gọi rkr_k, 0≤rk<c0\le r_k<c, là số dư của kbkb khi chia cho cc. Chứng minh rằng hai tập {r0,r1,r2,…,ra}\{r_0,r_1,r_2,\ldots,r_a\} và {0,1,2,…,a}\{0,1,2,\ldots,a\} khác nhau.
Bước 1 trên 5: Giả sử hai tập số dư bằng nhau
Bước trướcBước tiếp
{r0,…,ra}={0,…,a}⟹gcd⁡(b,c)=1\{r_0,\ldots,r_a\}=\{0,\ldots,a\}\Longrightarrow\gcd(b,c)=1
Phân tích chi tiết

Giả sử hai tập bằng nhau. Khi đó các số dư r_0,…,r_a đôi một khác nhau, nên gcd(b,c)=1; nếu không, phép nhân với b modulo c sẽ lặp lại số dư trước khi hết khoảng.