Order dari Suatu Bilangan

Apakah Anda sudah pernah mendengar kata order? Dimanakah anda menjumpai kata tersebut?

Kata order dapat ditemui salah satunya pada pembahasan mengenai strukrut aljabar, khususnya teori grup dan teori ring. Order dari suatu elemen a di grup atau ring adalah bilangan asli terkecil sehingga a dipangkatkan dengan bilangan tersebut hasilnya adalah elemen identitas. Pada artikel ini akan dibahas mengenai order dari suatu bilangan.

Order dari Suatu Bilangan

Diberikan bilangan asli relatif prima $a$ dan $n$ . Apakah selalu terdapat bilangan asli $m$ sehingga $a^m \equiv 1 \mod n$ ? Artikel ini akan menyelidiki sifat-sifat bilangan $m$ yang memenuhi kondisi tersebut.

Tinjau himpunan $S = \{a,a^2,a^3,\ldots\}$ di modulo $n$ . Jelas bahwa hanya terdapat sebanyak $n$ (berhingga) residu di modulo $n$ . Akibatnya, pasti terdapat dua anggota $S$ yang kongruen di modulo $n$ , sebut $a^k \equiv a^l \mod n$ dengan $k > l$ . Jadi, $a^{k-l} \equiv 1 \mod n$ sehingga terbukti bahwa selalu terdapat bilangan asli $m$ yang memenuhi $a^m \equiv 1 \mod n$ .

Selanjutnya kita akan menyelidiki sifat-sifat bilangan asli terkecil yang memenuhi sifat tersebut.

Definisi

Diberikan bilangan asli $a$ dan $n$ dengan $\gcd(a,n) = 1$ . Bilangan asli $d$ disebut sebagai \textbf{order} dari $a$ modulo $m$ , atau dituliskan $d = \ord_n(a)$ apabila $d$ merupakan bilangan asli terkecil yang memenuhi $a^d \equiv 1 \mod n$ .

Sebagai contoh, perhatikan barisan $(2^n)_{n \geq 1}$ di modulo 7 berikut

$2,2^2,2^3,2^4,2^5,2^6,2^7,\ldots \equiv 2,4,1,2,4,1,2,\ldots \mod 7.$

Dapat dilihat bahwa order dari 2 modulo 7 adalah 3 atau dituliskan $\ord_7(2) = 3$ . Perhatikan bahwa pula bahwa apabila $2^n \equiv 1 \mod 7$ , maka $n$ haruslah merupakan kelipatan 3 (ordernya). Sifat yang cukup intuitif tersebut dibahas pada teorema berikut.

Teorema 1.

[box] Diberikan bilangan asli $a$ dan $n$ dengan $\gcd(a,n) = 1$ . Jika $d = \ord_n(a)$ , maka untuk sebarang bilangan asli $m$ yang memenuhi $a^m \equiv 1 \mod n$ , berlaku $d \mid m$ . [/box]

[learn_more caption=”Bukti:” state=”open”]

Menurut algoritma pembagian, terdapat bilangan bulat $q$ dan $r$ yang memenuhi $m = dq+r$ dan $0 \leq r < d$ . Perhatikan bahwa

$a^m \equiv a^{dq+r} \equiv (a^d)^q \cdot a^r \equiv a^r \mod n$

Akibatnya, $a^r \equiv 1 \mod n$ . Apabila $r \neq 0$ , maka karena $r < d$ , diperoleh suatu kontradiksi dengan fakta bahwa $d$ merupakan bilangan asli terkecil sehingga $a^d \equiv 1 \mod n$ . Jadi, $r = 0$ dan disimpulkan bahwa $d \mid m$ .

[/learn_more]

Akibat 2.

[box] Diberikan bilangan asli $a$ . Berikut adalah beberapa akibat dari Teorema 1.

Jika $p$ adalah bilangan prima, maka $\ord_p(a) \mid p-1$ .
Jika $n$ adalah bilangan asli yang relatif prima dengan $a$ , maka $\ord_n(a) \mid \varphi(n)$ .
Jika $k,l$ dan $n$ adalah bilangan asli serta $\gcd(a,n) = 1$ dan $a^k \equiv a^l \mod n$ , maka $\ord_n(a) \mid k-l$ . [/box]

Teorema 3

[box] Untuk sebarang bilangan asli $a,b,x$ dan $y$ dengan $\gcd(a,b) = 1$ , berlaku

$\gcd(a^x-b^x, a^y-b^y) = a^{\gcd(x,y)} - b^{\gcd(x,y)}.$

[/box]

[learn_more caption=”Bukti:” state=”open”]

Jelas bahwa $a^{\gcd(x,y)} - b^{\gcd(x,y)}$ pasti membagi $a^x-b^x$ dan $a^y-b^y$ sehingga

$a^{\gcd(x,y)} - b^{\gcd(x,y)} \mid \gcd(a^x-b^x,a^y-b^y).$

Selanjutnya, diambil sebarang bilangan asli $r$ yang membagi $a^x-b^x$ dan $a^y-b^y$ . Jelas bahwa $\gcd(a,r) = \gcd(b,r) = 1$ sehingga $a$ dan $b$ punya inverse di modulo $r$ . Menurut Bezout, terdapat bilangan bulat $s$ dan $m$ sehingga $sx + ty = \gcd(x,y)$ . Jadi

$\begin{align*} a^{\gcd(x,y)} = a^{sx+ty} = a^{sx} \cdot a^{ty} &= (a^x)^s \cdot (a^y)^t \\ &\equiv b^{sx} \cdot b^{ty} \equiv b^{sx+ty} \equiv b^{\gcd(x,y)} \mod r \end{align*}$

sehingga $r \mid a^{\gcd(x,y)} - b^{\gcd(x,y)}$ . Karena ini berlaku untuk setiap $r$ pembagi persekutuan $a^x-b^x$ dan $a^y-b^y$ , jika dipilih $r = \gcd(a^x-b^x,a^y-b^y)$ , maka didapat

$\gcd(a^x-b^x,a^y-b^y) \mid a^{\gcd(x,y)} - b^{\gcd(x,y)}.$

[/learn_more]

Contoh

Contoh 1

[AIME 2001]
Banyaknya kelipatan 1001 yang dapat dinyatakan dalam bentuk $10^j - 10^i$ di mana $i$ dan $j$ adalah bilangan bulat dan $0 \leq i < j \leq 99$ adalah $\ldots$

Solusi:

Diperhatikan bahwa

$10^3 \equiv -1 \mod 101 \implies 10^6 \equiv 1 \mod 101$

Jadi, $\ord_{101}(10) \mid 6$ . Namun, karena $10^3 \equiv -1 \mod 101$ , maka $\ord_{101}(10) = 6$ . Akibatnya, jika untuk suatu $(i,j)$ dengan $0 \leq i < j \leq 99$ berlaku $101 \mid 10^j-10^i$ , berlaku

$101 \mid 10^{j-i} - 1 \implies 6 \mid j-i.$

Begitu pula sebaliknya. Apabila $(i,j)$ adalah pasangan di mana $0 \leq i < j \leq 99$ dengan $6 \mid j-i$ , pasti berlaku $101 \mid 10^j-10^i$ . Akibatnya, cukup dihitung banyaknya $(i,j)$ yang memenuhi $0 \leq i < j \leq 99$ dan $6 \mid j-i$ . Pembaca dipersilahkan untuk memverifikasi bahwa banyaknya pasangan tersebut adalah 784.

Contoh 2

Diberikan bilangan prima $p$ . Buktikan bahwa semua faktor prima $2^p-1$ lebih besar dari $p$ .

Solusi:

Misalkan $q$ adalah faktor prima $2^p-1$ dan $\ord_q(2) = d$ . Diperoleh

$q \mid 2^p-1 \text{ dan } q \mid 2^{q-1} - 1$

Akibatnya, $d \mid p$ dan $d \mid q-1$ . Karena $d \mid p$ , maka $d = 1$ atau $d = p$ .

Jika $d = 1$ , diperoleh kontradiksi sebab $q \mid 2^1-1 = 1$ .
Jika $d = p$ , diperoleh $p \mid q-1$ sehingga $q-1 \leq p \implies q > p

Terbukti.

Order dari Suatu Bilangan

Published by ricky.the.ising on October 21, 2020October 21, 2020

Order dari Suatu Bilangan

Contoh

0 Comments

Leave a Reply Cancel reply

Relasi Urutan Pada Bilangan Bulat

Sistem Bilangan Bulat

Operasi Perkalian Pada Sistem Bilangan Asli

Order dari Suatu Bilangan

Published by ricky.the.ising on October 21, 2020October 21, 2020

Order dari Suatu Bilangan

Contoh

0 Comments

Leave a Reply Cancel reply

Related Posts

Relasi Urutan Pada Bilangan Bulat

Sistem Bilangan Bulat

Operasi Perkalian Pada Sistem Bilangan Asli