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

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

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

Մոդուլյար հակադարձներ

Ինչ է հակադարձը

Հիշիր, որ թվի և իր հակադարձի արտադրյալը 1 է։ Սովորական թվաբանությունից գիտենք, որ՝
  • A թվի հակադարձը 1/A է, քանի որ A * 1/A = 1 (օրինակ՝ 5-ի հակադարձը 1/5-ն է)
  • 0-ից բացի, բոլոր իրական թվերն ունեն հակադարձ։
  • Թիվն A-ի հակադարձով բազմապատկելը համարժեք է A-ի բաժանելուն (օրինակ՝ 10/5-ը նույնն է, ինչ 10* 1/5-ը)

Ինչ է մոդուլյար հակադարձը

Մոդուլյար թվաբանության մեջ մենք չունենք բաժանում գործողությունը։ Այնուամենայնիվ, ունենք մոդուլյար հակադարձներ։
  • A (mod C)-ի մոդուլյար հակադարձը A^-1-ն է
  • (A * A^-1) ≡ 1 (mod C) կամ (A * A^-1) mod C = 1
  • Միայն այն թվերը, որոնք C-ի հետ փոխադարձաբար պարզ են (թվեր, որոնք C-ի հետ ընդհանուր բաժանարար չունեն), կարող են ունենալ մոդուլյար հակադարձ (mod C)

Ինչպես գտնել մոդուլյար հակադարձը

A (mod C)-ի մոդուլյար հակադարձը գտնելու համար մեթոդ է՝
քայլ 1։ Հաշվել A * B mod C բոլոր B արժեքների համար, որոնք ընկած են 0-ից մինչև C-1
քայլ 2։ A mod C-ի մոդուլյար հակադարձը B-ի այն արժեքն է, որով A * B mod C = 1
Ուշադրություն դարձրու, որ B mod C տերմինը միայն կարող է լինել 0-ից մինչև C-1 ամբողջ թիվ, հետևաբար B-ի ավելի մեծ արժեքների համար ստուգելն ավելորդ կլինի։

Օրինակ․ A=3, C=7

Քայլ 1։ Հաշվիր A * B mod C-ն 0-ից C-1 ընկած B-ի արժեքների համար

3 * 0 ≡ 0 (mod 7)
3 * 1 ≡ 3 (mod 7)
3 * 2 ≡ 6 (mod 7)
3 * 3 ≡ 9 ≡ 2 (mod 7)
3 * 4 ≡ 12 ≡ 5 (mod 7)
3 * 5 ≡ 15 (mod 7) ≡ 1 (mod 7)   <------ ​ԳՏԱՆՔ ՀԱԿԱԴԱՐՁԸ
3 * 6 ≡ 18 (mod 7) ≡ 4 (mod 7)

Քայլ 2։ A mod C-ի մոդուլյար հակադարձն այն B-ի արժեքն է, որով A * B mod C = 1

5-ը 3 mod 7-ի մոդուլյար հակադարձն է, որովհետև 5*3 mod 7 = 1
Պարզ և հասարակ։
Արի մեկ այլ օրինակ դիտարկենք, որտեղ հակադարձ չենք գտնի։

Օրինակ․ A=2 C=6

Քայլ 1։ Հաշվիր A * B mod C-ն 0-ից C-1 ընկած B-ի արժեքների համար

2 * 0 ≡ 0 (mod 6)
2 * 1 ≡ 2 (mod 6)
2 * 2 ≡ 4 (mod 6)
2 * 3 ≡ 6 ≡ 0 (mod 6)
2 * 4 ≡ 8 ≡ 2 (mod 6)
2 * 5 ≡ 10 ≡ 4 (mod 6)

Քայլ 2։ A mod C-ի մոդուլյար հակադարձն B-ի այն արժեքն է, որով A * B mod C = 1

B-ի ոչ մի արժեքով չենք ստանում A * B mod C = 1։ Հետևաբար, A-ն չունի մոդուլյար հակադարձ (mod 6)։
Սա այսպես է, քանի որ 2-ն ու 6-ը փոխադարձաբար պարզ թվեր չեն (նրանց ամենամեծ ընդհանուր բաժանարարը 2-ն է)։

Այս մեթոդը կարծես թե դանդաղ է․․․

Շատ ավելի արագ մեթոդ կա A (mod C)-ի հակադարձը գտնելու համար, որը մենք կքննարկենք հետագա հոդվածներում՝ «Ընդլայնված Էվկլիդյան ալգորիթմ» թեմայում։

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

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