login
A102057
Triangle of modular inverses of b (mod m) for b = 1, ..., m-1, where 0 indicates no modular inverse exists.
4
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,3
COMMENTS
For all m, a(m, 1) = 1 and a(m, m-1) = m-1. - Evgeny Kapun, Dec 20 2016
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
LINKS
Eric Weisstein's World of Mathematics, Modular Inverse
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)
EXAMPLE
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
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 *)
PROG
(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
CROSSREFS
Sequence in context: A146540 A162922 A246180 * A276276 A157497 A257961
KEYWORD
nonn,tabl
AUTHOR
Eric W. Weisstein, Dec 28 2004
STATUS
approved