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,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

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

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

Cf. A001783, A160377, A211487, A216919.

Sequence in context: A226523 A070238 A062157 * A112347 A057427 A178334

Adjacent sequences: A103128 A103129 A103130 * A103132 A103133 A103134

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