A316506 a(n) is the rank of the multiplicative group of Gaussian integers modulo n.

0, 1, 1, 2, 2, 2, 1, 3, 2, 3, 1, 3, 2, 2, 3, 3, 2, 2, 1, 4, 2, 2, 1, 4, 2, 3, 2, 3, 2, 4, 1, 3, 2, 3, 3, 3, 2, 2, 3, 5, 2, 3, 1, 3, 3, 2, 1, 4, 2, 3, 3, 4, 2, 2, 3, 4, 2, 3, 1, 5, 2, 2, 3, 3, 4, 3, 1, 4, 2, 4, 1, 4, 2, 3, 3, 3, 2, 4, 1, 5, 2, 3, 1, 4, 4, 2, 3

Offset: 1

Author

Jianing Song, Jul 05 2018

Keywords

• nonn

Comments

The rank of a finitely generated group rank(G) is defined to be the size of the minimal generating sets of G.

Let p be an odd prime and (Z[i]/nZ[i])* be the multiplicative group of Gaussian integers modulo n, then: (Z[i]/p^e*Z[i])* = (C_((p-1)*p^(e-1)))^2 if p == 1 (mod 4); C_(p^(e-1)) X C_(p^(e-1)*(p^2-1)) if p == 3 (mod 4). (Z[i]/2Z[i])* = C_2, (Z[i]/2^e*Z[i])* = C_4 X C_(2^(e-2)) X C_(2^(e-1)) for e >= 2. If n = Product_{i=1..k} (p_i)^(e_i), then (Z[i]/nZ[i])* = (Z[i]/(p_1)^(e_1)*Z[i])* X (Z[i]/(p_2)^(e_2)*Z[i])* X ... X (Z[i]/(p_k)^(e_k)*Z[i])*.

The order of (Z[i]/nZ[i])* is A079458(n) and the exponent of it is A227334(n).

{a(n)} is not additive: (Z[i]/2Z[i])* = C_2, (Z[i]/9Z[i])* = C_3 X C_24, so (Z[i]/18Z[i])* = C_6 X C_24, a(18) < a(2) + a(9). The same problem occurs for a(36), a(54) and a(72) and so on. But note that (Z[i]/63Z[i])* = C_3 X C_24 X C_48 and a(63) = a(7) + a(9).

A079458(n)/A227334(n) is always an integer, and is 1 if and only if (Z[i]/nZ[i])* is cyclic, that is, rank((Z[i]/nZ[i])*) = a(n) = 0 or 1, and n has a primitive root in (Z[i]/nZ[i])*. a(n) = 1 if and only if n = 2 or a prime congruent to 3 mod 4. - Jianing Song, Jan 08 2019

From Jianing Song, Oct 03 2022: (Start)

More generally, let pi be a prime element of Z[i] of norm p or p^2 for prime p, then:

- for p == 1 (mod 4), (Z[i]/(pi^e)Z[i])* = C_((p-1)*p^(e-1));

- for p == 3 (mod 4), (Z[i]/(pi^e)Z[i])* = C_(p^(e-1)) X C_(p^(e-1)*(p^2-1));

- for p = 2, (Z[i]/(pi^e)Z[i])* = C_1 for e = 1, C_2 for e = 2, C_4 X C_(2^floor((e-3)/2)) X C_(2^ceiling((e-3)/2)) for e >= 3.

For a more general result see my link below. (End)

Examples

			(Z[i]/1Z[i])* = C_1 (has rank 0);
(Z[i]/2Z[i])* = C_2 (has rank 1);
(Z[i]/3Z[i])* = C_8 (has rank 1);
(Z[i]/4Z[i])* = C_2 X C_4 (has rank 2);
(Z[i]/5Z[i])* = C_4 X C_4 (has rank 2);
(Z[i]/6Z[i])* = C_2 X C_8 (has rank 2);
(Z[i]/7Z[i])* = C_48 (has rank 1);
(Z[i]/8Z[i])* = C_2 X C_4 X C_4 (has rank 3);
(Z[i]/9Z[i])* = C_3 X C_24 (has rank 2);
(Z[i]/10Z[i])* = C_2 X C_4 X C_4 (has rank 3).
		

Links

• Jianing Song, Table of n, a(n) for n = 1..10000
• Jianing Song, Structure of (R/P^e)* for R the ring of integers of a quadratic field and P a prime ideal of R

Crossrefs

Cf. A046072, A079458, A227334, A302254.

Equivalent in the ring of Eisenstein integers: A319447.

Programs

PARI

rad(n) = factorback(factorint(n)[, 1]);
grad(n)=
{
    my(r=1, f=factor(n));
    for(j=1, #f[, 1], my(p=f[j, 1], e=f[j, 2]);
        if(p==2&e==1, r*=2);
        if(p==2&e==2, r*=4);
        if(p==2&e>=3, r*=8);
        if(p%4==1, r*=(rad(p-1))^2);
        if(p%4==3&e==1, r*=rad(p^2-1));
        if(p%4==3&e>=2, r*=p^2*rad(p^2-1));
    );
    return(r);
}
a(n)=if(n>1, vecmax(factor(grad(n))[, 2]), 0);

Formula

Let p be an odd prime, then: a(p^e) = 2 if p == 1 (mod 4) or p == 3 (mod 4), e >= 2; a(p) = 1 if p == 3 (mod 4). a(2) = 1, a(4) = 2, a(2^e) = 3 for e >= 3.