Եթե տեսնում ես այս հաղորդագրությունը, նշանակում է՝ մեզ չի հաջողվում կայքում արտաքին ռեսուրսներ բեռնել։

If you're behind a web filter, please make sure that the domains *.kastatic.org and *.kasandbox.org are unblocked.

Հիմնական նյութ

Մոդուլյար արտադրյալ

Արի ուսումնասիրենք մոդուլյար գործողությունների բազմապատկման հատկությունը․

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

Բազմապատկման օրինակ․

Տրված է՝ A=4, B=7, C=6
Արի ստուգենք․ (A * B) mod C = (A mod C * B mod C) mod C
ՀՁԿ= Հավասարման ձախ կողմ
ՀԱԿ= Հավասարման աջ կողմ
ՀՁԿ = (A * B) mod C
ՀՁԿ = (4 * 7) mod 6
ՀՁԿ = 28 mod 6
ՀՁԿ = 4
ՀԱԿ = (A mod C * B mod C) mod C
ՀԱԿ = (4 mod 6 * 7 mod 6) mod 6
ՀԱԿ = (4 * 1) mod 6
ՀԱԿ = 4 mod 6
ՀԱԿ = 4
ՀՁԿ = ՀԱԿ = 4

Մոդուլյար արտադրյալի ապացույցը

Մենք կապացուցենք, որ (A * B) mod C = (A mod C * B mod C) mod C
Պետք է ցույց տանք, որ ՀՁԿ = ՀԱԿ
Մնացորդով բաժանման թեորեմից կարող ենք A-ն և B-ն գրել որպես․
A = C * Q1 + R1, որտեղ 0 ≤ R1 < C և Q1-ն ինչ-որ ամբողջ թիվ է։ A mod C = R1
B = C * Q2 + R2, որտեղ 0 ≤ R2 < C և Q2-ն ինչ-որ ամբողջ թիվ է։ B mod C = R2
ՀՁԿ = (A * B) mod C
ՀՁԿ = ((C * Q1 + R1 ) * (C * Q2 + R2) ) mod C
ՀՁԿ = (C * C * Q1 * Q2 + C * Q1 * R2 + C * Q2 * R1 + R1 * R 2 )  mod C
ՀՁԿ = (C * (C * Q1 * Q2 + Q1 * R2 + Q2 * R1)  + R1 * R 2 )  mod C
Կարող ենք արտաքսել C-ի բազմապատիկները mod C գործողությունը կատարելիս
ՀՁԿ = (R1 * R2) mod C
Հետո արի անենք ՀԱԿ
ՀԱԿ = (A mod C * B mod C) mod C
ՀԱԿ = (R1 * R2 ) mod C
Հետևաբար, ՀԱԿ = ՀՁԿ
ՀՁԿ = ՀԱԿ = (R1 * R2 ) mod C

Ուզո՞ւմ ես միանալ խոսակցությանը։

Առայժմ հրապարակումներ չկան։
Անգլերեն հասկանո՞ւմ ես: Սեղմիր այստեղ և ավելի շատ քննարկումներ կգտնես «Քան» ակադեմիայի անգլերեն կայքում: