Berapakah nilai dari 2022²⁰⁰⁰ x 100! (Mod 707)? (Dimana n!

Berikut ini adalah pertanyaan dari trip79517 pada mata pelajaran TI untuk jenjang Sekolah Menengah Atas

Berapakah nilai dari 2022²⁰⁰⁰ x 100! (Mod 707)? (Dimana n! = n x (n- 1) x(n-2) ... x 2 x 1, sedangkan x (mod y) berarti sisa bagi dari x oleh y dengan nilai antara 0 sampai y - 1):

Jawaban dan Penjelasan

Berikut ini adalah pilihan jawaban terbaik dari pertanyaan diatas.

Nilai dari $2022^{2000} \times 100! \: (mod \: 707)$ adalah 504.

PEMBAHASAN

Operasi modulo adalah operasi yang menyatakan sisa bagi antara dua bilangan bulat. Jika n = ax + b, maka bentuk tersebut dapat dinyatakan juga dengan n mod a = b atau n ≡ b (mod a).

Beberapa sifat modulo:

1. Perkalian

$a \times b (mod n)$ akan sama dengan $((a \: mod \: n) \times (b \: mod \: n)) \: mod \: n$

2. Perpangkatan

$a^b mod n$ akan sama dengan $(a \: mod \: n)^b mod n$

3. Pembagian

Jika $an \equiv bn \: mod \: c$ , maka $a \equiv b \: mod \frac{c}{GCD(c, n)}$

4. Fermat's Little Theorem

Untuk setiap p bilangan prima, a bilangan asli yang tidak habis dibagi p

$a^{(p - 1)} \equiv 1 \: mod \: p$

5. Wilson's Theorem

Untuk setiap p bilangan prima

$(p - 1)! \equiv p -1 \: mod \: p$

6. Chinese Remainder Theorem

Jika terdapat beberapa sistem kongruensi dengan modulus yang saling koprima, maka sistem kongruensi tersebut memiliki solusi yang unik.

PERTANYAAN

Nilai dari $2022^{2000} \times 100! \: (mod \: 707)$ adalah ....

PENYELESAIAN

Pecah operasi di atas menjadi

$2022^{2000} \times 100! \: mod \: 707 = (2022^{2000} \: mod \: 707) \times (100! \: mod \: 707)$

Lalu, kita selesaikan satu per satu.

Dari Fermat's Little Theorem

$2022^{100} \equiv 1 \: (mod \: 101)$

$2022^{2000} \equiv {2022^{100}}^{20} \equiv 1^{20} \equiv 1 \: (mod \: 101)$

Dari Fermat's Little Theorem (lagi)

$2022^6 \equiv 1 \: (mod \: 7)$

$2022^{2000} \equiv {2022^6}^{337} \equiv 1^{337} \equiv 1 \: (mod \: 7)$

Karena sisa baginya sama dan 101 dan 7 relatif prima, maka

$2022^{2000} \equiv 1 (mod \: 707)$

Dari Wilson Theorem

$100! \equiv 100 \: (mod \: 101) \: \: \: ...(i)$

Perhatikan bahwa $100! = 1 \times 2 \times ... \times 7 \times ... \times 99 \times 100$ . Terlihat jelas bahwa $7 \divides 707$ . Maka, $100! \cong 0 \: (mod \: 7)$ . Bentuk tersebut dapat ditulis menjadi $100! = 7a \: \: \: ...(ii)$ .

Satukan persamaan (i) dan (ii).

$7a \equiv 100 \: (mod 101)$

Kita akan mencari invers modulo. Mencari invers modulo prinsipnya sama dengan menggunakan sifat pembagian. Karena langkahnya panjang (dan rasanya udah kayak beda materi), proses mencari inversnya akan diletakkan di bagian bawah.

$a \equiv 72 \: (mod 101)$