A046072 -id:A046072 - 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}.

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

Jianing Song, Apr 01 2018

nonn

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

			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

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

Cf. A002174, A002322, A002396.

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

Some terms corrected by Jianing Song, Apr 29 2018

Some terms corrected by Jianing Song, Sep 15 2018

A302109 Smallest integer N such that there are exactly n cyclic groups C_2 in the multiplicative group of integers modulo N when decomposed as a product of cyclic groups C_{k_1} x C_{k_2} x ... x C_{k_m}, and k_i divides k_j for i < j.

Original entry on oeis.org

1, 3, 8, 24, 840, 9240, 212520, 9988440, 589317960, 48913390680, 5233732802760, 874033378060920, 156451974672904680, 35514598250749362360, 8487988981929097604040, 2232341102247352669862520, 721046176025894912365593960, 51194278497838538777957171160

Offset: 0

Jianing Song, Apr 01 2018

nonn

a(n) exists for all n: by Dirichlet's theorem on arithmetic progressions, there exists primes of the form 2*c_1 + 1, 2*c_2 + 1, ..., 2*c_(n+1) + 1 where c_i are pairwise coprime odd numbers, then the multiplicative group of integers modulo (2*c_1 + 1)(2*c_2 + 1)*...*(2*c_(n+1) + 1) is isomorphic to (C_2)^n x C_(2*c_1*c_2*...*c_(n+1)).

Conjecture: (a) a(j) is divisible by a(i) if i < j; (b) a(n)/4 is squarefree for all n.

			The multiplicative group of integers modulo 212520 is isomorphic to (C_2)^6 x C_660 and 212520 is the smallest number N such that the multiplicative group of integers modulo N contains six C_2 as the product of cyclic groups, so a(6) = 212520.
a(17) = 2^3 * 3 * 5 * 7 * 11 * 17 * 19 * 23 * 47 * 59 * 71 * 83 * 107 * 167 * 179 * 227 * 239 * 263, and the multiplicative group of integers modulo a(17) is isomorphic to (C_2)^17 x C_(4*3*5*7) x C_(16*9*5*7*11*17*23*29*41*53*83*113*131).

Jianing Song, Table of n, a(n) for n = 0..61 [This now agrees with the list of factorized terms. - _N. J. A. Sloane_, Jan 19 2019]
Jianing Song, Group structure of the multiplicative group of integers modulo a(0) to a(61)
Jianing Song, Factorizations of a(0) to a(61) [Corrected by _Jianing Song_, Jan 19 2019]

Cf. A046072.

A318909 a(n) = Product_{1<=x<=n, n|(x^2-1)} x.

Original entry on oeis.org

1, 1, 2, 3, 4, 5, 6, 105, 8, 9, 10, 385, 12, 13, 616, 945, 16, 17, 18, 1881, 2080, 21, 22, 37182145, 24, 25, 26, 5265, 28, 6061, 30, 7905, 7360, 33, 5916, 11305, 36, 37, 13300, 1384944561, 40, 15457, 42, 20769, 21736, 45, 46, 4087504225, 48, 49, 28000, 34425

Offset: 1

Jianing Song, Sep 05 2018

a(n) is the product of self-inverse elements in (Z/nZ)*, where (Z/nZ)* is the multiplicative group of integers modulo n.
For n >= 2, a(n) = n - 1 iff n is in A033948. For other n, a(n) == 1 (mod n). This can also be written as: a(n) == (-1)^A034380(n) == (-1)^(A060594(n)/2) (mod n) for n >= 3.
More generally, let P(k,n) = Product_{1<=x<=n, n|(x^k-1)} x, then P(k,n) == 1 (mod n) if k is odd or n is not in A033948, P(k,n) == -1 (mod n) otherwise. Equivalently, if A046072(n) > 1 then P(k,n) == 1 (mod n), otherwise P(k,n) == (-1)^((k+1)/2) (mod n).

			For n = 8, 1^2 == 3^2 == 5^2 == 7^2 == 1 (mod 8) so a(8) = 1*3*5*7 = 105.
For n = 12, 1^2 == 5^2 == 7^2 == 11^2 == 1 (mod 12) so a(12) = 1*5*7*11 = 385.

Robert Israel, Table of n, a(n) for n = 1..10000

Cf. A033948, A034380, A046072, A060594.

f:= proc(n) convert(map(t -> rhs(op(t)),[msolve(x^2=1,n)]),`*`) end proc:
f(1):= 1:
map(f, [$1..100]); # Robert Israel, Nov 05 2019

a(n) = prod(i=1, n, i^(Mod(i^2-1,n)==0))

A328415 Numbers k such that (Z/mZ)* = C_2 X C_(2k) has exactly one solution, where (Z/mZ)* is the multiplicative group of integers modulo m.

Original entry on oeis.org

4, 16, 27, 32, 64, 256, 512, 1024, 2048, 2187, 4096, 6561, 8192, 16384, 59049, 65536, 131072, 177147, 262144, 524288, 531441, 1048576, 1594323, 2097152, 4194304, 4782969, 8388608, 14348907, 16777216, 33554432, 67108864, 134217728, 268435456, 387420489, 536870912, 1073741824

Offset: 1

Jianing Song, Oct 14 2019

nonn

Numbers k being powers of 2 or 3 such that 2*k+1 is not prime.
Proof. If m is a solution to (Z/mZ)* = C_2 X C_(2k) such that m is odd, then 2*m is also a solution, and vice versa. So if there is only one solution to (Z/mZ)* = C_2 X C_(2k), m must be a multiple of 4. If 8 divides m and m has odd prime factors, or if m has at least two distinct odd prime factors, then A046072(m) >= 3, a contradiction. So m = 2^e, e >= 3 or m = 4*p^e, p odd prime and e >= 1. If m = 4*p^e and p >= 5, then (Z/(3*p^e)Z)* = (Z/mZ)*. So we have m = 2^e, e >= 3 or m = 4*3^e, e >= 1, then (Z/mZ)* = C_2 X C_(2*2^(e-3)) or (Z/mZ)* = C_2 X C_(2*3^(e-1)).
If k = 2^(e-3) > 1 and p = 2*k+1 is prime, then (Z/(3*p)Z)* = (Z/(2^e)Z)*; if k = 3^(e-1) > 1 and p = 2*k+1 is prime, then (Z/(3*p)Z)* = (Z/(4*3^e)Z)*; on the other hand, if k is a power of 2 or a power of 3 such that 2*k+1 is not prime, then (Z/mZ)* = C_2 X C_(2k) indeed has only one solution.

			The only solution to (Z/mZ)* = C_2 X C_54 is m = 324, so 54/2 = 27 is a term.

Wikipedia, Multiplicative group of integers modulo n

Cf. A328412.

select(i->!isprime(2*i+1), upto(10^9)) \\ See A006899 for the function upto(n)

A368042 Moduli k for which the number of quadratic residues mod k coprime to k is phi(k)/2^r for positive r = (phi(k)/lambda(k)) - x, x > 0, where lambda is Carmichael's function. Complement of A366935.

Original entry on oeis.org

2, 24, 40, 48, 56, 60, 63, 65, 72, 80, 84, 85, 88, 91, 96, 104, 105, 112, 117, 120, 126, 130, 132, 133, 136, 140, 144, 145, 152, 156, 160, 165, 168, 170, 171, 176, 180, 182, 184, 185, 189, 192, 195, 200, 204, 205, 208, 210, 216, 217

Offset: 1

Miles Englezou, Dec 09 2023

An empirical observation, verified for 2 <= k <= 10^5: The number of quadratic residues mod k coprime to k is |Q_k| = phi(k)/2^r, r = A046072(k) <= phi(k)/lambda(k). Up to 10^5, the equality holds for 37758 moduli, and the inequality holds for 62241.

			k = 2 is a term: |Q_2| = phi(2)/2^0 = 1, and r = 0 < phi(2)/lambda(2) = 1.

D. Shanks, Solved and Unsolved Problems in Number Theory, 4th ed. New York: Chelsea, 1993, page 95.

Cf. A366935, A000010, A002322, A046073, A034380, A033948, A046072.

isok(n) = my(z=znstar(n).cyc); #z < eulerphi(n)/lcm(z)

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Extensions

A302109 Smallest integer N such that there are exactly n cyclic groups C_2 in the multiplicative group of integers modulo N when decomposed as a product of cyclic groups C_{k_1} x C_{k_2} x ... x C_{k_m}, and k_i divides k_j for i < j.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A318909 a(n) = Product_{1<=x<=n, n|(x^2-1)} x.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

PARI

A328415 Numbers k such that (Z/mZ)* = C_2 X C_(2k) has exactly one solution, where (Z/mZ)* is the multiplicative group of integers modulo m.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

A368042 Moduli k for which the number of quadratic residues mod k coprime to k is phi(k)/2^r for positive r = (phi(k)/lambda(k)) - x, x > 0, where lambda is Carmichael's function. Complement of A366935.

Views

Author

Keywords

Comments

Examples

References

Crossrefs

Programs

PARI