cp's OEIS Frontend

A001783 n-phi-torial, or phi-torial of n: Product k, 1 <= k <= n, k relatively prime to n.

%I A001783 M0921 N0346 #114 Jul 02 2025 16:01:54
%S A001783 1,1,2,3,24,5,720,105,2240,189,3628800,385,479001600,19305,896896,
%T A001783 2027025,20922789888000,85085,6402373705728000,8729721,47297536000,
%U A001783 1249937325,1124000727777607680000,37182145,41363226782215962624,608142583125,1524503639859200000
%N A001783 n-phi-torial, or phi-torial of n: Product k, 1 <= k <= n, k relatively prime to n.
%C A001783 In other words, a(1) = 1 and for n >= 2, a(n) = product of the phi(n) numbers < n and relatively prime to n.
%C A001783 From Gauss's generalization of Wilson's theorem (see Weisstein link) it follows that, for n>1, a(n) == -1 (mod n) if and only if there exists a primitive root modulo n (cf. the Hardy and Wright reference, Theorem 129. p. 102). - _Vladimir Shevelev_, May 11 2012
%C A001783 Islam & Manzoor prove that a(n) is an injection for n > 1, see links. In other words, if a(m) = a(n), and min(m, n) > 1, then m = n. - _Muhammed Hedayet_, May 25 2016
%C A001783 Cosgrave & Dilcher propose the name Gauss factorial. Indeed the sequence is the special case N = n of the Gauss factorial N_n! = Product_{1<=j<=N, gcd(j, n)=1} j (see A216919). - _Peter Luschny_, Feb 07 2018
%D A001783 G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, Fifth ed., Clarendon Press, Oxford, 2003, Theorem 129, p. 102.
%D A001783 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D A001783 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A001783 T. D. Noe, <a href="/A001783/b001783.txt">Table of n, a(n) for n = 1..200</a>
%H A001783 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 A001783 J. B. Cosgrave and K. Dilcher, <a href="http://dx.doi.org/10.1142/S179304211100396X"> The multiplicative orders of certain Gauss factorials</a>, Intl. J. Number Theory 7 (1) (2011) 145-171.
%H A001783 S. W. Golomb and William Small, <a href="http://www.jstor.org/stable/2306745">Problem E1045</a>, Amer. Math. Monthly, 60 (1953), 422.
%H A001783 Muhammed H. Islam and Shahriar Manzoor, <a href="https://www.researchgate.net/publication/303459783">φ1 and phitorial are injections, for any positive integer N, where N > 1</a>
%H A001783 Laszlo Toth, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL14/Toth/toth9.html">Weighted gcd-sum functions</a>, J. Integer Sequences, 14 (2011), Article 11.7.7
%H A001783 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/WilsonsTheorem.html">Wilson's Theorem</a>
%F A001783 a(n) = n^phi(n)*Product_{d|n} (d!/d^d)^mu(n/d); phi=A000010 is the Euler totient function and mu=A008683 the Moebius function (Tom M. Apostol, Introduction to Analytic Number Theory, New York 1984, p. 48). - _Franz Vrabec_, Jul 08 2005
%F A001783 a(n) = n!/A066570(n). - _R. J. Mathar_, Mar 10 2011
%F A001783 A001221(a(n)) = A000720(n) - A001221(n) = A048865(n).
%F A001783 A006530(a(n)) = A136548(n). - _Enrique Pérez Herrero_, Jul 23 2011
%F A001783 a(n) = A124441(n)*A124442(n). - _M. F. Hasler_, Jul 23 2011
%F A001783 a(n) == (-1)^A211487(n) (mod n). - _Vladimir Shevelev_, May 13 2012
%F A001783 a(n) = A250269(n) / A193679(n). - _Daniel Suteu_, Apr 05 2021
%p A001783 A001783 := proc(n) local i,t1; t1 := 1; for i from 1 to n do if gcd(i,n)=1 then t1 := t1*i; fi; od; t1; end;
%p A001783 A001783 := proc(n) local i; mul(i,i=select(k->igcd(n,k)=1,[$1..n])) end; # _Peter Luschny_, Oct 30 2010
%t A001783 A001783[n_]:=Times@@Select[Range[n],CoprimeQ[n,#]&];
%t A001783 Array[A001783,20] (* _Enrique Pérez Herrero_, Jul 23 2011 *)
%o A001783 (PARI) A001783(n)=prod(k=2,n-1,k^(gcd(k,n)==1))  \\ _M. F. Hasler_, Jul 23 2011
%o A001783 (PARI) a(n)=my(f=factor(n),t=n^eulerphi(f)); fordiv(f,d, t*=(d!/d^d)^moebius(n/d)); t \\ _Charles R Greathouse IV_, Nov 05 2015
%o A001783 (Haskell)
%o A001783 a001783 = product . a038566_row
%o A001783 -- _Reinhard Zumkeller_, Mar 04 2012, Aug 26 2011
%o A001783 (Sage)
%o A001783 def Gauss_factorial(N, n): return mul(j for j in (1..N) if gcd(j, n) == 1)
%o A001783 def A001783(n): return Gauss_factorial(n, n)
%o A001783 [A001783(n) for n in (1..25)] # _Peter Luschny_, Oct 01 2012
%Y A001783 Cf. A023896, A066570, A038566, A124441.
%Y A001783 Main diagonal gives A216919.
%K A001783 nonn,nice,easy
%O A001783 1,3
%A A001783 _N. J. A. Sloane_
%E A001783 More terms from _James Sellers_, Dec 23 1999