Ana içerik

Modüler çarpma

Modüler aritmetiğin çarpma özelliğini keşfedelim:

(A * B) mod C = (A mod C * B mod C) mod C

A=4, B=7, C=6 olsun

Doğrulayalım: (A * B) mod C = (A mod C * B mod C) mod C

SOL= Denklemin Sol Tarafı

SAĞ= Denklemin Sağ Tarafı

SOL= (A * B) mod C

SOL = (4 * 7) mod 6

SOL = 28 mod 6

SOL = 4

SAĞ = (A mod C * B mod C) mod C

SAĞ = (4 mod 6 * 7 mod 6) mod 6

SAĞ = (4 * 1) mod 6

SAĞ = 4 mod 6

SAĞ = 4

SOL = SAĞ = 4

(A * B) mod C = (A mod C * B mod C) mod C 'yi kanıtlayacağız

SOL = SAĞ olduğunu göstermeliyiz

Bölüm kalan teoreminegöre A ve B 'yi böyle yazabiliriz:

A = C * Q1 + R1 burada 0 ≤ R1 < C ve Q1 tam sayıdır. A mod C = R1

B = C * Q2 + R2 burada 0 ≤ R2 < C ve Q2 tam sayıdır. B mod C = R2

SOL = (A * B) mod C

SOL = ((C * Q1 + R1 ) * (C * Q2 + R2) ) mod C

SOL = (C * C * Q1 * Q2 + C * Q1 * R2 + C * Q2 * R1 + R1 * R 2 ) mod C

SOL = (C * (C * Q1 * Q2 + Q1 * R2 + Q2 * R1) + R1 * R 2 ) mod C

Mod C'de C'nin katlarını elemine edebiliriz

SOL = (R1 * R2) mod C

SAĞı yapalım

SAĞ = (A mod C * B mod C) mod C

SAĞ = (R1 * R2 ) mod C

Buna göre, SAĞ=SOL

SOL = SAĞ = (R1 * R2 ) mod C

Sıralama ölçütü:

Henüz gönderi yok.