Fő tartalom

Moduláris szorzás

Vizsgáljuk meg a moduláris aritmetikában a szorzás szabályát:

(A · B) mod C = (A mod C · B mod C) mod C

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

Bizonyítsuk be: (A · B) mod C = (A mod C · B mod C) mod C

BO= az egyenlet bal oldala

JO= az egyenlet jobb oldala

BO = (A · B) mod C

BO = (4 · 7) mod 6

BO = 28 mod 6

BO = 4

JO = (A mod C · B mod C) mod C

JO = (4 mod 6 · 7 mod 6) mod 6

JO= (4 · 1) mod 6

JO = 4 mod 6

JO = 4

BO = JO = 4

Be fogjuk bizonyítani, hogy (A · B) mod C = (A mod C · B mod C) mod C

Meg kell mutatnunk, hogy BO = JO

A maradékra vonatkozó tétel alapján A-t és B-t felírhatjuk az alábbi alakban:

A = C · Q1 + R1, ahol 0 ≤ R1 < C és Q1 egész szám. A mod C = R1

B = C · Q2 + R2, ahol 0 ≤ R2 < C és Q2 egész szám. B mod C = R2

BO = (A · B) mod C

BO = ((C · Q1 + R1 ) · (C · Q2 + R2) ) mod C

BO = (C · C · Q1 · Q2 + C · Q1 · R2 + C · Q2 · R1 + R1 · R 2 ) mod C

BO = (C · (C · Q1 · Q2 + Q1 · R2 + Q2 · R1) + R1 · R 2 ) mod C

C többszörösei elhagyhatók mod C esetén

BO = (R1 · R2) mod C

Most nézzük a JO-t!

JO = (A mod C · B mod C) mod C

JO = (R1 · R2 ) mod C

Ezért JO = BO .

BO = JO = (R1 · R2 ) mod C

Rendezés:

Még nincs hozzászólás.