login
A103131
The product of the residues in [1,n] relatively prime to n, taken modulo n.
5
0, 1, -1, -1, -1, -1, -1, 1, -1, -1, -1, 1, -1, -1, 1, 1, -1, -1, -1, 1, 1, -1, -1, 1, -1, -1, -1, 1, -1, 1, -1, 1, 1, -1, 1, 1, -1, -1, 1, 1, -1, 1, -1, 1, 1, -1, -1, 1, -1, -1, 1, 1, -1, -1, 1, 1, 1, -1, -1, 1, -1, -1, 1, 1, 1, 1, -1, 1, 1, 1, -1, 1, -1, -1, 1, 1, 1, 1, -1, 1, -1, -1, -1, 1, 1, -1, 1, 1, -1, 1, 1, 1, 1, -1, 1, 1, -1, -1, 1, 1, -1, 1
OFFSET
1,1
COMMENTS
Old name was: Minimal residue (in absolute value) of A001783(n) (mod n).
If the positive representation for integers modulo n is used this is A160377. Here the symmetric (or minimal) representation for the integers modulo n is used.
From Gauss's generalization of Wilson's theorem (see Weisstein link) it follows that, for n>1, a(n) = -1 if and only if there exists a primitive root modulo n (cf. the Hardy and Wright reference, Theorem 129. p. 102). (Adapted from a comment by Vladimir Shevelev in A001783). - Peter Luschny, Oct 20 2012
REFERENCES
G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, Fifth ed., Clarendon Press, Oxford, 2003, Theorem 129, p. 102.
LINKS
J. B. Cosgrave and K. Dilcher, Extensions of the Gauss-Wilson Theorem, Integers: Electronic Journal of Combinatorial Number Theory, 8 (2008).
Eric Weisstein's World of Mathematics, Wilson's theorem
FORMULA
For n>2, a(n)=-1 if A060594(n)=2, or equivalently if n is in A033948; otherwise a(n)=1. - Max Alekseyev, May 26 2009; edited by Peter Luschny, May 25 2017.
a(n) = Gauss_factorial(n, n) modulo n. (Definition of the Gauss factorial in A216919.) - Peter Luschny, Oct 20 2012
For n > 2, a(n) = (-1)^A211487(n). (See Max Alekseyev's formula above.) - Antti Karttunen, Aug 22 2017
EXAMPLE
The residues in [1, 22] relatively prime to 22 are [1, 3, 5, 7, 9, 13, 15, 17, 19, 21] and the product of those residues is -1 modulo 22.
MAPLE
A103131 := proc(n) local k, r; r := 1;
for k to n do if igcd(n, k) = 1 then r := mods(r*k, n) fi od;
r end: seq(A103131(i), i=1..102); # Peter Luschny, Oct 20 2012
MATHEMATICA
a[n_] := If[IntegerQ[PrimitiveRoot[n]], -1, 1]; a[1] = 0; a[2] = 1; Table[a[n], {n, 1, 102}] (* Jean-François Alcover, Nov 09 2012, after Max Alekseyev *)
PROG
(Sage)
def A103131(n):
def smod(a, n): return a-n*ceil(a/n-1/2) if n != 0 else a
r = 1
for k in (1..n):
if gcd(n, k) == 1: r = smod(r*k, n)
return r
[A103131(n) for n in (1..102)] # Peter Luschny, Oct 20 2012
(PARI)
A211487(n) = if(n%2, !!isprimepower(n), (n==2 || n==4 || (isprimepower(n/2, &n) && n>2))); \\ After Charles R Greathouse IV's code for A033948.
A103131(n) = if(n<=2, n-1, (-1)^A211487(n)); \\ Antti Karttunen, Aug 22 2017
CROSSREFS
KEYWORD
sign
AUTHOR
Eric W. Weisstein, Jan 23 2005
EXTENSIONS
Definition rewritten by Max Alekseyev, May 26 2009
New name from Peter Luschny, Oct 20 2012
a(2) set to 1 by Peter Luschny, May 25 2017
STATUS
approved