A240370 Positive integers n such that every element in the ring of integers modulo n can be written as the sum of two squares modulo n.

1, 2, 3, 5, 6, 7, 10, 11, 13, 14, 15, 17, 19, 21, 22, 23, 25, 26, 29, 30, 31, 33, 34, 35, 37, 38, 39, 41, 42, 43, 46, 47, 50, 51, 53, 55, 57, 58, 59, 61, 62, 65, 66, 67, 69, 70, 71, 73, 74, 75, 77, 78, 79, 82, 83, 85, 86, 87, 89, 91, 93, 94, 95, 97, 101, 102, 103, 105, 106, 107, 109, 110, 111, 113, 114, 115, 118, 119, 122, 123, 125, 127, 129, 130, 131, 133, 134, 137, 138, 139, 141, 142, 143, 145, 146, 149, 150, 151, 154, 155, 157, 158, 159, 161, 163, 165, 166, 167, 169

Offset: 1

Author

Charles R Greathouse IV, Apr 04 2014

Keywords

• nonn

Comments

Numbers n such that, if p^2 divides n for any prime p, then p = 1 mod 4.

Equivalently, squarefree numbers times A004613.

Thus, numbers k such that A065338(A057521(k)) = 1. - Antti Karttunen, Jun 21 2014

Different from A193304: terms 169, 289, 338, 507, 578, 841, 845, 867, ... are here but not in A193304. - Michel Marcus, Jun 20 2014

The asymptotic density of this sequence is 3/(8*K^2) = (3/4) * A243379 = 0.64208..., where K is the Landau-Ramanujan constant (A064533). - Amiram Eldar, Dec 19 2020

Examples

			In Z_7, 0^2 + 0^2 = 0, 1^2 + 0^2 = 1, 1^2 + 1^2 = 2, 3^2 + 1^2 = 3, 2^2 + 0^2 = 4, 2^2 + 1^2 = 5, 3^2 + 2^2 = 6. Therefore 7 is in the sequence.
In Z_8, there is no way to express 3 as a sum of two squares. Therefore 8 is not in the sequence.
		

Links

• Antti Karttunen, Table of n, a(n) for n = 1..10000
• Joshua Harrington, Lenny Jones, and Alicia Lamarche, Representing Integers as the Sum of Two Squares in the Ring Z_n, arXiv:1404.0187 [math.NT], Apr 01 2014 and, J. Int. Seq. 17 (2014) # 14.7.4.

Crossrefs

The subsequence A240109 is a version not allowing 0.

Different from A193304.

Complement of A053443. Subsequence of A192450.

Cf. A004613, A057521, A064533, A065338, A243379.

Programs

Mathematica

rad[n_] := Times @@ First /@ FactorInteger[n];
a57521[n_] := n/Denominator[n/rad[n]^2];
a65338[n_] := a65338[n] = If[n==1, 1, Mod[p = FactorInteger[n][[1, 1]], 4]* a65338[n/p]];
Select[Range[200], a65338[a57521[#]] == 1&] (* Jean-François Alcover, Sep 22 2018, after Antti Karttunen *)
Select[Range[200], AllTrue[FactorInteger[#], Mod[First[#1], 4] == 1 || Last[#1] == 1 &] &] (* Amiram Eldar, Dec 19 2020 *)

PARI

is(n)=my(f=factor(n)); for(i=1,#f~,if(f[i,2]>1 && f[i,1]%4>1, return(0))); 1

PARI

isok(n) = { if (n < 2, return (0)); if ((n % 4) == 0, return (0)); forprime(q = 2, n, if (((q % 4) == 3) && ((n % q) == 0) && ((n % q^2) == 0), return (0)); ); return (1); } \\ Michel Marcus, Jun 08 2014

Scheme

;; With Antti Karttunen's IntSeq-library.
(define A240370 (MATCHING-POS 1 1 (lambda (k) (= 1 (A065338 (A057521 k))))))
;; Antti Karttunen, Jun 21 2014