|
|
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
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
|
|
|
FORMULA
|
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 *)
|
|
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
|
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|