A.6 · Congruences, divisibility and arithmetic functions

Chuẩn bị GRE đại học. Mục tiêu cục bộ nằm trong phạm vi ETS đã xem xét; đây là giảng dạy nguyên bản, không phải bài thi chính thức hoặc dự đoán điểm số.

Tiền đề: thuật toán Euclid, 作答 nguyên tố và số học模.

• Giải đồng dư tuyến tính bằng điều kiện gcd
• Kết hợp các đồng dư nguyên tố cùng nhau bằng định lý dư Trung Quốc
• Áp dụng định lý Euler chỉ cho các phần dư khả nghịch
• Sử dụng tính chia hết theo lũy thừa nguyên tố để tìm số nguyên thích hợp nhỏ nhất

đồng dư: Sự bằng nhau của các phần dư vì mô-đun chia hết hiệu của chúng.

số totient: Số lượng phần dư nguyên tố cùng với mô-đun số nguyên dương.

Phương trình ax≡b theo modulo n có nghiệm khi và chỉ khi d=gcd(a,n) chia hết b. Nếu có, chia a,b,n cho d để thu được phương trình có hệ số khả nghịch. Nó có một nghiệm phần dư theo modulo n/d và d nghiệm riêng biệt theo modulo n. Chia hệ số nhưng giữ nguyên mô-đun gốc thường làm mất nghiệm. Phân tích thừa số nguyên tố cung cấp một công cụ chia hết khác: nếu n^k phải chia hết cho tích các lũy thừa nguyên tố p^a, mỗi lũy thừa nguyên tố trong n phải lớn ít nhất ceil(a/k). Các lũy thừa tối thiểu này độc lập tạo ra số n thích hợp nhỏ nhất. Đối với n⁴ chia hết cho 2⁷·3⁵, n phải chứa 2² và 3², vì vậy giá trị nhỏ nhất là 36. Đây là điều kiện lũy thừa nguyên tố, không phải là đồng dư giải bằng phép chia模.

Thuật toán Euclid mở rộng biểu thị gcd(a,n) dưới dạng ua+vn. Khi gcd là 1, u là nghịch đảo của a theo modulo n. Chọn đại diện trong khoảng yêu cầu sau khi rút gọn. Đối với 7 và 26, 1=15·7−4·26, vậy 15 là nghịch đảo của 7 theo modulo 26; hãy kiểm tra tích để bắt lỗi dấu.

Đối với các mô-đun dương nguyên tố cùng nhau m,n, định lý dư Trung Quốc cho đúng một nghiệm theo modulo mn cho mỗi cặp điều kiện phần dư. Thay x=r+mk vào đồng dư thứ hai và giải theo k. Nếu các mô-đun không nguyên tố cùng nhau, các giá trị phần dư của chúng phải khớp nhau theo gcd(m,n); khi nhất quán, tính duy nhất là theo bội chung nhỏ nhất, không phải tích.

Số totient Euler phi(n) đếm các phần dư nguyên tố cùng với n. Đối với các thừa số nguyên tố phân biệt p, phi(n)=n nhân tích của (1−1/p). Định lý Euler cho a^phi(n)≡1 chỉ khi gcd(a,n)=1. Trường hợp nguyên tố là định lý nhỏ Fermat. Chỉ rút gọn số mũ sau khi kiểm tra điều kiện này; một phần tử không khả nghịch có thể trở thành zero dưới các lũy thừa lặp lại.

Giải 6x≡9 modulo 15. Ước chung lớn nhất là 3 và chia hết cho 9. Chia cả ba đại lượng để thu được 2x≡3 modulo 5; nghịch đảo của 2 là 3, nên x≡9≡4 modulo 5. Các nghiệm ban đầu modulo 15 là 4,9,14. Đối với x≡2 modulo 4 và x≡3 modulo 7, viết x=2+4k; sau đó 4k≡1 modulo 7, cho k≡2. Do đó x≡10 modulo 28.

Biểu thức a^phi(n)≡1 là sai đối với a tùy ý. Ví dụ, 2 không có nghịch đảo modulo 8 và 2^4 bằng không modulo 8.

Giải $8x\equiv12\pmod{20}$ hoàn toàn. Tìm nghịch đảo của 7 theo modulo 20. Giải thích tại sao định lý Euler không thể dùng để thay thế $2^8$ bằng 1 theo modulo 20.

Giải mẫu

Ước chung lớn nhất là bốn và chia hết cho 12. Chia cả ba số cho ta $2x\equiv3\pmod5$, nên $x\equiv4\pmod5$. Theo modulo 20, bốn đáp án đều là $4,9,14,19$; phép thế vào mỗi lần đều dư 12. Vì $7\cdot3=21$, nghịch đảo của 7 là 3. Mặc dù $\phi(20)=8$, định lý Euler yêu cầu phần tử đơn vị. Ước chung lớn nhất của 2 và 20 là hai, và $2^8=256\equiv16$, không phải 1.

Giải $x\equiv2\pmod6$, $x\equiv5\pmod9$, hoặc chứng minh sự bất nhất. Nêu modulus để đảm bảo tính duy nhất. Tìm số nguyên dương nhỏ nhất n sao cho $2^5\cdot3^7$ chia hết cho $n^3$.

Kiểm tra sau khi đã làm

Các thặng dư đồng nhất theo ước chung lớn nhất ba. Đặt $x=2+6k$: khi đó $6k\equiv3\pmod9$, suy ra $2k\equiv1\pmod3$ và $k\equiv2\pmod3$. Vậy $x\equiv14\pmod{18}$. Modulus là bội chung nhỏ nhất, không phải 54. Đối với bài toán chia hết, viết các lũy thừa nguyên tố trong n. Chúng phải thỏa mãn $3a\ge5$, $3b\ge7$, nên $a\ge2$, $b\ge3$. Số n nhỏ nhất là $2^2\cdot3^3=108$; các nhân tố nguyên tố khác chỉ làm tăng giá trị này.