login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

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

%I #126 Nov 19 2024 01:04:47

%S 1,2,5,10,13,17,25,26,29,34,37,41,50,53,58,61,65,73,74,82,85,89,97,

%T 101,106,109,113,122,125,130,137,145,146,149,157,169,170,173,178,181,

%U 185,193,194,197,202,205,218,221,226,229,233,241,250,257,265,269,274,277,281,289

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

%C 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

%C 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]

%C If a(n) is a term of this sequence, then so too are all of its divisors (Euler). - _Ant King_, Oct 11 2010

%C From _Richard R. Forberg_, Mar 21 2016: (Start)

%C 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.

%C Record setting values for the number of solutions (i.e., the next higher k values), occur at values for a(n) given by A006278.

%C A224450 and A224770 give a(n) values with exactly one and exactly two solutions, respectively, primitively representing integers as x^2 + y^2.

%C 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)

%C 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

%C 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

%C 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

%C 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

%C 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

%D B. C. Berndt & R. A. Rankin, Ramanujan: Letters and Commentary, see p. 176; AMS Providence RI 1995.

%D J. W. S. Cassels, Rational Quadratic Forms, Cambridge, 1978.

%D Leonard Eugene Dickson, History of the Theory Of Numbers, Volume II: Diophantine Analysis, Chelsea Publishing Company, 1992, pp.230-242.

%D 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).

%D G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, 5th ed., Oxford Univ. Press, 1979, Ch. 20.2-3.

%H T. D. Noe, <a href="/A008784/b008784.txt">Table of n, a(n) for n = 1..1000</a>

%H J.-P. Allouche and F. M. Dekking, <a href="https://arxiv.org/abs/1809.03424">Generalized Beatty sequences and complementary triples</a>, arXiv:1809.03424 [math.NT], 2018.

%H British Mathematical Olympiad, <a href="https://bmos.ukmt.org.uk/home/bmo-1985.pdf">1985 - Problem 6</a>.

%H Édouard Lucas, <a href="http://www.numdam.org/item/?id=NAM_1878_2_17__129_1">Théorème sur la géométrie des quinconces</a>, Nouvelles annales de mathématiques : journal des candidats aux écoles polytechnique et normale, Série 2, Tome 17 (1878), p. 129-130.

%H P. Cho-Ho Lam, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL18/Lam/lam2.html">Representation of integers using a^2+b^2-dc^2</a>, J. Int. Seq. 18 (2015) 15.8.6, Theorems 2 and 3.

%H Richard J. Mathar, <a href="https://arxiv.org/abs/1703.01677">Construction of Bhaskara pairs</a>, arXiv:1703.01677 [math.NT], 2017.

%H N. J. A. Sloane et al., <a href="https://oeis.org/wiki/Binary_Quadratic_Forms_and_OEIS">Binary Quadratic Forms and OEIS</a> (Index to related sequences, programs, references).

%H <a href="/index/O#Olympiads">Index to sequences related to Olympiads</a>.

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

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

%t 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_ *)

%o (PARI) 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

%o (PARI) 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

%o (PARI) for(n=1,300,if(issquare(Mod(-1, n)),print1(n,", "))); \\ _Joerg Arndt_, Apr 27 2020

%o (Haskell)

%o import Data.List.Ordered (union)

%o a008784 n = a008784_list !! (n-1)

%o a008784_list = 1 : 2 : union a004613_list (map (* 2) a004613_list)

%o -- _Reinhard Zumkeller_, Oct 25 2015

%Y Apart from the first term, a subsequence of A000404.

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

%K nonn

%O 1,2

%A _N. J. A. Sloane_, _Olivier Gérard_

%E Checked by _T. D. Noe_, Apr 19 2007