A329589 Odd integers which are not a positive power of a single prime and have at least one prime divisor 1 (mod 4).

15, 35, 39, 45, 51, 55, 65, 75, 85, 87, 91, 95, 105, 111, 115, 117, 119, 123, 135, 143, 145, 153, 155, 159, 165, 175, 183, 185, 187, 195, 203, 205, 215, 219, 221, 225, 235, 245, 247, 255, 259, 261, 265, 267, 273, 275, 285, 287, 291, 295, 299, 303, 305, 315, 319, 323, 325, 327, 333, 335, 339, 345

Offset: 1

Author

Wolfdieter Lang, Dec 14 2019

Keywords

• nonn
• easy

Comments

This sequence is a proper subsequence of A257591 where also odd numbers, not a prime power, and 1 (mod 4) divisors involving only primes congruent to 3 modulo 4 are included, like 63, 99, 147, 171, 189, ... .

This sequence gives all odd moduli m that have solutions of the complex congruence z^2 = +1 (mod m), with z = a + b*i, where a, b are positive integers (nonvanishing a*b case). For a proof one can use the formula for the number of solutions of this congruence for a*b vanishing, given in A329586 without powers of 2 (e2 = 0) and subtract it from the formula for the number of all representative solutions with modulus m >= 1 which is S(m) = 1 if m = 1, and S(m) = 2^(2*r1(m) + r3(m)), with r1(m) and r3(m) the number of distinct primes 1 (mod 4) (A002144) and 3 (mod 4) (A002145), respectively. This becomes the number of representative solutions 2^(r1(m) + r3(m))*(2^(r1(m)) - 1) - delta(r3(m), 0)*2^(r1(m))), with the Kronecker symbol. This shows that for odd modulus m >= 3 and nonvanishing a*b there is no solution if r1(m) = 0 and r3 >= 1. Moduli which are powers of a single prime have only solutions with a or b vanishing.

See A329587 for all moduli m with solutions of z^2 = +1 (mod m), with z = a + b*i and nonvanishing a*b, where all even numbers >= 4 appear.

For the representative solutions of this congruence with a*b = 0 see A329585 for all positive moduli m.

For the representative solutions of this congruence for all m >= 1 see A227091.

Crossrefs

Cf. A002144, A002145, A257591, A329585, A329586, A329587, A227091.

Programs

Mathematica

Select[Range[3, 235, 2], And[! PrimePowerQ@ #, AnyTrue[FactorInteger[#][[All, 1]], Mod[#, 4] == 1 &]] &] (* Michael De Vlieger, Dec 14 2019 *)

PARI

isok(k) = if ((k%2) && !isprimepower(k), my(f=factor(k)); sum(i=1, #f~, (f[i,1] % 4) == 1) >= 1); \\ Michel Marcus, Sep 18 2023

Formula

See the name.

Extensions

More terms from Michel Marcus, Sep 18 2023