Residu Kuadrat
- Definisi
- Contoh Soal
Definisi
Bentuk umum persamaan kongruensi kuadrat adalah $$ax^2 +bx +c\equiv 0 (\text{mod }p),\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ } (24.1)$$ di mana $a \not\equiv 0$ (mod $p$) dan $p > 1$. Ketika $p$ adalah bilangan prima ganjil dan $(a, p) = 1$, $(24.1)$ setara dengan $$(2ax +b)^2 \equiv b^2-4ac\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ } (\text{mod }p).$$ Misalkan $y = 2ax + b, D = b^2- 4ac$, maka diperoleh bentuk baku: $$y^2\equiv D\text{ }\text{ }\text{ }(\text{mod }p).\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }(24.2)$$ Ketika $(24.1)$ memiliki solusi $x = x_o$ (mod $p$), maka $(24.2)$ memiliki solusi $y=2ax_o + b$ (mod $p$). Sebaliknya, jika $y = y_o$ (mod $p$) memenuhi $(24.2)$, maka persamaan $2ax \equiv y_o – b$ (mod $p$) dapat diselesaikan untuk mendapatkan solusi $(24.1)$. Dengan demikian, permasalahan menemukan solusi $(24.1)$ untuk $x$ setara dengan menemukan solusi persamaan kongruensi kuadratik berbentuk $(24.2)$ dan kemudian solusi persamaan kongruensi linear.
Definisi 1. Untuk bilangan prima ganjil $p$ dan bilangan bulat $a$ dengan $(a, p) =1$, ketika persamaan kongruensi kuadrat $x^2 \equiv a$ (mod $p$) memiliki solusi untuk $x$, maka $a$ dikatakan sebagai residu kuadrat modulo $p$. Jika tidak, $a$ dikatakan sebagai non-residu kuadrat modulo $p$.
Teorema-teorema yang akan diperkenalkan di bawah ini menyusun teori dasar residu kuadrat.
Teorema I. Untuk setiap bilangan prima ganjil $p$, jumlah residu kuadrat bukan nol modulo $p$ dan non-residu kuadrat modulo $p$ keduanya $\frac{p-1}{2}$.
Definisi 2. Untuk bilangan prima ganjil $p$ dan bilangan bulat $a$ dengan $(a, p) = 1$, definisikan Simbol Legenda $\left(\frac{a}{p}\right)$ dengan $$\left( \frac{a}{p} \right) = \left\{ \begin{array}{cl}
1 & \text{ jika $a$ adalah residu kuadrat modulo $p$}\\
-1 & \text{ jika $a$ adalah non-residu kuadrat modulo $p$.}
\end{array} \right.$$
Teorema II. (Kriteria Euler) Misalkan $p$ bilangan prima ganjil, $a$ bilangan bulat dengan $(a, p) = 1$. Maka $a$ adalah residu kuadrat dari $p$ jika dan hanya jika $$a^{\frac{p-1}{2}}\equiv 1\text{ }\text{ }\text{ }\text{ }\text{ }(\text{mod }p).$$ Konsekuensi I: $\left(\frac{a}{p}\right)\equiv a^{\frac{p-1}{2}}$ (mod $p$).
Konsekuensi II: $\left(\frac{a}{p}\right)\left(\frac{b}{p}\right)=\left(\frac{ab}{p}\right).$
Dengan mempertimbangkan definisi simbol Legendre dan menggunakan teorema II dan I, diperoleh sifat-sifat simbol Legendre berikut:
Untuk bilangan prima ganjil $p$ dan bilangan bulat $a$ dan $b$ yang memenuhi $(a, p) = (b, p) = 1$,
(i) Jika $a\equiv b$ (mod $p$), maka $\left(\frac{a}{p}\right)=\left(\frac{b}{p}\right):$
(ii) $\left(\frac{a^2b}{p}\right)=\left(\frac{b}{p}\right);$
(iii) $\left(\frac{1}{p}\right)=1,\left(\frac{-1}{p}\right)=(-1)^{\frac{p-1}{2}};$
(iv) $\sum_{k=1}^{p-1}\left(\frac{k}{p}\right)=0.$
Teorema III. (Lemma Gaus) Untuk bilangan prima ganjil $p$ dan bilangan bulat $a$ dengan $(a, p) = 1$, definisikan himpunan $S$ dengan $S=\left\{a,2a,3a,…,\left(\frac{p-1}{2}\right)a\right\}.$
Di antara sisa angka dalam $S$ mod $p$ jika $n$ angka lebih besar dari $p/2$, maka $\left(\frac{a}{p}\right)=(-1)^n$.
Teorema IV. (Hukum Timbal Balik Kuadrat) Untuk bilangan prima ganjil yang berbeda $p$ dan $q$, $$\left( \frac{p}{q} \right)\left( \frac{q}{p} \right)=(-1)^{\frac{p-1}{2}\cdot\frac{q-1}{2}}.$$ Mengenai kongruensi kuadrat dengan modulus komposit, teorema berikut memberikan hasil dasar
Teorema V. Jika $p$ adalah bilangan prima ganjil dengan $(a, p) = 1$, maka $x^2 \equiv a$ (mod $p^n$), $n ≥1$ memiliki solusi $f$ jika dan hanya jika $\left(\frac{a}{p}\right)=1.$
Teorema VI. Misalkan $a$ bilangan bulat dan $n$ bilangan bulat komposit positif. Jika $n = p_1^{\alpha_1} p_2^{\alpha_2}…p_r^{\alpha_r}$ adalah faktorisasi prima dari $n$, maka $a$ adalah residu kuadrat modulo $n$ jika dan hanya jika $a$ adalah residu kuadrat modulo $p_i$ untuk semua $i = 1, 2,…, r$.
Contoh Soal
- Untuk sembarang bilangan prima $p$, tentukan apakah persamaan $x^2 + y^2 + pz = 2003$ selalu memiliki solusi bilangan bulat di $x, y, z$. Berikan justifikasi atas jawaban Anda.
Solusi 1: Dalam solusi ini, kami menggunakan lemma berikut:
Lemma. Setiap bilangan prima $p$ dengan $p \equiv 1$ (mod $4$) dapat dinyatakan sebagai penjumlahan dua bilangan kuadrat sempurna.
Bukti Lemma. Karena $p = 4k + 1$, maka $\left(\frac{-1}{p}\right)=(-1)^{\frac{p-1}{2}}=(-1)^{2k}=1$, oleh karena itu terdapat bilangan bulat $u$ sehingga$u^2 +1 \equiv 0$ (mod $p$), yaitu terdapat $k∈\mathbb{N}$ sehingga $u^2 + 1 = kp$. Jadi, terdapat $k∈ \mathbb{N}$ sehingga $$kp=x^2+y^2,\text{ dimana }x,y\in\mathbb{Z}.$$ Jika $k = 1$, maka kesimpulannya terbukti. Jika $k > 1$, misalkan $r \equiv x$ (mod $k$), $s\equiv y$ (mod $k$) sehingga $-\frac{k}{2}<r,s\le \frac{k}{2}$ maka $r^2+s^2\equiv x^2+y^2\equiv 0$ (mod $k$). Jadi, terdapat $k_1 \in \mathbb{N}$ sehingga $r^2+s^2=k_1k$, dan seterusnya. $$(r^2+s^2)(x^2+y^2)=k_1k\cdot kp=k_1k^2p.$$ Karena $(r^2+s^2)(x^2+y^2)=(rx+sy)^2+(ry-sx)^2$, maka $\left(\frac{rx+sy}{k}\right)^2+\left(\frac{ry-sx}{k}\right)^2=k_1p$. Karena $rx+sy\equiv r^2+y^2\equiv 0$ (mod $k$) dan $ry-sx\equiv xy-yx\equiv 0$ (mod $k$), jadi $\frac{rx+sy}{k}$ dan $\frac{ry-sx}{k}$ kedua nya bilangan bulat, yaituu $k_1p$ dapat diekpresikan sebagai jumlah dari dua kuadrat sempurna.
Karena $k_1k=r^2+s^2\le \left(\frac{k}{2}\right)^2+\left(\frac{k}{2}\right)^2=\frac{k^2}{2}\Rightarrow k_1\le \frac{k}{2}<k$, maka proses ini dapat dilanjutkan hingga $k_1 = 1$. Dengan demikian, $p$ dapat dinyatakan sebagai penjumlahan dua kuadrat sempurna.
Di bawah ini kita kembali ke permasalahan awal.
(i) Jika $p = 2$, maka (0, 1, 1001) merupakan solusi;
(ii) Jika $p = 2003$, maka (0, 0, 1) merupakan solusi;
(iii) Jika $p ≠ 2$ dan $p ≠ 2003$, maka $$(2003+2p, 4p) = (2003, +2p, p) = (2003, p) = 1,$$ Jadi, berdasarkan Teorema Dirichlet, deret $\{2003 + 2p + 4p \cdot n\}$ mengandung bilangan prima tak terhingga banyaknya. Asumsikan $q = 2003 + 4pn_0 + 2p$ adalah bilangan prima, maka $q \equiv 1$ (mod $4$). Oleh karena itu, berdasarkan lemma, terdapat bilangan bulat $x, y$ sedemikian rupa sehingga $$x^2+y^2+p(-4n_0-2)=2003.$$ - Buktikan bahwa terdapat bilangan bulat positif $n$ tak terhingga banyaknya sehingga $n^2 + 1$ mempunyai pembagi prima yang lebih besar dari $2n + \sqrt{2n}$.
Solusi: Untuk setiap bilangan prima $p$ dengan $p = 1$ (mod $4$). $\left(\frac{-1}{p}\right)= 1$ menyiratkan bahwa terdapat $n∈ \{1, 2,…, p – 1\}$ sehingga $n^2\equiv −1$ (mod $p$). Oleh karena itu, $p$ adalah faktor prima dari $n^2 + 1$. Dengan menggunakan $p – n$ untuk menggantikan $n$ ketika $n >\frac{p}{2}$, selalu dimungkinkan untuk menjadikan $n$ bilangan bulat sehingga $0 < n <\frac{p}{2}$.
Di bawah ini kami membuktikan bahwa $p > 2n + \sqrt{2n}$ jika $p > 20$. $$(p-2n)^2 \equiv 4n^2 \equiv -4 \text{ }(\text{mod }p) ⇒ (p- 2n)^2 ≥p-4$$ $$⇒ p≥2n +\sqrt{p-4}≥2n + \sqrt{2n+\sqrt{p-4}-4}> 2n + \sqrt{2n}.$$ Terdapat bilangan prima $p$ tak terhingga banyaknya dengan $p \equiv 1$ (mod $4$), sehingga kita memiliki jumlah tak terhingga banyaknya $n ∈ \mathbb{N}$ yang bersesuaian. Jika $(n_o, p_o)$ adalah pasangan seperti itu, karena $n_o^2 +1 = k_op_o$ adalah nilai terbatas, $n_o$ tidak dapat muncul dalam pasangan tak terhingga banyaknya. Oleh karena itu, tak terhingga banyaknya $n$ berbeda harus muncul dalam pasangan-pasangan tersebut. - Jika $2^{m+1}+1$ adalah bilangan prima, dimana $m\in \mathbb{N}$, buktikan $2^{m+1}+1$ membagi $3^{2^m}+1$.
Solusi: Tulis $q=2^{m+1}+1$. Maka $\varphi(q)=q-1=2^{m+1}$. $(3,q)=1$ karena $q\ge 5$, dan dengan teorema kecil fermat $3^{q-1}=3^{2^{m+1}}\equiv 1$ (mod $q$). Maka $$3^{2^m}=3^{\frac{q-1}{2}}\equiv \pm 1\text{ }\text{ }\text{ }\text{ }\text{ }(\text{mod }q)\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }(24.3)$$ Dari $q\equiv 1$ (mod $4$) dan $q \equiv 2$ (mod $3$), menurut Hukum Timbal Balik Kuadrat, $$\left( \frac{3}{q} \right)=(-1)^{\frac{(3-1)(q-1)}{4}}\left( \frac{q}{3} \right)=\left( \frac{2}{3} \right)\equiv 2^{\frac{3-1}{2}}\equiv 2\equiv -1\text{ }\text{ }\text{ }\text{ }\text{ }(\text{mod }3).$$ Di sisi lain, $\left( \frac{3}{q} \right)\equiv 3^{\frac{q-1}{2}}=3^{2^m}$ (mod $q$), juga $3^{2^m}\equiv -1$ (mod $q$), yaitu $$q|(3^{2^m}+1).$$ - Untuk bilangan bulat non-negatif $a < 2007$ manakah kongruensi $x^2+ a \equiv 0$ (mod $2007$) memiliki tepat dua solusi bilangan bulat non-negatif yang berbeda?
Artinya, terdapat tepat dua bilangan bulat non-negatif $u$ dan $v$ yang kurang dari $2007$, sehingga $u^2 + a$ dan $v^2 + a$ keduanya habis dibagi $2007$.
Solusi: Karena $2007=3^2\cdot 223$, jadi jumlah penyelesaian untuk $x$ modulo $2007$ sama dengan hasil kali jumlah penyelesaian untuk $x$ modulo $9$ dan modulo $223$.
Krena $x^2\equiv 0,1,4,7$ (mod $9$), jadi jika $a\in\{2,5,8\}$, maka $x^2+a\equiv 0$ (mod $9$) memiliki dua solusi; jika $a\in\{1,3,4,6,7\}$ maka $x^2+a\equiv 0$ (mod $9$) tidak memiliki solusi; jika $a=0$, maka $x^2+a\equiv 0$ (mod $9$) memiliki tiga solusi.
Untuk persamaan $x^2+a\equiv 0$ (mod $223$), memiliki dua solusi ketika $-a\in S=\{b_i|b_i\equiv i^2$ (mod $223$), $0<b_i<223,i=1,2,…,111\}$; jika $-a\notin S\cup \{0\}$, maka tidak ada solusi dan jika $a\equiv 0$ (mod $223$) maka hanya ada satu solusi.
Jadi, persamaan asli memiliki tepat dua solusi jika dan hanya jika $x^2+a\equiv 0$ (mod $9$) memiliki dua solusi dan $x^2+a\equiv 0$ (mod $223$) memiliki satu solusi.
Misalkan $a=223b$. Karena $223\equiv -2$ (mod $9$) dan $-2$ adalah residu kuadrat modulo $9$, maka $-b$ juga pasti residu kuadrat modulo $9$. Maka $b\in\{2,5,8\}$ dan kita memiliki $$a=2\times 223=446,\text{ }\text{ }a=5\times 223=1115,\text{ }\text{ }a=8\times 223=1784.$$
“You can fool all of the people some of the time, and some of the people all of the time, but you can’t fool all of the people all of the time.”
