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}.

3, 5, 7, 32, 11, 13, 1247, 17, 19, 25, 23, 224, 4187, 29, 31, 128, 14111, 37, 43739, 41, 43, 115, 47, 119, 15251, 53, 81, 928, 59, 61, 116003, 256, 67, 70555, 71, 73, 33227, 174269, 79, 187, 83, 203, 74563, 89, 209, 235, 186497, 97, 67571, 101, 103

Offset: 1

Author

Jianing Song, Apr 01 2018

Keywords

• nonn

Comments

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}.

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]

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

Examples

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

Links

• Jianing Song, Table of n, a(n) for n = 1..200
• Jianing Song, Group structure of the multiplicative group of integers modulo a(1) to a(200)
• Jianing Song, Factorizations of a(1) to a(200)
• Wikipedia, Multiplicative group of integers modulo n

Crossrefs

Cf. A002174, A002322, A002396.

Programs

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

Extensions

Some terms corrected by Jianing Song, Apr 29 2018

Some terms corrected by Jianing Song, Sep 15 2018