Arit atika Modular

Kelompok 6: Dita Nababan, Stefany Sinurat

Dosen Pengampu: Hetdy Sitio

Apa Itu Arit atika Modular?
Aritmatika modular adalah sistem aritmatika bilangan bulat di mana
angka "melingkar" setelah mencapai nilai tertentu, yang disebut
modulus. Konsep ini mirip dengan cara kerja jam, di mana waktu
kembali ke angka 1 setelah mencapai 12.

Dalam aritmatika modular, kita hanya tertarik pada sisa pembagian

bilangan bulat. Ini memungkinkan kita untuk menganalisis sifat-sifat
angka dalam kerangka yang terbatas dan terstruktur.

Konsep ini memiliki aplikasi luas dalam kriptografi, ilmu komputer, teori
bilangan, dan banyak bidang lainnya.
Ko ep Da ar Ko grue i
Inti dari aritmatika modular adalah konsep kongruensi.

Defi i i Ko grue i

Dua bilangan bulat a dan b dikatakan kongruen modulo m (ditulis

a c b (mod m)) jika m membagi (a 2 b). Ini berarti (a 2 b) adalah
kelipatan dari m, atau dengan kata lain, a dan b memiliki sisa yang
sama ketika dibagi dengan m.

Si bol Si a Pe bagia
Simbol c digunakan untuk Fokus utama adalah pada sisa
menunjukkan kongruensi. pembagian.

Modulu ( )
m harus bilangan bulat positif.
Sifat- ifat Arit atika Modular

Reflek if Si etri Tra itif

a c a (mod m) untuk setiap Jika a c b (mod m), maka Jika a c b (mod m) dan
bilangan bulat a. b c a (mod m). b c c (mod m), maka a c c (mod m).

Pe ju la a Perkalia
Jika a c b (mod m) dan Jika a c b (mod m) dan
c c d (mod m), maka c c d (mod m), maka
(a + c) c (b + d) (mod m). (ac) c (bd) (mod m).

Sifat-sifat ini sangat fundamental dan memungkinkan kita untuk melakukan manipulasi aljabar dalam konteks modular.
Opera i Da ar Arit atika Modular
Pe ju la a da Pe gura ga

Pe ju la a Pe gura ga
Jika a (mod m) dan b (mod m), maka (a + b) (mod m) Jika a (mod m) dan b (mod m), maka (a 2 b) (mod m)
adalah sisa dari (a + b) ketika dibagi m. adalah sisa dari (a 2 b) ketika dibagi m.

Rumus: Rumus:
(a + b) (mod m) = ((a (mod m)) + (b (mod m))) (mod m) (a 2 b) (mod m) = ((a (mod m)) 2 (b (mod m))) (mod m)

Contoh: (15 + 7) (mod 5)

(15 (mod 5)) = 0

(7 (mod 5)) = 2

(0 + 2) (mod 5) = 2
Opera i Da ar Arit atika
Modular
Perkalia da Perpa gkata

Perkalia
Jika a (mod m) dan b (mod m), maka (a × b) (mod m) adalah
sisa dari (a × b) ketika dibagi m.

Rumus: (a × b) (mod m) = ((a (mod m)) × (b (mod m))) (mod m)

Perpa gkata
Untuk menghitung ak (mod m), kita dapat menggunakan sifat
perkalian modular berulang kali untuk menghindari bilangan
yang terlalu besar.

Rumus: ak (mod m) = (a × a × ï × a) (mod m) (k kali)

Gunakan ak (mod m) = (a (mod m))k (mod m)

Contoh Perpangkatan: Hitung 710 (mod 3)

7 c 1 (mod 3)

Maka, 710 c 110 (mod 3)

110 = 1

Jadi, 710 (mod 3) = 1

I ver Modular
Invers modular dari suatu bilangan a modulo m adalah bilangan bulat x sedemikian rupa sehingga a × x c 1 (mod m).

Invers modular hanya ada jika a dan m adalah koprima (faktor persekutuan terbesar mereka adalah 1), yaitu gcd(a, m) = 1.

Syarat Keberadaa Metode Pe caria Fu g i Pe ti g

gcd(a, m) = 1 Algoritma Euclidean Diperluas Invers modular sangat penting
adalah metode umum untuk dalam kriptografi dan pemecahan
menemukan invers modular. persamaan kongruensi linear.

Contoh: Invers modular dari 3 modulo 7

Kita mencari x sedemikian ruli 3x c 1 (mod 7).

Coba nilai x = 1, 2, &

3 × 1 = 3 c 3 (mod 7)

3 × 2 = 6 c 6 (mod 7)

3 × 3 = 9 c 2 (mod 7)

3 × 4 = 12 c 5 (mod 7)

3 × 5 = 15 c 1 (mod 7)

Jadi, invers modular dari 3 modulo 7 adalah 5.

Per a aa Ko grue i Li ear
Persamaan kongruensi linear memiliki bentuk ax c b (mod m), di mana kita ingin mencari nilai x.

Tujua Syarat Solu i

Menemukan x yang memenuhi Solusi ada jika dan hanya jika d#b, di
persamaan. mana d = gcd(a, m).

Metode Pe yele aia

Ju la Solu i
Selesaikan dengan menemukan
Jika solusi ada, akan ada d solusi unik
invers modular dari a modulo m, jika
modulo m.
gcd(a, m) = 1.

Contoh: Selesaikan 3x c 5 (mod 7)

Pertama, kita tahu dari contoh sebelumnya bahwa invers modular dari 3 modulo 7 adalah 5.

Kalikan kedua sisi dengan 5: 5 × (3x) c 5 × 5 (mod 7)

15x c 25 (mod 7)

Karena 15 c 1 (mod 7) dan 25 c 4 (mod 7),

Maka, 1x c 4 (mod 7)

Jadi, x c 4 (mod 7)
Lati a Soal da
Pe ba a a (Bagia 1)
Soal 1
1
Tentukan sisa pembagian dari 123456789 (mod 10).

Soal 2
2
Hitung (25 + 18) (mod 7).

Soal 3
3
Berapakah (13 × 9) (mod 5)?

Pembahasan:

Soal 1: Sisa pembagian dari 123456789 dibagi 10 adalah digit

terakhirnya, yaitu 9. Jadi, 123456789 c 9 (mod 10).
Soal 2:

25 c 4 (mod 7)

18 c 4 (mod 7)

(25 + 18) c (4 + 4) (mod 7) c 8 (mod 7) c 1 (mod 7).

Soal 3:

13 c 3 (mod 5)

9 c 4 (mod 5)

(13 × 9) c (3 × 4) (mod 5) c 12 (mod 5) c 2 (mod 5).

Lati a Soal da Pe ba a a (Bagia 2)
1 2

Soal 4 Soal 5
Tentukan nilai x yang memenuhi 2x c 6 (mod 8). Berapakah 5100 (mod 3)?

Pembahasan:

Soal 4: 2x c 6 (mod 8)

gcd(2, 8) = 2. Karena 2 membagi 6, maka ada 2 solusi.

Bagi semua suku dengan 2 dan modulus dengan gcd(2, 8): x c 3 (mod 4).

Ini berarti x = 3 + 4k untuk bilangan bulat k .

Solusi modulo 8 adalah x = 3 dan x = 7.

Soal 5: 5100 (mod 3)

Pertama, cari 5 (mod 3): 5 c 2 (mod 3).

Maka, 5100 c 2100 (mod 3).

Perhatikan pola pangkat 2 (mod 3):

21 c 2 (mod 3)

22 c 4 c 1 (mod 3)

23 c 2 × 1 c 2 (mod 3)

Polanya berulang setiap 2 pangkat. Karena 100 adalah bilangan genap, maka 2100 c (22 )50 c 150 c 1 (mod 3).

Jadi, 5100 (mod 3) = 1.