www.wikidata.id-id.nina.az

Teorema sisa Tiongkok adalah hasil dari aljabar abstrak dan teori bilangan Kongruensi Simultan dari bilangan bulat sunti

Teorema sisa Tiongkok

Teorema sisa Tiongkok adalah hasil dari aljabar abstrak dan teori bilangan.

Kongruensi Simultan dari bilangan bulat sunting

Bentuk asli dari teorema ini, seperti terdapat dalam buku yang ditulis oleh ahli matematika dari Tiongkok Qin Jiushao dan diterbitkan pada tahun 1247, adalah suatu pernyataan tentang kongruensi simultan (lihat aritmetika modular). Misalkan n1, ..., nk adalah bilangan bulat positif yang setiap pasangnya adalah koprima (yang artinya FPB (ni, nj) = 1 untuk setiap i ≠ j). Maka, untuk setiap bilangan bulat a1, ..., ak, selalu ada bilangan bulat x yang merupakan penyelesaian dari sistem kongruensi simultan

Pseudocode "subtitle": 

x_solves_it=true; for(i= 1; i <= k; i++) if(x % n[i] != a[i] % n[i]) x_solves_it=false;

Terlebih lagi, semua penyelesaian x dari sistem ini adalah juga kongruen modulo dari perkalian n = n1...nk.

Suatu penyelesaian x dapat ditemukan dengan cara sebagai berikut. Untuk setiap i, bilangan bulat ni dan n/ni adalah koprima, dan menggunakan ekstensi algoritme Euklidean kita dapat menemukan bilangan bulat r dan s sehingga r ni + s n/ni = 1. Jika kita menentukan ei = s n/ni, maka kita dapat

untuk j ≠ i. 

for (i= 1; i <= k; i++) {r, s}= ExtendedEuclid( n[i], n / n[i] ); e[i]= s * n / n[i]; for(j= 1; j <= k; j++) if (j != i) assert( e[i] % n[i] == 1 && e[i] % n[j] == 0 );

Penyelesaian dari sistem kongruensi simultan ini adalah 

for(i= 1; i <= k; i++) x += a[i] * e[i];

Sebagai contoh, misalkan kita ingin menemukan suatu bilangan bulat x sehingga 

 x % 3 == 2 % 3 && x % 4 == 3 % 4 && x % 5 == 2 % 5

Menggunakan ekstensi algoritme Euklidean untuk 3 dan 4×5 = 20, kita memperoleh (-13) × 3 + 2 × 20 = 1, di mana e1 = 40 (e[1] == 40). Menggunakan algoritme Euklidean untuk 4 dan 3×5 = 15, kita memperoleh (-11) × 4 + 3 × 15 = 1. Oleh karena itu, e2 = 45 (e[2] == 45). Akhirnya, menggunakan algoritme Euklidean untukr 5 dan 3×4 = 12, kita memperoleh 5 × 5 + (-2) × 12 = 1, yang berarti e3 = -24 (e[3] == -24). Jadi, penyelesaian x adalah 2 × 40 + 3 × 45 + 2 × (-24) = 167. Semua penyelesaian yang lain adalah kongruen 167 modulo 60, yang berarti bahwa mereka semua kongruen 47 modulo 60.

Kadang kala, sistem kongruensi simultan dapat diselesaikan sekalipun ni (n[i]) setiap pasangnya tidak selalu koprima. Syarat-syarat yang lebih tepat adalah sebagai berikut: sistem mempunyai penyelesaian x jika dan hanya jika ai ≡ aj (mod fpb(ni, nj)) (a[i] == a[j] % gcd(n[i], n[j])) untuk semua i dan j. Semua penyelesaian x adalah kongruen modulo kelipatan persekutuan terkecil dari ni (n[i]).

Dengan menggunakan metode substitusi, kita sering kali bisa menemukan penyelesaian dari sistem kongruensi simultan, sekalipun setiap pasang modulusnya tidak selalu koprima.

Pranala luar sunting

wikipedia, wiki, buku, buku, perpustakaan, artikel, baca, unduh, gratis, unduh gratis, mp3, video, mp4, 3gp, jpg, jpeg, gif, png, gambar, musik, lagu, film, buku, permainan, permainan.
Tanggal penerbitan:
Teorema sisa Tiongkok adalah hasil dari aljabar abstrak dan teori bilangan Kongruensi Simultan dari bilangan bulat suntingBentuk asli dari teorema ini seperti terdapat dalam buku yang ditulis oleh ahli matematika dari Tiongkok Qin Jiushao dan diterbitkan pada tahun 1247 adalah suatu pernyataan tentang kongruensi simultan lihat aritmetika modular Misalkan n1 nk adalah bilangan bulat positif yang setiap pasangnya adalah koprima yang artinya FPB ni nj 1 untuk setiap i j Maka untuk setiap bilangan bulat a1 ak selalu ada bilangan bulat x yang merupakan penyelesaian dari sistem kongruensi simultan x a i mod n i f o r i 1 k displaystyle x equiv a i pmod n i quad mathrm for i 1 cdots k nbsp Pseudocode subtitle x solves it true for i 1 i lt k i if x n i a i n i x solves it false Terlebih lagi semua penyelesaian x dari sistem ini adalah juga kongruen modulo dari perkalian n n1 nk Suatu penyelesaian x dapat ditemukan dengan cara sebagai berikut Untuk setiap i bilangan bulat ni dan n ni adalah koprima dan menggunakan ekstensi algoritme Euklidean kita dapat menemukan bilangan bulat r dan s sehingga r ni s n ni 1 Jika kita menentukan ei s n ni maka kita dapat e i 1 mod n i a n d e i 0 mod n j displaystyle e i equiv 1 pmod n i quad mathrm and quad e i equiv 0 pmod n j nbsp untuk j i for i 1 i lt k i r s ExtendedEuclid n i n n i e i s n n i for j 1 j lt k j if j i assert e i n i 1 amp amp e i n j 0 Penyelesaian dari sistem kongruensi simultan ini adalah x i 1 k a i e i displaystyle x sum i 1 k a i e i nbsp for i 1 i lt k i x a i e i Sebagai contoh misalkan kita ingin menemukan suatu bilangan bulat x sehingga x 2 mod 3 displaystyle x equiv 2 pmod 3 nbsp x 3 mod 4 displaystyle x equiv 3 pmod 4 nbsp x 2 mod 5 displaystyle x equiv 2 pmod 5 nbsp x 3 2 3 amp amp x 4 3 4 amp amp x 5 2 5 Menggunakan ekstensi algoritme Euklidean untuk 3 dan 4 5 20 kita memperoleh 13 3 2 20 1 di mana e1 40 e 1 40 Menggunakan algoritme Euklidean untuk 4 dan 3 5 15 kita memperoleh 11 4 3 15 1 Oleh karena itu e2 45 e 2 45 Akhirnya menggunakan algoritme Euklidean untukr 5 dan 3 4 12 kita memperoleh 5 5 2 12 1 yang berarti e3 24 e 3 24 Jadi penyelesaian x adalah 2 40 3 45 2 24 167 Semua penyelesaian yang lain adalah kongruen 167 modulo 60 yang berarti bahwa mereka semua kongruen 47 modulo 60 Kadang kala sistem kongruensi simultan dapat diselesaikan sekalipun ni n i setiap pasangnya tidak selalu koprima Syarat syarat yang lebih tepat adalah sebagai berikut sistem mempunyai penyelesaian x jika dan hanya jika ai aj mod fpb ni nj a i a j gcd n i n j untuk semua i dan j Semua penyelesaian x adalah kongruen modulo kelipatan persekutuan terkecil dari ni n i Dengan menggunakan metode substitusi kita sering kali bisa menemukan penyelesaian dari sistem kongruensi simultan sekalipun setiap pasang modulusnya tidak selalu koprima Pranala luar suntingChinese remainder theorem Diperoleh dari https id wikipedia org w index php title Teorema sisa Tiongkok amp oldid 16757405