A103131 The product of the residues in [1,n] relatively prime to n, taken modulo n.

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

Author

Eric W. Weisstein, Jan 23 2005

Keywords

• sign

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

Examples

			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.
		

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

• Antti Karttunen, Table of n, a(n) for n = 1..16385
• 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

Crossrefs

Cf. A001783, A160377, A211487, A216919.

Programs

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 *)

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

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

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

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