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,1

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

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

Example

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

Prog

(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

Crossrefs

Cf. A002174, A002322, A002396.

Sequence in context: A162714 A359044 A002396 * A029508 A256935 A095714

Adjacent sequences: A302096 A302097 A302098 * A302100 A302101 A302102

Keyword

nonn

Author

Jianing Song, Apr 01 2018

Extensions

Some terms corrected by Jianing Song, Apr 29 2018

Some terms corrected by Jianing Song, Sep 15 2018

Status

approved