Kongruen, keterbagian dan fungsi aritmatika
Diperkenalkan| English | Makna |
|---|---|
| congruence/ˈkɒŋɡruːəns/ | Kongruen |
| totient/ˈtəʊʃənt/ | fungsi totien |
Keputusan sebelum jawaban
- Sebuah mesin melakukan satu siklus setiap empat menit dan lainnya setiap tujuh menit. Posisi bersamaan adalah masalah kongruensi, bukan pendekatan desimal.
- Tujuan Anda: Selesaikan kongruensi linear menggunakan syarat GCD.
Bacalah hubungannya
- Persamaan ax≡b modulo n memiliki solusi tepat ketika d=gcd(a,n) membagi b. Jika ya, bagilah a,b,n dengan d untuk mendapatkan persamaan dengan koefisien yang invertible. Persamaan tersebut memiliki satu solusi residu modulo n/d dan d solusi berbeda modulo n. Membagi koefisien tetapi meninggalkan modulus asli umumnya menghilangkan solusi. Faktorisasi prima memberikan alat divisibilitas lain: jika n^k harus habis dibagi oleh perkalian pangkat prima p^a, setiap eksponen prima dalam n harus setidaknya ceil(a/k). Eksponen minimum ini secara independen menghasilkan nilai n positif terkecil yang diperbolehkan. Untuk n⁴ yang habis dibagi 2⁷·3⁵, n harus mengandung 2² dan 3², sehingga nilai terkecil adalah 36. Ini adalah kondisi eksponen prima, bukan kongruensi yang diselesaikan dengan pembagian modular.
- Gabungkan kongruensi yang saling koprima dengan teorema sisa Chinese.
How many distinct solutions modulo 18 satisfy 6x≡12?
Difficulty 1/5 · 100 coins + a small bonus on first completion today
gcd(6,18)=6 divides 12, so there are six solutions; after dividing the modulus too, x≡2 modulo 3.
Gunakan aturan penentu
- 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 hasil kali untuk mendeteksi kesalahan tanda.
- Terapkan teorema Euler hanya pada residu yang invertibel.
What is the least nonnegative x with x≡1 modulo 3 and x≡2 modulo 5?
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Among 1,4,7,10,13 modulo 15, only 7 has residue 2 modulo 5.
Periksa syarat-syaratnya
- Untuk modulus positif yang saling prima m, n, 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 setara modulo gcd(m,n); ketika konsisten, keunikan adalah modulo kelipatan persekutuan terkecil, bukan perkaliannya.
- Gunakan divisibilitas eksponen prima untuk menemukan bilangan bulat yang paling sesuai.
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.
phi(12) equals ____.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
The coprime residues are 1,5,7,11, or use 12(1−1/2)(1−1/3)=4.
Terapkan format tugas
- Totien Euler phi(n) menghitung residu yang saling prima dengan n. Untuk pembagi prima yang berbeda p, phi(n)=n kali hasil kali (1−1/p). Teorem Euler memberikan a^phi(n)≡1 hanya jika gcd(a,n)=1. Kasus prima adalah teorem kecil Fermat. Kurangi eksponen hanya setelah memeriksa syarat ini; non-unit dapat menjadi nol di bawah perpangkatan berulang.
- Gunakan divisibilitas eksponen prima untuk menemukan bilangan bulat yang paling sesuai.
Ekspresi a^phi(n)≡1 salah untuk sembarang a. Sebagai contoh, 2 tidak invertible modulo 8 dan 2^4 bernilai nol modulo 8.
Jawaban mana yang sesuai dengan kasus ini?
Selesaikan kongruensi linear menggunakan syarat gcd
x≡0 modulo 4 and x≡1 modulo 6 have a simultaneous solution.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
The first condition makes x even, the second makes it odd; residues disagree modulo gcd(4,6)=2.
Jaga pembedaan
- kongruensi — Kesamaan residu karena modulus membagi selisihnya.
- totien — Jumlah residu yang saling prima dengan modulus bilangan bulat positif.
- Selesaikan kongruensi linear menggunakan syarat gcd.
- Gabungkan kongruensi yang saling koprima dengan teorema sisa Chinese.
- Terapkan teorema Euler hanya pada residu yang invertibel.
- Gunakan divisibilitas eksponen prima untuk menemukan bilangan bulat yang paling sesuai.
Match each term with its precise meaning in this lesson.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
Keep the distinctions stated in the teaching example.
Put this lesson’s reasoning or event sequence in order.
Difficulty 3/5 · 200 coins + a small bonus on first completion today
The order follows the stated process; check each stage before the next.