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

«Google Classroom»

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

Հիշիր, որ թվի և իր հակադարձի արտադրյալը 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)-ի հակադարձը գտնելու համար, որը մենք կքննարկենք հետագա հոդվածներում՝ «Ընդլայնված Էվկլիդյան ալգորիթմ» թեմայում։

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

Մուտք գործել

Դասակարգել ըստ

Առայժմ հրապարակումներ չկան։

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