モジュラ逆数(Modular multiplicative inverse)を調べてみた。

オリジナル

実行環境

例

解法1:手計算で

(勉強中)

解法2:wolframalphaのPowerModで

Result
4

解法3:vbaで

Modular inverse　＜

Private Function mul_inv(a As Long, n As Long) As Variant
    If n < 0 Then n = -n
    If a < 0 Then a = n - ((-a) Mod n)
    Dim t As Long: t = 0
    Dim nt As Long: nt = 1
    Dim r As Long: r = n
    Dim nr As Long: nr = a
    Dim q As Long
    Do While nr <> 0
        q = r \ nr
        tmp = t
        t = nt
        nt = tmp - q * nt
        tmp = r
        r = nr
        nr = tmp - q * nr
    Loop
    If r > 1 Then
        mul_inv = "a is not invertible"
    Else
        If t < 0 Then t = t + n
        mul_inv = t
    End If
End Function
Sub aaa_Sub_mi()
    ActiveSheet.Cells.Clear
    Cells(1, 1) = 3
    Cells(1, 2) = 11
    Cells(1, 3) = mul_inv(Cells(1, 1), Cells(1, 2))
End Sub
'3   11  4

解法3:Sageのpower_modで

x=power_mod(3,-1,11);x
4

解法4:sympyのmod_inverseで

from sympy import *
print("#",mod_inverse(3,11))
# 4

逆数計算

省略

応用

解法1:手計算とwolframのPowerModで

(勉強中)

解法2:wolframalphaのChineseRemainderで

結果
39

解法3:Sageのcrtで

x=crt([4,4,6],[5,7,11]);x
39

解法4: sympyのsolve_congruenceで

from sympy.ntheory.modular import solve_congruence
print("#",solve_congruence((4,5),(4,7),(6,11)))
(mpz(39), 385)

参考