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
Evgeny Kapun, Table of n, a(n) for n = 1..10000
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
KEYWORD
nonn,tabl
AUTHOR
Eric W. Weisstein, Dec 28 2004
STATUS
approved