cp's OEIS Frontend

A302099 Decompose the multiplicative group of integers modulo N as a product of cyclic groups C_{k_1} x C_{k_2} x ... x C_{k_m}, where k_i divides k_j for i < j, then a(n) is the smallest N such that the product contains a copy of C_{2n}.

%I A302099 #50 Mar 23 2021 07:19:56
%S A302099 3,5,7,32,11,13,1247,17,19,25,23,224,4187,29,31,128,14111,37,43739,41,
%T A302099 43,115,47,119,15251,53,81,928,59,61,116003,256,67,70555,71,73,33227,
%U A302099 174269,79,187,83,203,74563,89,209,235,186497,97,67571,101,103
%N A302099 Decompose the multiplicative group of integers modulo N as a product of cyclic groups C_{k_1} x C_{k_2} x ... x C_{k_m}, where k_i divides k_j for i < j, then a(n) is the smallest N such that the product contains a copy of C_{2n}.
%C A302099 a(n) exists for all n: by Dirichlet's theorem on arithmetic progressions, there must exist two primes with the form 2a*n + 1 and 2b*n + 1 where at least one of a,b is coprime to 2n, then the multiplicative group of integers modulo (2a*n + 1)(2b*n + 1) is isomorphic to C_{2*n} x C_{2ab*n}.
%C A302099 Factorizations of a(n) where 2n is not a term in A002174: a(7) = 29*43, a(13) = 53*79, a(17) = 103*137, a(19) = 191*229, a(25) = 101*151, a(31) = 311*373, a(34) = 5*103*137, a(37) = 149*223, a(38) = 229*761, a(43) = 173*431, a(47) = 283*659, a(49) = 7^3*197. - _Jianing Song_, Apr 29 2018 [Corrected on Sep 15 2018]
%C A302099 It may appear that for odd n, A046072(a(n)) = 1 or 2, but this is not generally true. The smallest counterexample is a(85) = 1542013, as the multiplicative group of integers modulo 1542013 is isomorphic to C_2 x C_170 x C_4080. - _Jianing Song_, Sep 15 2018
%H A302099 Jianing Song, <a href="/A302099/b302099.txt">Table of n, a(n) for n = 1..200</a>
%H A302099 Jianing Song, <a href="/A302099/a302099.txt">Group structure of the multiplicative group of integers modulo a(1) to a(200)</a>
%H A302099 Jianing Song, <a href="/A302099/a302099_1.txt">Factorizations of a(1) to a(200)</a>
%H A302099 Wikipedia, <a href="https://en.wikipedia.org/wiki/Multiplicative_group_of_integers_modulo_n">Multiplicative group of integers modulo n</a>
%e A302099 For n = 7 the multiplicative group of integers modulo 1247 is isomorphic to C_14 x C_84, and 1247 is the smallest number that contains a copy of C_14 in the product of cyclic groups, so a(7) = 1247.
%e A302099 For n = 34 the multiplicative group of integers modulo 70555 is isomorphic to C_2 x C_68 x C_408, and 70555 is the smallest number that contains a copy of C_68 in the product of cyclic groups, so a(34) = 70555. - _Jianing Song_, Sep 15 2018
%o A302099 (PARI) a(n)=my(i=3, Z=[2]); while(prod(j=1, #Z, 1-(Z[j]==2*n)), i++&&Z=znstar(i)[2]); i \\ _Jianing Song_, Sep 15 2018
%Y A302099 Cf. A002174, A002322, A002396.
%K A302099 nonn
%O A302099 1,1
%A A302099 _Jianing Song_, Apr 01 2018
%E A302099 Some terms corrected by _Jianing Song_, Apr 29 2018
%E A302099 Some terms corrected by _Jianing Song_, Sep 15 2018