A103131 - OEIS

%I #39 Mar 23 2022 12:07:32

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

%T -1,1,-1,1,-1,1,1,-1,1,1,-1,-1,1,1,-1,1,-1,1,1,-1,-1,1,-1,-1,1,1,-1,

%U -1,1,1,1,-1,-1,1,-1,-1,1,1,1,1,-1,1,1,1,-1,1,-1,-1,1,1,1,1,-1,1,-1,-1,-1,1,1,-1,1,1,-1,1,1,1,1,-1,1,1,-1,-1,1,1,-1,1

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

%C Old name was: Minimal residue (in absolute value) of A001783(n) (mod n).

%C 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.

%C 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

%D G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, Fifth ed., Clarendon Press, Oxford, 2003, Theorem 129, p. 102.

%H Antti Karttunen, <a href="/A103131/b103131.txt">Table of n, a(n) for n = 1..16385</a>

%H J. B. Cosgrave and K. Dilcher, <a href="http://www.emis.de/journals/INTEGERS/papers/i39/i39.Abstract.html"> Extensions of the Gauss-Wilson Theorem</a>, Integers: Electronic Journal of Combinatorial Number Theory, 8 (2008).

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Wilsonstheorem.html">Wilson's theorem</a>

%F 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.

%F a(n) = Gauss_factorial(n, n) modulo n. (Definition of the Gauss factorial in A216919.) - _Peter Luschny_, Oct 20 2012

%F For n > 2, a(n) = (-1)^A211487(n). (See _Max Alekseyev_'s formula above.) - _Antti Karttunen_, Aug 22 2017

%e 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.

%p A103131 := proc(n) local k, r; r := 1;

%p for k to n do if igcd(n,k) = 1 then r := mods(r*k, n) fi od;

%p r end: seq(A103131(i), i=1..102);   # _Peter Luschny_, Oct 20 2012

%t 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_ *)

%o (Sage)

%o def A103131(n):

%o     def smod(a,n): return a-n*ceil(a/n-1/2) if n != 0 else a

%o     r = 1

%o     for k in (1..n):

%o         if gcd(n, k) == 1: r = smod(r*k, n)

%o     return r

%o [A103131(n) for n in (1..102)]  # _Peter Luschny_, Oct 20 2012

%o (PARI)

%o 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.

%o A103131(n) = if(n<=2,n-1,(-1)^A211487(n)); \\ _Antti Karttunen_, Aug 22 2017

%Y Cf. A001783, A160377, A211487, A216919.

%K sign

%O 1,1

%A _Eric W. Weisstein_, Jan 23 2005

%E Definition rewritten by _Max Alekseyev_, May 26 2009

%E New name from _Peter Luschny_, Oct 20 2012

%E a(2) set to 1 by _Peter Luschny_, May 25 2017