Kongruensi kuadratis
Download as PPT, PDF0 likes2,861 views
Dokumen ini membahas kongruensi kuadratis dalam bentuk ax2+bx+c=0(mod p) dengan p adalah bilangan prima ganjil. Terdapat teorema yang menjelaskan jumlah solusi mod p dan pengertian residu kuadratis. Selain itu, didefinisikan lambang Legendre dan teorema terkait yang menjelaskan sifat residu kuadratis.
![x2+qx+r=0(mod p)
x2+q.1.x+r=0(mod p)
x2+q.2m.x+r=0(mod p)
x2+q.2m.x+[(qm)2-(qm)2]+r=0(mod p)
(x+(qm))2-(qm)2+r=0(mod p)
(x+(qm))2=((qm)2-r) (mod p) y2=k(mod p)
Contoh.
4x2+9x+5=0(mod 17)
x2+2x+14=0(mod 17)
(x+1)2=4(mod 17)
(x+1)=2(mod 17) atau (x+1)=-2(mod 17)](https://image.slidesharecdn.com/kongruensikuadratis-140411222021-phpapp02/85/Kongruensi-kuadratis-4-320.jpg)
![Definisi. Jika k, p Z, p>0, dan (k,p)=1, maka
a) k disebut residu kuadratis modulo p jika
x2=k(mod p) mempunyai penyelesaian
b) k disebut bukan residu kuadratis modulo p jika
x2=k(mod p) tidak mempunyai penyelesaian
Definisi. Misalkan p bilangan prima ganjil, k Z,
dan k tidak habis dibagi p. Lambang Legendre [k/p]
didefinisikan dengan
1.[k/p] = 1 jika k adalah residu kuadratis modulo p
2.[k/p] = -1 jika k bukan residu kuadratis modulo p](https://image.slidesharecdn.com/kongruensikuadratis-140411222021-phpapp02/85/Kongruensi-kuadratis-5-320.jpg)
![Teorema (Kriteria Euler) Jika p bilangan prima
ganjil, k Z, dan k tidak habis dibagi p, maka
[k/p] =k(p-1)/2mod(p)
Teorema (Lemma Gauss) Misalkan k Z, dan p
bilangan prima ganjil dimana (k,p)=1. Jika r adalah
banyaknya residu terkecil dari k, 2k, 3k, ,[(p-1)/2]k
yang lebih dari p/2, maka [k/p]=(-1)r
Contoh.
x2=7(mod 13)
7, 14,21,28,35,42(mod 13) = 7,1,8,2,9,3(mod 13)
yang lebih dari 13/2 adalah 1,2 dan 3, maka [7/13]=(-1)3](https://image.slidesharecdn.com/kongruensikuadratis-140411222021-phpapp02/85/Kongruensi-kuadratis-6-320.jpg)
Kongruensi kuadratis
- 2. ax2+bx+c=0(mod p) a0, p prima ganjil, (a,p)=1 a-1ax2+a-1bx+a-1c=0(mod p) x2+a-1bx+a-1c=0(mod p) x2+qx+r=0(mod p) Contoh. 4x2-9x+5=0(mod 17) 13.4x2-13.9x+13.5=0(mod 17) x2-117x+65=0(mod 17) x2+2x+14=0(mod 17)
- 3. Teorema. Misalkan k Z, dan p bilangan prima ganjil dimana (k,p)=1. Jika kongruensi x2=k(mod p) dapat diselesaikan, maka terdapat tepat dua penyelesaian yang tidak kongruen modulo p. Contoh. Selesaikan x2=5(mod 11) x2=11(mod 19)
- 4. x2+qx+r=0(mod p) x2+q.1.x+r=0(mod p) x2+q.2m.x+r=0(mod p) x2+q.2m.x+[(qm)2-(qm)2]+r=0(mod p) (x+(qm))2-(qm)2+r=0(mod p) (x+(qm))2=((qm)2-r) (mod p) y2=k(mod p) Contoh. 4x2+9x+5=0(mod 17) x2+2x+14=0(mod 17) (x+1)2=4(mod 17) (x+1)=2(mod 17) atau (x+1)=-2(mod 17)
- 5. Definisi. Jika k, p Z, p>0, dan (k,p)=1, maka a) k disebut residu kuadratis modulo p jika x2=k(mod p) mempunyai penyelesaian b) k disebut bukan residu kuadratis modulo p jika x2=k(mod p) tidak mempunyai penyelesaian Definisi. Misalkan p bilangan prima ganjil, k Z, dan k tidak habis dibagi p. Lambang Legendre [k/p] didefinisikan dengan 1.[k/p] = 1 jika k adalah residu kuadratis modulo p 2.[k/p] = -1 jika k bukan residu kuadratis modulo p
- 6. Teorema (Kriteria Euler) Jika p bilangan prima ganjil, k Z, dan k tidak habis dibagi p, maka [k/p] =k(p-1)/2mod(p) Teorema (Lemma Gauss) Misalkan k Z, dan p bilangan prima ganjil dimana (k,p)=1. Jika r adalah banyaknya residu terkecil dari k, 2k, 3k, ,[(p-1)/2]k yang lebih dari p/2, maka [k/p]=(-1)r Contoh. x2=7(mod 13) 7, 14,21,28,35,42(mod 13) = 7,1,8,2,9,3(mod 13) yang lebih dari 13/2 adalah 1,2 dan 3, maka [7/13]=(-1)3