A103131 - OEIS

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

(list; graph; refs; listen; history; text; internal format)

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