A102057 Triangle of modular inverses of b (mod m) for b = 1, ..., m-1, where 0 indicates no modular inverse exists.
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, 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, 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
Offset: 1
Examples
m\b 1 2 3 4 5 6 7 8 9 10 11 2 1 3 1 2 4 1 0 3 5 1 3 2 4 6 1 0 0 0 5 7 1 4 5 2 3 6 8 1 0 3 0 5 0 7 9 1 5 0 7 2 0 4 8 10 1 0 7 0 0 0 3 0 9 11 1 6 4 3 9 2 8 7 5 10 12 1 0 0 0 5 0 7 0 0 0 11
Links
- Evgeny Kapun, Table of n, a(n) for n = 1..10000
- Eric Weisstein's World of Mathematics, Modular Inverse
Programs
-
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
-
Mathematica
Table[ If[ !CoprimeQ[b, m], 0, PowerMod[b, -1, m]], (* or ModularInverse[b, m] with version >= 11.1 *) {m, 1, 15}, {b, 1, m-1}] // Flatten (* Jean-François Alcover, Nov 09 2012, after Eric W. Weisstein *)
Formula
From Evgeny Kapun, Dec 20 2016: (Start)
If gcd(m, b) = 1 = mx+by (Bézout's lemma), then a(m, b) == y (mod m).
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.
If m is prime, then a(m, b) == b^(m-2) (mod m).
If m is prime, then a(m, 1) = 1 and a(m, b) == -floor(m/b)a(m, m mod b) (mod m).
(End)
Comments