A192450 -id:A192450 - cp's OEIS frontend

A008784 Numbers k such that sqrt(-1) mod k exists; or, numbers that are primitively represented by x^2 + y^2.

1, 2, 5, 10, 13, 17, 25, 26, 29, 34, 37, 41, 50, 53, 58, 61, 65, 73, 74, 82, 85, 89, 97, 101, 106, 109, 113, 122, 125, 130, 137, 145, 146, 149, 157, 169, 170, 173, 178, 181, 185, 193, 194, 197, 202, 205, 218, 221, 226, 229, 233, 241, 250, 257, 265, 269, 274, 277, 281, 289

Offset: 1

N. J. A. Sloane, Olivier Gérard

nonn

Numbers whose prime divisors are all congruent to 1 mod 4, with the exception of at most a single factor of 2. - Franklin T. Adams-Watters, Sep 07 2008
In appears that {a(n)} is the set of proper divisors of numbers of the form m^2+1. - Kaloyan Todorov (kaloyan.todorov(AT)gmail.com), Mar 25 2009 [This conjecture is correct. - Franklin T. Adams-Watters, Oct 07 2009]
If a(n) is a term of this sequence, then so too are all of its divisors (Euler). - Ant King, Oct 11 2010
From Richard R. Forberg, Mar 21 2016: (Start)
For a given a(n) > 2, there are 2^k solutions to sqrt(-1) mod n (for some k >= 1), and 2^(k-1) solutions primitively representing a(n) by x^2 + y^2.
Record setting values for the number of solutions (i.e., the next higher k values), occur at values for a(n) given by A006278.
A224450 and A224770 give a(n) values with exactly one and exactly two solutions, respectively, primitively representing integers as x^2 + y^2.
The 2^k different solutions for sqrt(-1) mod n can written as values for j, with j <= n, such that integers r = sqrt(n*j-1). However, the set of j values (listed from smallest to largest) transform into themselves symmetrically (i.e., largest to smallest) when the solutions are written as n-r. When the same 2^k solutions are written as r-j, it is clear that only 2^(k-1) distinct and independent solutions exist. (End)
Lucas uses the fact that there are no multiples of 3 in this sequence to prove that one cannot have an equilateral triangle on the points of a square lattice. - Michel Marcus, Apr 27 2020
For n > 1, terms are precisely the numbers such that there is at least one pair (m,k) where m + k = a(n), and m*k == 1 (mod a(n)), m > 0 and m <= k. - Torlach Rush, Oct 18 2020
A pair (s,t) such that s+t = a(n) and s*t == +1 (mod a(n)) as above is obtained from a square root of -1 (mod a(n)) for s and t = a(n)-s. - Joerg Arndt, Oct 24 2020
The Diophantine equation x^2 + y^2 = z^5 + z with gcd(x, y, z) = 1 has solutions iff z is a term of this sequence. See Gardiner reference, Olympiad links and A340129. - Bernard Schott, Jan 17 2021
Except for 1, numbers of the form a + b + 2*sqrt(a*b - 1) for positive integers a,b such that a*b-1 is a square. - Davide Rotondo, Nov 10 2024

B. C. Berndt & R. A. Rankin, Ramanujan: Letters and Commentary, see p. 176; AMS Providence RI 1995.
J. W. S. Cassels, Rational Quadratic Forms, Cambridge, 1978.
Leonard Eugene Dickson, History of the Theory Of Numbers, Volume II: Diophantine Analysis, Chelsea Publishing Company, 1992, pp.230-242.
A. Gardiner, The Mathematical Olympiad Handbook: An Introduction to Problem Solving, Oxford University Press, 1997, reprinted 2011, Problem 6 pp. 63 and 167-168 (1985).
G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, 5th ed., Oxford Univ. Press, 1979, Ch. 20.2-3.

T. D. Noe, Table of n, a(n) for n = 1..1000
J.-P. Allouche and F. M. Dekking, Generalized Beatty sequences and complementary triples, arXiv:1809.03424 [math.NT], 2018.
British Mathematical Olympiad, 1985 - Problem 6.
Édouard Lucas, Théorème sur la géométrie des quinconces, Nouvelles annales de mathématiques : journal des candidats aux écoles polytechnique et normale, Série 2, Tome 17 (1878), p. 129-130.
P. Cho-Ho Lam, Representation of integers using a^2+b^2-dc^2, J. Int. Seq. 18 (2015) 15.8.6, Theorems 2 and 3.
Richard J. Mathar, Construction of Bhaskara pairs, arXiv:1703.01677 [math.NT], 2017.
N. J. A. Sloane et al., Binary Quadratic Forms and OEIS (Index to related sequences, programs, references).
Index to sequences related to Olympiads.

Apart from the first term, a subsequence of A000404.

Cf. A001481, A022544, A020893, A037942, A034023, A057756, A076948, A045673, A004613, A340129, A192450 (complement).

import Data.List.Ordered (union)
a008784 n = a008784_list !! (n-1)
a008784_list = 1 : 2 : union a004613_list (map (* 2) a004613_list)
-- Reinhard Zumkeller, Oct 25 2015

with(numtheory); [seq(mroot(-1,2,p),p=1..300)];

data=Flatten[FindInstance[x^2+y^2==# && 0<=x<=# && 0<=y<=# && GCD[x,y]==1,{x,y},Integers]&/@Range[289],1]; x^2+y^2/.data//Union (* Ant King, Oct 11 2010 *)
Select[Range[289], And @@ (Mod[#, 4] == 1 & ) /@ (fi = FactorInteger[#]; If[fi[[1]] == {2, 1}, Rest[fi[[All, 1]]], fi[[All, 1]]])&] (* Jean-François Alcover, Jul 02 2012, after Franklin T. Adams-Watters *)

is(n)=if(n%2==0,if(n%4,n/=2,return(0)));n==1||vecmax(factor(n)[,1]%4)==1 \\ Charles R Greathouse IV, May 10 2012

list(lim)=my(v=List([1,2]),t); lim\=1; for(x=2,sqrtint(lim-1), t=x^2; for(y=0,min(x-1,sqrtint(lim-t)), if(gcd(x,y)==1, listput(v,t+y^2)))); Set(v) \\ Charles R Greathouse IV, Sep 06 2016

for(n=1,300,if(issquare(Mod(-1, n)),print1(n,", "))); \\ Joerg Arndt, Apr 27 2020

Checked by T. D. Noe, Apr 19 2007

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.

Original entry on oeis.org

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

Charles R Greathouse IV, Apr 04 2014

nonn

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

			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.

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.

The subsequence A240109 is a version not allowing 0.
Different from A193304.
Complement of A053443. Subsequence of A192450.
Cf. A004613, A057521, A064533, A065338, A243379.

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 *)

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

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

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

A334819 Largest quadratic nonresidue modulo n (with n >= 3).

Original entry on oeis.org

2, 3, 3, 5, 6, 7, 8, 8, 10, 11, 11, 13, 14, 15, 14, 17, 18, 19, 20, 21, 22, 23, 23, 24, 26, 27, 27, 29, 30, 31, 32, 31, 34, 35, 35, 37, 38, 39, 38, 41, 42, 43, 44, 45, 46, 47, 48, 48, 50, 51, 51, 53, 54, 55, 56, 56, 58, 59, 59, 61, 62, 63, 63, 65, 66, 67

Offset: 3

Peter Schorn, May 12 2020

The largest nonnegative integer less than n which is not a square modulo n.

If p is a prime congruent 3 modulo 4 then a(p) = p-1 since -1 is not a quadratic residue for such primes.

			The squares modulo 3 are 0 and 1. Therefore a(3) = 2. The nonsquares modulo 4 are 2 and 3 which makes a(4) = 3. Modulo 5 we have 0, 1 and 4 as squares giving a(5) = 3. 0, 1 and 4 are also the squares modulo 6 resulting in a(6) = 5. Since 10007 is a prime of the form 4*k + 3, a(10007) = 10006.

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

Cf. A020649, A047210 (the largest square modulo n), A192450 (a(n)=n-1).

f:= proc(n) local k;
  for k from n-1 by -1 do if numtheory:-msqrt(k,n)=FAIL then return k fi
  od
end proc:
map(f, [$3..100]); # Robert Israel, May 14 2020

a[n_] := Module[{r}, For[r = n-1, r >= 1, r--, If[!IntegerQ[Sqrt[Mod[r, n]] ], Return[r]]]];
a /@ Range[3, 100] (* Jean-François Alcover, Aug 15 2020 *)

a(n) = forstep(r = n - 1, 1, -1, if(!issquare(Mod(r, n)), return(r)))

cp's OEIS Frontend

A008784 Numbers k such that sqrt(-1) mod k exists; or, numbers that are primitively represented by x^2 + y^2.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI

PARI

Extensions

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Scheme

A334819 Largest quadratic nonresidue modulo n (with n >= 3).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI