Berapa sisa dari (34!)³⁴+(35!)³⁵ dibagi 37?

Pada artikel ini, saya akan membahas sebuah soal tentang sisa pembagian, yaitu “berapa sisa dari (34!)³⁴+(35!)³⁵ dibagi 37?“. Semoga soal ini juga dapat menjadi bahan latihan bagi para pembaca. Baiklah mari simak pembahasannya berikut ini.

Beberapa hal yang perlu kalian pahami terlebih dahulu sebelum mengerjakan soal ini adalah konsep modulo, Teorema Wilson, dan Teorema Kecil Fermat.

Pembahasan

Menurut Teorema Wilson, 36! \equiv (37-1)! \equiv -1 \pmod{37}, maka

\begin{aligned}
35! \cdot 36 &\equiv -1 \pmod{37}\\
35! \cdot -1 &\equiv -1 \pmod{37}\\
\end{aligned}

Akibatnya, haruslah 35! \equiv 1 \pmod{37}. Kemudian, dengan cara yang serupa kita peroleh sebagai berikut.

\begin{aligned}
34! \cdot 35 &\equiv 1 \pmod{37}\\
34! \cdot -2 &\equiv 1 \pmod{37}\\
34! \cdot -2 \cdot18 &\equiv 1 \cdot18 \pmod{37}\\
34! \cdot -36 &\equiv 18 \pmod{37}\\
34! \cdot 1 &\equiv 18 \pmod{37}\\
34! &\equiv 18 \pmod{37}
\end{aligned}

Sejauh ini, kita punya (34!)^{34} + (35!)^{35} \equiv 18^{34} + 1^{35} \pmod{37} . Selanjutnya, tinjau 18 sebagai perkalian 6 dan 3. Perhatikan berikut ini.

6^{34} \equiv (6^2)^{17} \equiv 36^{17} \equiv (-1)^{37} \equiv -1 \pmod{37}

Selanjutnya, kita cari juga sisa dari 3^{34} dibagi 37. Sebenarnya, kita bisa saja gunakan cara serupa dengan menggunakan fakta 3^{9} \equiv - 1 \pmod{37}, tetapi menurut saya ini kurang elegan karena kita mencoba-coba berbagai nilai pangkat hingga 9. Saya akan mencoba dengan pendekatan lain, yaitu Teorema Kecil Fermat.

\begin{aligned}
3^{36} & \equiv 1 \pmod{37}\\
3^{35} \cdot3 & \equiv 1 + 2 \cdot 37 \pmod{37}\\
&\equiv 75 \pmod{37}\\
3^{35} &\equiv 25 \pmod{37}\\
3^{34} \cdot 3 &\equiv 25 + 2 \cdot 37 \pmod{37}\\
&\equiv 99 \pmod{37}\\
3^{34} &\equiv33 \pmod{37}\\
&\equiv -4 \pmod{37}
\end{aligned}

Dengan demikian,

\begin{aligned}
(34!)^{34} + (35!)^{35} &\equiv 18^{34} + 1 \pmod{37}\\
&\equiv 6^{34} \cdot3^{34} + 1 \pmod{37}\\
&\equiv -1 \cdot-4+1 \pmod{37}\\
&\equiv 5 \pmod{37}
\end{aligned}

Akhirnya, kita peroleh sisa dari (34!)³⁴+(35!)³⁵ dibagi 37 adalah 5.

Semoga artikel ini dapat berguna bagi para pembaca. Apabila ada pertanyaan, silakan untuk menuliskannya di kolom komentar.

Baca juga soal berikut yang berkaitan dengan sisa pembagian: Pembahasan OSN-K Matematika SMA 2024 – Difa MTK

Tambahan

Saya akan menyajikan beberapa hal tambahan terkait hasil pengerjaan di atas.

Apakah bisa melakukan pembagian pada modulo?

Jawabannya adalah tidak selalu. Hal ini dapat dijamin kebenarannya apabila hasil baginya berupa bilangan bulat serta pembagi dan modulonya saling relatif prima. Mari lihat contoh berikut. Jelas bahwa 3 dan 37 saling relatif prima, maka

3^{34} \cdot 3 \equiv 75 \pmod{37} \implies 3^{34} \equiv 25 \pmod{37}

Hal tersebut dapat berlaku karena berikut ini.

3^{34}\cdot 3  = 37k+75

dengan k adalah suatu bilangan bulat. Karena ruas kiri merupakan kelipatan 3, maka ruas kanan juga harus demikian. Karena 75 merupakan kelipatan 3 dan 37 bukan kelipatan 3, maka haruslah k kelipatan 3. Oleh karena itu, kita dapat membagi kedua ruas dengan 3.

3^{34}= 37\cdot \frac{k}{3} + 25 = 37l + 25 \implies 3^{34} \equiv 25 \pmod{37}

Hasil Pemrograman

import math

i = (math.factorial(34))**34 % 37 + (math.factorial(35))**35 % 37 
print(i)

# i = 5