izak

widget: modular inverses

Multiplicative Inverse Sequence

Multiplicative Inverse Sequence

The modular multiplicative inverse of an integer $a $ modulo $m $ is an integer $y $ such that: $ a \cdot y \equiv 1 \pmod{m} $ This inverse exists if and only if $a $ and $m $ are coprime (i.e., their greatest common divisor, or GCD, is 1). For example: If $x = 2 $ and $m = 7 $, the sequence might look like: $ [4, 2, 1, 4, 2, 1, \dots] $ This is because: $ 2^1 \equiv 2 \pmod{7} $, and the inverse of 2 modulo 7 is 4. $ 2^2 \equiv 4 \pmod{7} $, and the inverse of 4 modulo 7 is 2. $ 2^3 \equiv 1 \pmod{7} $, and the inverse of 1 modulo 7 is 1. The sequence repeats after this point.