Aritmatika modular adalah bidang penting dari Teori Bilangan. Di sini kita akan membahas 4 hukum aritmatika modular yang penting tetapi sedikit dibuat-buat, berguna untuk dipahami saat menangani ide matematika lain yang menggunakan bukti aritmatika modular, seperti yang kita lihat dalam eksplorasi Fungsi Carmichael kita .

Catatan :

• Simbol itu |berarti “membagi tanpa sisa”. Begitu x|yjuga dengan cara penulisan lainnya y % x = 0.
• Pembagi persekutuan terbesar atau GCD(x, y)adalah bilangan terbesar yang semua bilangan bulatnya dibagi tanpa sisa.
• Dua bilangan yang coprimetidak memiliki pembagi persekutuan yang lebih besar dari 1. Keduanya prima terhadap satu sama lain.

• JIKA GCD(a, b) = 1, yaitu a& badalah koprime
• DAN a|bc(ingat ini berarti bc % a = 0)
• KEMUDIANa|c

Ingat Identitas Bézout, yang kita bahas saat membahas Algoritma Euclid ? Ini menyatakan bahwa untuk setiap 2 koprime , a& bharus ada nilai x& yyang memenuhi:

ax + by = 1

> multiply by `c`
acx + bcy = c
> acx divides by a
a|acx
> and because we stated that
a|bc
> so bcy must divide by a
a|bcy
> therefore divide both sides of the statement by `a`
acx/a + bcy/a = c/a

• Karena a|bcykita tahu itu bcy/aadalah bilangan bulat.

Aturan 2

• JIKA GCD(a, n) = 1(yaitu koprime)
• DANax ≡ ay (mod n)
• KEMUDIANx ≡ y (mod n)

> IF
ax ≡ ay (mod n)
> THEN
(ax — ay) % n = 0
> Factor out `a`
a(x-y) % n = 0
> Put differently
n|a(x-y)
> Remember that `a` & `n` are coprime
> So applying Rule 1 from above
n|(x-y)
> Meaning that
x ≡ y (mod n)

Aturan 3

• JIKA a& nadalah koprime
• MAKA ada bilangan bulat positif ksehinggaaᵏ≡ 1 (mod n)

Ada sejumlah terbatas koprime dari n, kurang dari n. Mari kita tetapkan nilai ini ke surat itu t. Jadi ada tkoprime nyang kurang dari n.

Diberikan daftar nomor:

a¹, a², ..., aᵗ, aᵗ⁺¹ (each mod n)

• Hanya ada t + 1angka dalam daftar.
• Mereka semua koprime ke n, karena akoprime ke n, dan tidak ada faktor baru yang diperkenalkan.
• Mereka semua lebih kecil dari n, karena masing - masing mod n.

Jadi kita tahu ada dua bilangan bulat h& j, h < j, sehingga:

aʰ ≡ aʲ (mod n)

> substitute out j
aʰ ≡ aʰ⁺ᵏ (mod n)
> separating exponents
aʰ ≡ aʰaᵏ (mod n)

aʰ ≡ aʰaᵏ (mod n)
> cancel aʰ
1 ≡ aᵏ (mod n)

Aturan 4

• JIKAaᵏ ≡ 1 (mod n)
• DAN radalah kelipatan darik
• aʳ≡ 1 (mod n)

Karena radalah kelipatan dari kada beberapa bilangan bulat sdi mana r/k = s.

aʳ = aᵏˢ = (aᵏ)ˢ
> We know that
aᵏ ≡ 1 (mod n)
> So
aʳ ≡ (aᵏ)ˢ ≡ (1)ˢ ≡ 1 (mod n)

Kami baru saja menunjukkan yang berikut:

1. Jika a& badalah koprime, AND a|bc, THENa|c
2. Jika a& badalah koprime, AND ax ≡ ay (mod n), THENx ≡ y (mod n)
3. Jika a& badalah koprime, MAKA terdapat bilangan bulat positif, ksehinggaaᵏ≡ 1 (mod n)
4. Jika aᵏ ≡ 1 (mod n)AND rmerupakan kelipatan dari kTHENaʳ≡ 1 (mod n)

Anda dapat melihatnya diterapkan pada masalah seperti itu ketika kita melihat Fungsi Carmichael .

Lagi ?

Saya menulis buletin terpendek di dunia. Satu hal cepat yang saya pelajari atau lihat atau baca dalam seminggu, setiap hari Rabu.

Saya ingin ini menjadi buletin yang paling mudah diakses dan langsung yang Anda terima.

Mungkin patut dicoba. Berhenti berlangganan juga mudah.

Ini disebut . Sampai jumpa!