# Number Theory :3

###### tags: `RTGS`

*Notes: bahannya paling ga jelas*

## Modulo
Apa itu hayo
Modulo itu sisa hasil pembagian, contohnya $34 \bmod 6 = 4$, karena:

Sifatnya ada beberapa:
1. $(a\cdot b)\bmod c= [(a\bmod c)\cdot (b\bmod c)]\bmod c$
2. $(a+b)\bmod c= [(a\bmod c)+(b\bmod c)]\bmod c$
3. $(a-b)\bmod c= [(a\bmod c)-(b\bmod c)]\bmod c$

Pada pembagian tak berlaku :( harus pake inverse modulo

## Barisan dan deret
- Suku ke-$n$ barisan aritmetika: $U_n=a+(n-1)b$
- Jumlah suku ke-$n$ barisan aritmetika: $S_n=\frac{n}{2}(U_1 + U_n) = \frac{n}{2}(2a+(n-1)b)$
- Suku ke-$n$ barisan geometri: $U_n=ar^{n-1}$
- Jumlah suku ke-$n$ barisan geometri: $S_n=\frac{a(1-r^n)}{1-r}$

#### Beberapa Contoh
- $S_n=1+2+3+\dots+n=\frac{n(n+1)}{2}$
- $S_n=1+4+9+16+\dots+n^2 = \frac{n(n+1)(2n+1)}{6}$
- $S_n=1+8+27+64+\dots+n^3=\frac{n^2(n+1)^2}{4}$
- $S_n=1+3+6+10+\dots+\frac{n(n+1)}{2}=\frac{n(n+1)(n+2)}{6}$

## Euclid's Algorithm

Euclid's algorithm menggunakan properti $\text{GCD}(A, B) = \text{GCD}(B, A - B)$.

> **Bukti.** Misalkan $\text{GCD}(A, B) = k$, maka jelas bahwa $k \mid (A - B)$ dan $k \mid B$, maka $\text{GCD}(B, A - B) \ge \text{GCD}(A, B)$.
>
> Sebaliknya, jika $GCD(B, A - B) = l$, jelas bahwa $l \mid A \equiv l \mid (A - B) + B$ dan $l \mid B$, maka $GCD(A, B) \ge \text{GCD(B, A - B)}$.
>
> Maka, terbukti.

Euclid membuat algoritmanya cepat dengan menyadari bahwa $\text{GCD}(A, B) = \text{GCD}(B, A \bmod B)$ menggunakan properti diatas.

Dapat dibuktikan jika $A \ge B$, maka $A \bmod B \le \frac{A}{2}$. sehingga algoritma euclid berjalan dalam $O(\log \min(A, B))$

## Bézout's identity and Linear Diophantine Equations

Untuk bilangan bulat $a, b$ dengan $\text{GCD}(a, b) = d$, dapat dibuktikan bahwa pernyataan $ax + by = k$ mempunyai solusi untuk $x, y$ bilangan bulat jika dan hanya jika $d \mid k$.

Kita dapat menemukan solusinya menggunakan [Extended Euclidean Algorithm](https://cp-algorithms.com/algebra/extended-euclid-algorithm.html#algorithm) (Silahkan baca sendiri implementasinya).

## Some Theorems and Properties

- **Lowest Common Multiple,** $\text{LCM}(A, B) = \frac{AB}{\text{GCD}(A, B)}$.
- **Fermat's Little Theorem,** $a^{p-1}\equiv 1\pmod p$ jika $p$ prima dan $p$ tidak habis membagi $a$.
- **Euler's Totient Function,** $\varphi(n)$ itu berapa banyak bilangan yang relatif prima terhadap $n$ sampai $n$
Contohnya $\varphi(18)=18\cdot(1-\frac{1}{2})\cdot(1-\frac{1}{3})=6$, berarti ada $6$ bilangan relatif prima thdp $18$, yaitu $1, 5, 7, 11, 13, 17$.

- **Euler's Theorem,** jika $a$ dan $n$ relatif prima, maka $a^{\varphi(n)}\equiv1\pmod n$, dimana $\varphi(n)=\text{Euler's Totient Function}.$
- **Inverse Modulo with Fermat's Little,** disuruh hitung $\frac{a}{b} \bmod p$, dimana $p$ relatif prima dengan $b$. Berarti kan sama aja kayak
$$(a\cdot b^{-1})\bmod p=(a\bmod p)\cdot(b^{-1}\bmod p)\bmod p$$
Nah $a\bmod p$ obvious, $b^{-1}\bmod p$ bisa pake Fermat, $b^{-1}\cdot 1=b^{-1}\cdot b^{p-1}\bmod p$.
$$b^{-1}\bmod p=b^{p-2}\bmod p$$
Yay selesai :DDDD

- **Wilson's Theorem**, suatu bilangan bulat $n$ adalah bilangan prima **jika dan hanya jika** $(n-1)!+1$ habis dibagi $n$. Dengan kata lain:
$$(n-1)!\equiv -1\pmod n$$
- **Lazy Caterer's Sequence**, berapa banyak segmen maksimal yang dihasilkan dari suatu lingkaran yang dipotong sebanyak $n$ kali.
$$ p = \frac{n^2+n+2}{2}$$
- **Number of Divisors,** contohnya berapa banyak pembagi $720$ ga mungkin dikuli, jadi caranya kita faktorkan dulu:

$$720=2^4\cdot 3^2\cdot 5$$

Nah jadi pembagi $720$ pasti merupakan faktor dari $720$. Jadi kalo pembaginya misalkan $X$, berarti $X=2^x\cdot 3^y\cdot 5^z,$ dimana $0\leq x\leq4$ dan $0\leq y\leq2,$ dan $0\leq z\leq1$
Berarti banyaknya pembagi $X$ yang mungkin $5\cdot3\cdot2=30$ yay!

Secara umum, jika $n = p_1^{e_1} \cdot p_2^{e_2} \dots p_k^{e_k}$ dimana $p_i$ adalah bilangan prima unik, maka

$\sigma_0(n) = (e_1 + 1) \cdot (e_2 + 1) \cdots (e_k + 1)$

- **Sum of Divisors,** Nah idenya mirip. Misal kita pake $720$ lagi. Faktorisasi primanya tadi:

$$720=2^4\cdot 3^2\cdot 5$$

Maka jumlah semua pembaginya $(1+2+2^2+2^3+2^4)\cdot(1+3+3^2)\cdot(1+5)=2418.$ Perhatikan bahwa jika perkalian tersebut "dibongkar", kita akan menjumlahkan setiap faktor dari $720$.

Secara umum, jika $n = p_1^{e_1} \cdot p_2^{e_2} \dots p_k^{e_k}$ dimana $p_i$ adalah bilangan prima unik, maka

$$\sigma_1(n) = \prod_{i = 1}^k {(1 + p_i + p_i^2 + \dots + p_i^{e_i})} = \prod_{i = 1}^k \frac{p_i^{e_i + 1} - 1}{p_i - 1}$$

- **Multiplicative Function,** Sebuah fungsi $f$ dikatakan *multiplicative* jika

- $f(1) = 1$
- $f(ab) = f(a) \cdot f(b)$ jika $a$ dan $b$ *co-prime*.

Beberapa contoh *multiplicative functions* (semua contoh dibawah merupakan fungsi dari $n$):
- $\text{GCD}(n, k)$ dimana $k$ konstan.
- $\varphi(n)$
- $\sigma_k(n)$

Properti ini kadang berguna untuk menyelesaikan soal.

## Harmonic Series

Harmonic series adalah $H(n) = \sum_{i = 1}^n \frac{1}{i}$. Yang penting untuk diketahui itu adalah $H(n) = O(\log n)$.

Kenapa penting? Banyak soal-soal NT bisa diselesaikan dengan kompleksitas $n H(n) = n + \frac{n}{2} + \frac{n}{3} + \dots + 1$. Sehingga, kalau bisa menemukan solusi dengan kompleksitas gini, sama saja dengan kompleksitas $O(N \log N)$.

Contoh soal banyak dibawah ~~*(Males cari contoh soal buat dijelasin)*~~.

## Chinese Remainder Theorem

Kenapa namanya *Chinese* Remainder Theorem? Karena earliest known statement dari persoalan ini berasal dari Sun-tzu.

> Terdapat sebuah jendral dengan $x$ orang tentara. Dia mengetahui bahwa $400 \le x \le 500$. Kemudian, dia meminta tentaranya untuk berbaris sebagai berikut:
> 
> - Jika tentaranya berbaris dengan $3$ orang per kolom, maka kolom terakhir tersisa $2$ orang.
> - Jika tentaranya berbaris dengan $5$ orang per kolom, maka kolom terakhir tersisa $3$ orang.
> - Jika tentaranya berbaris dengan $7$ orang per kolom, maka kolom terakhir tersisa $2$ orang.
>
> Maka, berapakah banyak tentara jendral tersebut?

Secara formal, diberikan sebuah bilangan bulat $400 \le x \le 500$, diketahui bahwa:

- $x \equiv 2 \pmod 3$
- $x \equiv 3 \pmod 5$
- $x \equiv 2 \pmod 7$

Berapakah $x$?

Nah, datanglah Chinese Remainder Theorem.

CRT menyatakan bahwa jika $p = p_1 \cdot p_2 \dots p_k$ dimana $p_i$ relatif prima terhadap satu sama lain, dan diberikan himpunan persamaan:

- $x \equiv a_1 \pmod {p_1}$
- $x \equiv a_2 \pmod {p_2}$
- $\dots$
- $x \equiv a_k \pmod {p_k}$

Maka terdapat satu solusi $0 \le a < p$ sehingga $x \equiv a \pmod p$.

Cara hitungnya gimana?

Misalkan kita pakai contoh diatas, maka kita misalkan:

$x = (3 \cdot 5)a + (3 \cdot 7)b + (5 \cdot 7)c$, jadi kita perlu cari $a, b, c$.

Maka,
- Jika kita tinjau terhadap $\pmod 3$, maka $x = 35c \equiv 2 \pmod 3$. Maka $c = 1$.
- Jika kita tinjau terhadap $\pmod 5$, maka $x = 21b \equiv 3 \pmod 5$. Maka $b = 3$.
- Jika kita tinjau terhadap $\pmod 7$, maka $x = 15a \equiv 2 \pmod 7$. Maka $a = 2$.

Maka, $x = 30 + 63 + 35 = 128 \equiv 23 \pmod {105}$.

Sehingga, solusi general $x$ adalah $x = 105k + 23$ untuk $k$ bilangan bulat. Sehingga, $x = 105 \cdot 4 + 23 = 443$.

Untuk coding, bole membaca [cp-algo](https://cp-algorithms.com/algebra/chinese-remainder-theorem.html).

## Bahan & Soal Tambahan (RTGS Tahun Lalu)
- [Number Theory](https://drive.google.com/file/d/1mGEp6t2HEy3liKwl8gkRgwBOiqE2Z-9-/view)
- [Modulo Arithmetic](https://drive.google.com/file/d/1-D2-rrmDf0D-qNlbNWlX_DBE2YsGhpPC/view)

## Soal OSK
1. Bilangan Harshad didefinisikan sebagai bilangan yang habis dibagi oleh hasil penjumlahan setiap digit dari bilangan itu sendiri. Contohnya bilangan 18, karena 18 habis dibagi oleh 9. Ada berapa banyak bilangan Harshad dari 1 sampai 50?
a. 20
b. 21
c. 22
d. 23
e. 24
Source : OSK 2019 no. 5

1. Angka yang menempati digit satuan dari $21^{100} - 25^{100} + 29^{100} - 33^{100}$ adalah:
a. 0
b. 2
c. 3
d. 6
e. 8
Source : OSK 2019 no. 2

2. Berapakah hasil $27^{2016}$ mod $26$?
a. 1
b. 2
c. 3
d. 4
e. 5
Source : OSK 2016 no. 3

8. Dua digit terakhir dari $43^{43^{2018}}$ adalah…
a. 41
b. 01
c. 07
d. 49
e. 43
Source : OSK 2020 no. 5

3. Sisa pembagian $1^3 + 2^3 + 3^3 + 4^3 + \dots + 99^3 + 100^3$ oleh $7$ adalah…
a. 1
b. 2
c. 3
d. 4
e. 5
Source : OSK 2020 no. 4

2. Bilangan ajaib adalah bilangan yang memiliki jumlah faktor yang menyisakan 1 apabila dibagi 4, sebagai contoh adalah angka 1, 1 memiliki 1 buah faktor (yaitu 1). Untuk kesekian kalinya, pak Dengklek ingin meminta tolong kalian untuk menghitung ada berapa banyak bilangan ajaib yang berada diantara 1 dan 300 inklusif. Ada berapakah bilangan ajaib yang ingin diketahui pak Dengklek?
a. 9
b. 5
c. 2
d. 4
e. 8
Source : OSK 2019 no. 8

5. Pada suatu hari, Pak Chanek ingin meminjam uang Pak Dengklek. Tetapi, karena Pak Chanek terlalu sering meminjam uang, Pak Dengklek memberikan sebuah ujian.

* Pak Dengklek: “Kamu harus mencari tahu 3 bilangan yang sedang aku pikirkan. Perkalian dari
ketiganya adalah 140. Bilangan terbesarnya adalah bilangan favoritku.”
* Pak Chanek: “Aku tahu bilangan favoritmu, tapi aku masih belum tahu apa ketiga bilangan
tersebut.”
* Pak Dengklek: “Jumlah dari 2 bilangan terkecil adalah bilangan genap.”
* Pak Chanek: “Oh, sekarang aku tahu.”
<br/>Berapakah penjumlahan dari ketiga bilangan tersebut?
a. 41
b. 39
c. 34
d. 28
e. 21
Source : OSK 2019 no. 23

8. Untuk hadiah ulang tahun pak Dengklek, pak Ganesh ingin memberikan beberapa barisan yang sangat unik. Diantaranya adalah:
* 1, 2, 3, 4, 5, 6, ….
* 1, 4, 9, 16, 25, 36, ….
* 1, 2, 6, 24, 120, ….
* 1, 4, 18, 96, ….
Seketika pak Dengklek berkata ke pak Ganesh “Barisan apakah yang kamu berikan kepadaku bung?”. Pak Ganesh pun menjawab, “Saya tidak akan memberitahumu sebelum kamu menemukan suku ke-6 dari barisan terakhir”. Bantulah pak Dengklek untuk mengetahui barisan ke-4 dengan menemukan suku ke-6 nya?
a. 4320
b. 4230
c. 2340
d. 5040
e. 1296
Source : OSK 2019 no. 24

9. Dua orang sahabat, Pak Dengklek dan Pak Ganesh memiliki sejumlah kucing kesayangan yang tak terhingga jumlahnya dengan harga 465 satuan per ekornya. Sedangkan pak Dengklek memiliki milyaran ekor bebek yang setiap bebeknya bernilai 300 satuan. Keduanya melakukan transaksi dengan cara bertukar hewan. Sebagai contoh, jika pak Dengklek berhutang ke pak Ganesh sebesar 135 satuan, maka ia dapat membayar hutangnya dengan memberi pak Ganesh 2 ekor bebek dan mendapatkan sebuah kucing sebagai kembalian. Berapakah pecahan transaksi terkecil yang dapat diselesaikan dengan menggunakan cara pertukaran tersebut ?
a. 5
b. 10
c. 15
d. 135
e. 165
Source : OSK 2018 no. 3

10. Jika FPB dari a dan 2008 = 251. Jika a < 4036, maka nilai terbesar untuk a adalah…
a. 3263
b. 4016
c. 2259
d. 3765
e. 3514
Source : OSK 2018 no. 4

11. Kita tahu bahwa bilangan prima adalah suatu bilangan yang memiliki tepat 2 bilangan pembagi positif. Didefinisikan F-Primes adalah suatu bilangan yang memiliki tepat 5 bilangan pembagi positif. Berapa banyakkah bilangan F-Primes dari 1-1000 (inklusif)?
a. 2
b. 3
c. 4
d. 5
e. 6
Source : OSK 2018 no. 5

12. Diberikan suatu bilangan bulat m yang memenuhi $1009 < m < 2018$. Diberikan pula himpunan $S = \{1, 2, 3, … ,m\}$. Berapakah nilai $m$ terkecil agar selalu terdapat paling sedikit satu pasang anggota himpunan S yang jumlahnya adalah 2018?
a. 2017
b. 1010
c. 505
d. 1009
e. 506
Source : OSK 2018 no. 10

13. Berapakah banyaknya bilangan antara 1-1000, inklusif, dimana perkalian digit-digitnya merupakan
bilangan positif kelipatan 10?
a. 157
b. 156
c. 155
d. 154
e. 153
Source : OSK 2017 no. 1

14. Terdapat 2 bilangan, yaitu 720000 dan 262144. Berapa banyak bilangan berbeda yang membagi habis kedua bilangan tersebut?
a. 7
b. 8
c. 30
d. 31
e. 23
Source : OSK 2016 no. 9

15. Pak Dengklek menjatuhkan sebuah bola pingpong dari ketinggian 25 m. Bola tersebut memantul kembali dengan ketinggian 4/5 kali tinggi semula. Pematulan ini berlangsung terus menerus hingga bola berhenti. Jumlah seluruh lintasan bola adalah … m.
a. 200
b. 215
c. 225
d. 250
e. 235
Source : OSK 2020 no. 7

16. Tempat duduk gedung pertunjukan film diatur mulai dari baris depan ke belakang dengan banyak baris di belakang lebih 4 kursi dari baris di depannya. Bila dalam gedung pertunjukan itu terdapat 15 baris kursi dan baris terdepan ada 20 kursi, kapasitas gedung tersebut adalah ⋯
a. 1200 kursi
b. 800 kursi
c. 720 kursi
d. 600 kursi
e. 300 kursi
Source : OSK 2020 no. 19

17. Pada bidang XY, titik R dan S masing-masing memiliki koordinat (-2, 1) dan (4, -7). Jika titik P adalah titik tengah segmen garis RS, berapakah koordinat titik P?
a. (-1, -3)
b. (1, -4)
c. (1, -3)
d. (2, -4)
e. (3, -4)
Source : OSK 2020 no. 20

18. Blengki memasuki lift di sebuah lantai pada gedung bertingkat. Kemudian lift itu naik 4 lantai lalu turun 3 lantai kemudian naik lagi 4 lantai. Sekarang Blengki berada di lantai 7. Di lantai berapakah Blengki masuk lift?
a. 2
b. 3
c. 4
d. 5
e. 6
Source : OSK 2020 no. 25

19. Berapa hasil dari $42!$ jika di-modulo dengan $2021$?
Source: OSK 2021 no. 23

20. Berapakah digit kedua dari belakang dari nilai $111^{112^{113}}$?

---

### Soal 21
A, B, dan C bekerja untuk sebuah proyek dengan deadline 100 hari.

Jika A dan B saja yang bekerja, maka proyek selesai dalam 144 hari.

Jika A dan C saja yang bekerja, maka proyek akan selesal dalam 135 hari.

Jika B dan C saja yang bekerja, maka proyek akan selesai dalam 120 hari.

Agar proyek cepat selesai, mereka bertiga bekerja bersama-sama. Namun setelah 11 hari bekerja, A mendadak tidak datang. Pada hari keberapakah si A paling lambat harus datang kembali sehingga pekerjaan tersebut dapat selesai dengan tidak melebihi deadline?

### Soal 22
Dua digit terakhir dari $43^{43^{2018}}$ adalah ...

## Soal Coding
- [ABC 182 - To 3](https://atcoder.jp/contests/abc182/tasks/abc182_c)
- [ARC 116C - Multiple Sequences](https://atcoder.jp/contests/arc116/tasks/arc116_c)
- [KSN-P 2021 - Kartu](https://tlx.toki.id/problems/ksnp-2021/B2)
- [CF Round #360 - Remainders Game](https://codeforces.com/problemset/problem/687/B)
- [CF Round #162 - Good Sequences](https://codeforces.com/problemset/problem/264/B)
- [TROC #15 - Tzaph and GCD LCM](https://tlx.toki.id/problems/troc-15/C)
- [BNPCHS 2018 Super Trombosit](https://tlx.toki.id/problems/bnpchs-2018-final/F)
- [CF Round #588 - Kamil and Making a Stream](https://codeforces.com/contest/1230/problem/E)
- [BNPCHS 2021 - Function Declaration (GCD)](https://tlx.toki.id/problems/bnpchs-2021-final/E)
- [OSN 2018 - GCD Festival](https://tlx.toki.id/problems/osn-2018/2C)
- [TROC #4 - GCD Path](https://tlx.toki.id/problems/troc-4/F)
- [TROC #1 - Progression of Trees](https://tlx.toki.id/problems/troc-1/F)
- [ABC #128 - Frog Jump](https://atcoder.jp/contests/abc128/tasks/abc128_f)