cp's OEIS Frontend

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

%I A103131 #40 Feb 16 2025 08:32:56
%S A103131 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 A103131 -1,1,-1,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 A103131 -1,1,1,1,-1,-1,1,-1,-1,1,1,1,1,-1,1,1,1,-1,1,-1,-1,1,1,1,1,-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 A103131 The product of the residues in [1,n] relatively prime to n, taken modulo n.
%C A103131 Old name was: Minimal residue (in absolute value) of A001783(n) (mod n).
%C A103131 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 A103131 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 A103131 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 A103131 Antti Karttunen, <a href="/A103131/b103131.txt">Table of n, a(n) for n = 1..16385</a>
%H A103131 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 A103131 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/Wilsonstheorem.html">Wilson's theorem</a>
%F A103131 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 A103131 a(n) = Gauss_factorial(n, n) modulo n. (Definition of the Gauss factorial in A216919.) - _Peter Luschny_, Oct 20 2012
%F A103131 For n > 2, a(n) = (-1)^A211487(n). (See _Max Alekseyev_'s formula above.) - _Antti Karttunen_, Aug 22 2017
%e A103131 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 A103131 := proc(n) local k, r; r := 1;
%p A103131 for k to n do if igcd(n,k) = 1 then r := mods(r*k, n) fi od;
%p A103131 r end: seq(A103131(i), i=1..102);   # _Peter Luschny_, Oct 20 2012
%t A103131 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 A103131 (Sage)
%o A103131 def A103131(n):
%o A103131     def smod(a,n): return a-n*ceil(a/n-1/2) if n != 0 else a
%o A103131     r = 1
%o A103131     for k in (1..n):
%o A103131         if gcd(n, k) == 1: r = smod(r*k, n)
%o A103131     return r
%o A103131 [A103131(n) for n in (1..102)]  # _Peter Luschny_, Oct 20 2012
%o A103131 (PARI)
%o A103131 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 A103131(n) = if(n<=2,n-1,(-1)^A211487(n)); \\ _Antti Karttunen_, Aug 22 2017
%Y A103131 Cf. A001783, A160377, A211487, A216919.
%K A103131 sign
%O A103131 1,1
%A A103131 _Eric W. Weisstein_, Jan 23 2005
%E A103131 Definition rewritten by _Max Alekseyev_, May 26 2009
%E A103131 New name from _Peter Luschny_, Oct 20 2012
%E A103131 a(2) set to 1 by _Peter Luschny_, May 25 2017