login
Least modulus with 2^n square roots of 1.
8

%I #28 Oct 19 2021 11:14:24

%S 1,3,8,24,120,840,9240,120120,2042040,38798760,892371480,25878772920,

%T 802241960520,29682952539240,1217001054108840,52331045326680120,

%U 2459559130353965640,130356633908760178920,7691041400616850556280

%N Least modulus with 2^n square roots of 1.

%C The number of square roots of 1 in any modulus is a power of 2.

%C Another way of expressing the same: These are also the record setting values of m for the number of solutions to "m*k+1 is a square", for some k, 0<=k<=m. There is 1 solution for a(0)=m=1, and for m = a(n), n>0, there is the first occurrence of 2^n solutions. Compare with A006278. - _Richard R. Forberg_, Mar 18 2016

%C Also a(n) is the least k such that the proportion of squares in a reduced residue system modulo n is 1/2^n, i.e. A046073(k)/A000010(k) = 1/2^n. - _Jianing Song_, Nov 12 2019

%C From _Jianing Song_, Oct 18 2021: (Start)

%C a(n) is the smallest k such that rank((Z/kZ)*) = n. The rank of a finitely generated group rank(G) is defined to be the size of the minimal generating sets of G. In particular, rank((Z/kZ)*) = 0 if k <= 2 and A046072(k) otherwise.

%C The number of coprime squares modulo a(n) is given by A046073(a(n)) = A323739(n-1) for n >= 2. (End)

%H Harvey P. Dale, <a href="/A102476/b102476.txt">Table of n, a(n) for n = 0..351</a>

%F a(n) = 4(prime(n-1))# = 4*A002110(n-1) for n >= 2. Least k with A060594(k) = 2^n.

%e a(3) = 24 because 24 is the least modulus with 2^3 square roots of 1, namely 1,5,7,11,13,17,19,23.

%t {1, 3}~Join~Table[4 Product[Prime[k], {k, n}], {n, 17}] (* _Michael De Vlieger_, Mar 27 2016 *)

%t nxt[{a_, p_}] := {a*NextPrime[p], NextPrime[p]}; Join[{1,3},NestList[nxt,{8,2},20][[All,1]]] (* or *) Join[{1,3},4*FoldList[ Times, Prime[ Range[ 21]]]](* _Harvey P. Dale_, Dec 18 2016 *)

%o (PARI) a(n) = if(n<=1, [1,3][n+1], 4*factorback(primes(n-1))) \\ _Jianing Song_, Oct 19 2021, following _David A. Corneth_'s program for A002110

%Y Cf. A060594, A002110, A006278, A046072, A046073, A272590, A323739.

%K easy,nonn

%O 0,2

%A _David W. Wilson_, Jan 10 2005