A.6 · Kekongruenan, pembagian, dan fungsi aritmetika

Persiapan GRE tingkat sarjana. Tujuan lokal dalam cakupan ETS yang ditinjau; ini adalah pengajaran orisinal, bukan uji coba resmi atau prediktor skor.

Prasyarat: Algoritma Euclid, faktor prima, dan aritmetika modular.

• Selesaikan kongruensi linear menggunakan syarat gcd
• Gabungkan kongruensi yang saling prima dengan teorema sisa Cina
• Terapkan teorem Euler hanya untuk residu yang dapat dibalik
• Gunakan pembagi bilangan berpangkat prima untuk mencari bilangan yang paling sesuai terkecil

kongruensi: Kesamaan residu karena modulus membagi selisihnya.

totien: Jumlah residu yang saling prima dengan modulus bilangan bulat positif.

Persamaan ax≡b modulo n memiliki solusi tepat ketika d=gcd(a,n) membagi b. Jika demikian, bagi a,b,n dengan d untuk mendapatkan persamaan dengan koefisien yang dapat dibalik. Persamaan tersebut memiliki satu solusi residu modulo n/d dan d solusi berbeda modulo n. Membagi koefisien tetapi membiarkan modulus asli umumnya kehilangan solusi. Pemfaktoran prima memberikan alat pembagian lain: jika n^k harus habis dibagi oleh hasil kali pangkat-pangkat prima p^a, setiap pangkat prima dalam n harus setidaknya ceil(a/k). Eksponen minimum ini secara independen menghasilkan nilai n yang paling sesuai terkecil. Untuk n⁴ yang habis dibagi 2⁷·3⁵, n harus mengandung 2² dan 3², sehingga nilai terkecil adalah 36. Ini adalah kondisi pangkat prima, bukan kongruensi yang diselesaikan melalui pembagian modular.

Algoritma Euclidean diperluas menyatakan gcd(a,n) sebagai ua+vn. Ketika gcd adalah 1, u merupakan invers dari a modulo n. Pilih perwakilan dalam rentang yang diperlukan setelah reduksi. Untuk 7 dan 26, 1=15·7−4·26, sehingga 15 adalah invers dari 7 modulo 26; verifikasi perkalian untuk menangkap kesalahan tanda.

Untuk modulus positif m,n yang saling prima, teorema sisa Cina memberikan tepat satu solusi modulo mn untuk setiap pasangan kondisi residu. Substitusikan x=r+mk ke dalam kongruensi kedua dan selesaikan untuk k. Jika modulus tidak saling prima, nilai residunya harus sama modulo gcd(m,n); ketika konsisten, keunikan bersifat modulo kelipatan persekutuan terkecil, bukan hasil kalinya.

Totien Euler phi(n) menghitung residu yang saling prima dengan n. Untuk pembagi prima yang berbeda p, phi(n)=n dikali hasil kali (1−1/p). Teorem Euler memberikan a^phi(n)≡1 hanya ketika gcd(a,n)=1. Kasus prima adalah teorem kecil Fermat. Kurangi eksponen hanya setelah memeriksa kondisi ini; non-unit dapat menjadi nol di bawah pangkat berulang.

Selesaikan 6x≡9 modulo 15. GCD-nya adalah 3 dan membagi 9. Bagi ketiga kuantitas tersebut untuk memperoleh 2x≡3 modulo 5; invers dari 2 adalah 3, sehingga x≡9≡4 modulo 5. Solusi-solusi asli modulo 15 adalah 4,9,14. Untuk x≡2 modulo 4 dan x≡3 modulo 7, tulis x=2+4k; lalu 4k≡1 modulo 7, menghasilkan k≡2. Akibatnya x≡10 modulo 28.

Ekspresi a^phi(n)≡1 salah untuk sembarang a. Sebagai contoh, 2 tidak invertible modulo 8 dan 2^4 bernilai nol modulo 8.

Selesaikan $8x\equiv12\pmod{20}$ sepenuhnya. Temukan invers dari 7 modulo 20. Jelaskan mengapa teorem Euler tidak dapat digunakan untuk mengganti $2^8$ dengan 1 modulo 20.

Penyelesaian terarah

Gcd adalah empat dan membagi 12. Membagi ketiga bilangan tersebut menghasilkan $2x\equiv3\pmod5$, sehingga $x\equiv4\pmod5$. Modulo 20 keempat jawaban adalah $4,9,14,19$; substitusi memberikan sisa 12 setiap kali. Karena $7\cdot3=21$, invers dari 7 adalah 3. Meskipun $\phi(20)=8$, teorem Euler memerlukan unit. Gcd dari 2 dan 20 adalah dua, dan $2^8=256\equiv16$, bukan 1.

Selesaikan $x\equiv2\pmod6$, $x\equiv5\pmod9$, atau buktikan inkonsistensi. Nyatakan modulus untuk keunikan. Temukan bilangan positif terkecil n sedemikian rupa sehingga $2^5\cdot3^7$ membagi $n^3$.

Periksa setelah mencoba

Residu-sepadan modulo gcd tiga. Letakkan $x=2+6k$: kemudian $6k\equiv3\pmod9$, sehingga $2k\equiv1\pmod3$ dan $k\equiv2\pmod3$. Dengan demikian $x\equiv14\pmod{18}$. Modulusnya adalah kelipatan persekutuan terkecil, bukan 54. Untuk masalah pembagian, tuliskan pangkat prima dalam n. Mereka harus memenuhi $3a\ge5$, $3b\ge7$, sehingga $a\ge2$, $b\ge3$. Nilai n terkecil adalah $2^2\cdot3^3=108$; faktor prima lain hanya dapat menambahkannya.