A394579 Moduli m in which a multiplicative square-root function exists over the ring of integers Z_m.

2, 3, 4, 6, 7, 9, 11, 12, 14, 18, 19, 21, 22, 23, 28, 31, 33, 36, 38, 42, 43, 44, 46, 47, 49, 57, 59, 62, 63, 66, 67, 69, 71, 76, 77, 79, 83, 84, 86, 92, 93, 94, 98, 99, 103, 107, 114, 118, 121, 124, 126, 127, 129, 131, 132, 133, 134, 138, 139, 141, 142, 147, 151, 154, 158, 161, 163

Offset

1,1

Comments

By a multiplicative square-root function over Z_m we mean a function sqrt(x) from the set of squares of Z_m; that is, from S={x^2:x in Z_m} to Z_m, such that sqrt(x)^2 = x and sqrt(x*y) = sqrt(x)*sqrt(y) for every x,y in S. It can be shown that if such a function exists over Z_m, then it is unique.

Let m>1 be an integer. Then there exists a multiplicative square-root function over Z_m if and only if either m=2 or m=4 or the prime decomposition of m is of the form m=2^{a_0}*p_1^{a_1}*...*p_s^{a_s}, where a_0 in {0,1,2}, s>=1 and p_i=3 mod 4, a_i in {1,2} for each 1<=i<=s.

Links

Table of n, a(n) for n=1..67.

Boaz Cohen, Multiplicative n-th Root Functions over Finite Semigroups, Groups, Fields and Commutative Rings, Mathematical Reports, 26(3-4), pp. 219-250.

Example

If m=18, then S={0,1,4,7,9,10,13,16} and the function sqrt:S-->Z_18 defined by sqrt(0)=0, sqrt(1)=1, sqrt(4)=16, sqrt(7)=13, sqrt(9)=9, sqrt(10)=10, sqrt(13)=7, sqrt(16)=4 is multiplicative. For instance, sqrt(4*7) = sqrt(10) = 10 = 16*13 = sqrt(4)*sqrt(7).

Maple

generate_m := proc(limit::integer)
    local m, fact, p_list, p, a, a0, s, i, results, is_valid;
    results := {2, 4}; # Start with the explicit cases
    for m from 1 to limit do
        fact := ifactors(m)[2];
        a0 := 0;
        p_list := [];
        for i from 1 to nops(fact) do
            p := fact[i][1];
            a := fact[i][2];
            if p = 2 then
                a0 := a;
            else
                p_list := [op(p_list), [p, a]];
            fi;
        od;
        s := nops(p_list);
        if a0 <= 2 and s >= 1 then
            is_valid := true;
            for i from 1 to s do
                p := p_list[i][1];
                a := p_list[i][2];
                if not (p mod 4 = 3 and (a = 1 or a = 2)) then
                    is_valid := false;
                    break;
                fi;
            od;
            if is_valid then
                results := results union {m};
            fi;
        fi;
    od;
    return sort(convert(results, list));
end proc:
generate_m(100);

Prog

(PARI) isok(m) = if ((m==2) || (m==4), return(1)); my(f=factor(m), odd=m%2, s=if(odd, 1, 2)); if (!odd, if (f[1, 2]>2, return(0))); for(i=s, #f~, if ((f[i, 1] % 4) != 3, return(0)); if ((f[i, 2]<1) || (f[i, 2]>2), return(0))); 1; \\ Michel Marcus, Apr 06 2026

Crossrefs

Cf. A022544.

Sequence in context: A026468 A263015 A056176 * A379754 A143831 A087072

Adjacent sequences: A394576 A394577 A394578 * A394580 A394581 A394582

Keyword

nonn

Author

Boaz Cohen, Mar 25 2026

Status

approved