cp's OEIS Frontend

A102057 Triangle of modular inverses of b (mod m) for b = 1, ..., m-1, where 0 indicates no modular inverse exists.

%I A102057 #15 Feb 16 2025 08:32:55
%S A102057 1,1,2,1,0,3,1,3,2,4,1,0,0,0,5,1,4,5,2,3,6,1,0,3,0,5,0,7,1,5,0,7,2,0,
%T A102057 4,8,1,0,7,0,0,0,3,0,9,1,6,4,3,9,2,8,7,5,10,1,0,0,0,5,0,7,0,0,0,11,1,
%U A102057 7,9,10,8,11,2,5,3,4,6,12,1,0,5,0,3,0,0,0,11,0,9,0,13,1,8,0,4,0,0,13
%N A102057 Triangle of modular inverses of b (mod m) for b = 1, ..., m-1, where 0 indicates no modular inverse exists.
%C A102057 For all m, a(m, 1) = 1 and a(m, m-1) = m-1. - _Evgeny Kapun_, Dec 20 2016
%C A102057 For all coprime m and b, a(m, b)*b == 1 (mod m) and a(m, a(m, b)) = b. - _Evgeny Kapun_, Dec 20 2016
%H A102057 Evgeny Kapun, <a href="/A102057/b102057.txt">Table of n, a(n) for n = 1..10000</a>
%H A102057 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/ModularInverse.html">Modular Inverse</a>
%F A102057 From _Evgeny Kapun_, Dec 20 2016: (Start)
%F A102057 If gcd(m, b) = 1 = mx+by (Bézout's lemma), then a(m, b) == y (mod m).
%F A102057 If gcd(m, b) = 1, then a(m, b) == b^(phi(m)-1) == b^(psi(m)-1) (mod m), where phi(n) is A000010 and psi(n) is A002322.
%F A102057 If m is prime, then a(m, b) == b^(m-2) (mod m).
%F A102057 If m is prime, then a(m, 1) = 1 and a(m, b) == -floor(m/b)a(m, m mod b) (mod m).
%F A102057 (End)
%e A102057 m\b 1 2 3 4 5 6 7 8 9 10 11
%e A102057 2   1
%e A102057 3   1 2
%e A102057 4   1 0 3
%e A102057 5   1 3 2 4
%e A102057 6   1 0 0 0 5
%e A102057 7   1 4 5 2 3 6
%e A102057 8   1 0 3 0 5 0 7
%e A102057 9   1 5 0 7 2 0 4 8
%e A102057 10  1 0 7 0 0 0 3 0 9
%e A102057 11  1 6 4 3 9 2 8 7 5 10
%e A102057 12  1 0 0 0 5 0 7 0 0  0 11
%t A102057 Table[ If[ !CoprimeQ[b, m], 0, PowerMod[b, -1, m]],
%t A102057 (* or ModularInverse[b, m] with version >= 11.1 *)
%t A102057 {m, 1, 15}, {b, 1, m-1}] // Flatten (* _Jean-François Alcover_, Nov 09 2012, after _Eric W. Weisstein_ *)
%o A102057 (Haskell) [let g 1 0 x y = x; g a 0 x y = 0; g a b x y = g b (mod a b) y (x - y * div a b) in g m b 0 1 `mod` m | m <- [1..], b <- [1..m-1]] -- _Evgeny Kapun_, Dec 20 2016
%K A102057 nonn,tabl
%O A102057 1,3
%A A102057 _Eric W. Weisstein_, Dec 28 2004