A057756 -id:A057756 - 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

A002314 Minimal integer square root of -1 modulo p, where p is the n-th prime of the form 4k+1.

Original entry on oeis.org

2, 5, 4, 12, 6, 9, 23, 11, 27, 34, 22, 10, 33, 15, 37, 44, 28, 80, 19, 81, 14, 107, 89, 64, 16, 82, 60, 53, 138, 25, 114, 148, 136, 42, 104, 115, 63, 20, 143, 29, 179, 67, 109, 48, 208, 235, 52, 118, 86, 24, 77, 125, 35, 194, 154, 149, 106, 58, 26, 135, 96, 353, 87, 39

Offset: 1

N. J. A. Sloane

nonn

In other words, if p is the n-th prime == 1 (mod 4), a(n) is the smallest positive integer k such that k^2 + 1 == 0 (mod p).
The 4th roots of unity mod p, where p = n-th prime == 1 (mod 4), are +1, -1, a(n) and p-a(n).
Related to Stormer numbers.
Comment from Igor Shparlinski, Mar 12 2007 (writing to the Number Theory List): Results about the distribution of roots (for arbitrary quadratic polynomials) are given by W. Duke, J. B. Friedlander and H. Iwaniec and A. Toth.
Comment from Emmanuel Kowalski, Mar 12 2007 (writing to the Number Theory List): It is known (Duke, Friedlander, Iwaniec, Annals of Math. 141 (1995)) that the fractional part of a(n)/p(n) is equidistributed in [0,1/2] for p(n)From Artur Jasinski, Dec 10 2008: (Start)
If we take the four numbers 1, A002314(n), A152676(n), and A152680(n), then their multiplication table modulo A002144(n) is isomorphic to the Latin square
    1 2 3 4
    2 4 1 3
    3 1 4 2
    4 3 2 1
and isomorphic to the multiplication table of {1, i, -i, -1} where i=sqrt(-1), A152680(n) is isomorphic to -1, A002314(n) with i or -i and A152676(n) vice versa -i or i.
1, A002314(n), A152676(n), A152680(n) are subfield of Galois Field [A002144(n)]. (End)
It is found empirically that the solutions of the Diophantine equation X^4 + Y^2 == 0 (mod P) (where P is a prime of the form P=4k+1) are integer points on parabolas Y = (+-(X^2 - P*X) + P*i)/C(P) where C(P) is the term corresponding to a prime P in this sequence. - Seppo Mustonen, Sep 22 2020

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Jon E. Schoenfield, Table of n, a(n) for n = 1..10000 (first 1000 terms from T. D. Noe)
A. J. C. Cunningham, Binomial Factorisations, Vols. 1-9, Hodgson, London, 1923-1929. See Vol. 1, pp. 1-21.
W. Duke, J. B. Friedlander and H. Iwaniec, Equidistribution of roots of a quadratic congruence to prime moduli, Annals of Math, 141 (1995), 423-441.
Jorma K. Merikoski, Pentti Haukkanen, and Timo Tossavainen, The congruence x^n = -a^n (mod m): Solvability and related OEIS sequences, Notes. Num. Theor. Disc. Math. (2024) Vol. 30, No. 3, 516-529. See p. 521.
Seppo Mustonen, Roots of Diophantine equations mod(X^4+Y^2,P)=0, 2020
Seppo Mustonen, Roots of Diophantine equations mod(X^4+Y^2,P)=0, Youtube video, 2020
J. Todd, A problem on arc tangent relations, Amer. Math. Monthly, 56 (1949), 517-528.
A. Toth, Roots of quadratic congruences, Intern. Math. Research Notices, 2000 (2000), 719-739.

Cf. A002313, A005528, A047818, A002144, A152676, A152680. Subsequence of A057756.

f:=proc(n) local i,j,k; for i from 1 to (n-1)/2 do if i^2 +1 mod n = 0 then RETURN(i); fi od: -1; end;
t1:=[]; M:=40; for n from 1 to M do q:=ithprime(n); if q mod 4 = 1 then t1:=[op(t1),f(q)]; fi; od: t1;

aa = {}; Do[If[Mod[Prime[n], 4] == 1, k = 1; While[ ! Mod[k^2 + 1, Prime[n]] == 0, k++ ]; AppendTo[aa, k]], {n, 1, 100}]; aa (* Artur Jasinski, Dec 10 2008 *)

first_N_terms(N) = my(v=vector(N), i=0); forprime(p=5, oo, if(p%4==1, i++; v[i] = lift(sqrt(Mod(-1,p)))); if(i==N, break())); v \\ Jianing Song, Apr 17 2021

Better description from Tony Davie (ad(AT)dcs.st-and.ac.uk), Feb 07 2001

More terms from Jud McCranie, Mar 18 2001

A371479 Irregular triangle read by rows: row n lists the numbers k such that 1<=k<=N/2 and k/N + i/N is in the modular group orbit of i, for N = A008784(n).

Original entry on oeis.org

0, 1, 2, 3, 5, 4, 7, 5, 12, 13, 6, 9, 7, 23, 17, 11, 8, 18, 27, 31, 9, 13, 38, 34, 22, 10, 23, 33, 15, 11, 57, 47, 57, 37, 12, 17, 27, 44, 28, 70, 13, 47, 80, 55, 19, 43, 68, 81, 75, 14, 91, 32, 73, 33, 21, 47, 15, 107, 89, 64, 57, 16, 23, 83, 82, 37, 60, 53, 38, 17, 133, 138, 105, 72, 133, 25, 129, 114, 18, 57, 148, 99, 93, 136, 42, 19, 27, 173, 43, 117, 104, 70, 99, 81, 115, 183, 63

Offset: 1

Valerio De Angelis, Mar 26 2024

The orbit of i under the action of the modular group (that is, the set {(ai+b)/(ci+d): a,b,c,d in Z, ad-bc=1}) is symmetric with respect to the imaginary axis, and periodic with period 1 relative to horizontal translations. So reflecting the orbit in the strip 0<=Re(z)<=1/2 across the imaginary axis and then translating horizontally by integer amounts gives the complete orbit of i in the complex plane.
The orbit in the strip 0<=Re(z)<=1/2 is the union of finite sets, one for each term of A008784, that correspond to the levels of {a(n)}. Each finite set is made of points with rational coordinates on horizontal lines with equation Im(z)=1/N, where N is a term of A008784. Starting at the top with n=1=A008784(1), we have only k=0, or i itself, corresponding to the identity element of the modular group. Then going down one level, at n=2=A008784(2), we have only k=1, or the element 1/2+i/2 corresponding to the modular group element ((1,0),(1,1)). Then at the next level n=3, we have A008784(3)=5, and we still have only one entry k=2, giving 2/5+i/5, corresponding to the matrix ((0,-1),(1,-2)). Continuing this way we find that all levels up to n=16 have only one term of the sequence. This is because if N=A008784(n), then for 1<=n<=16 the equation x^2+y^2=N has only one solution with (x,y) relatively prime. For n=17, we have A008784(17)=65 and (1,8), (4,7) are two solutions of x^2+y^2=65. So we find two terms of the sequence, 8 and 18, at level 17, corresponding to 8/65+i/65 and 18/65+i/65 in the orbit of i, with matrices ((0,-1),(1,-8)) and ((2,1),(7,4)).
So {a(n)} lists the numerators of the real part of the elements of the orbit of i in 0<=Re(z)<=1/2, as we descend the "floors", moving from left to right.
Here is how the sequence is constructed: Each N = A008784(n) can be expressed as the sum of two relatively prime squares. If N has s prime divisors, and all of them are of form 4k+1, then there will be 2^(s-1) solutions of x^2 + y^2 = N (see the MathStackExchange post cited in the Links section).
Consider one such solution, c^2+d^2=N. Let a,b be the unique integers given by the Euclidean algorithm such that ad-bc=1 (or equivalently, the pair of integers (x,y) at minimal distance from the origin such that cx-dy=1). It can be shown that ac+bd will be in {1,2,...,N-1} and relatively prime to N. Let k=min(ac+bd, N-ac-bd). Then k is in {1,2,...,N/2}. Do this for every possible solution of x^2+y^2=N, then list the resulting numbers (all contained in {1,2,3,...,N/2}) in increasing order. These will be the numerators of the rational numbers that are the real part of the points of the orbit of i with imaginary part 1/N. Row n of the triangle is then k1,k2,...,kr and r is the row length, which will always be a power of 2.
The connection with A057756 is as follows: the terms of A057756 are found as the first term of each level of {a(n)} (because A057756 is the numerator of the first rational number on a level of the orbit of i).

			For each row number n, the table below gives N=A008784(n), the number r of terms in the n-th row, and the values of those terms:
.
             terms in row n:
   n   N  r  k = 1   2 ... r
  --  --  -  ---------------
   1   1  1      0;
   2   2  1      1;
   3   5  1      2;
   4  10  1      3;
   5  13  1      5;
   6  17  1      4;
   7  25  1      7;
   8  26  1      5;
   9  29  1     12;
  10  34  1     13;
  11  37  1      6;
  12  41  1      9;
  13  50  1      7;
  14  53  1     23;
  15  58  1     17;
  16  61  1     11;
  17  65  2      8, 18;
  18  73  1     27;
  19  74  1     31;
  20  82  1      9;
  21  85  2     13, 38;
  ...
For row n=17, N=A008784(17)=65 and 65 has two representations as x^2+y^2: 65 = 1^2 + 8^2 = 7^2 + 4^2. For the pair (1,8), we have (a,b)=(1,7), so ac+bd=57, and -ab-cd = -57 == 8 (mod 65). For the pair (7,4) we have (a,b)=(2,1), so ac+bd=18 and -ac-bd = -18 == 47 (mod 65). Taking the minimum, we find that 8,18 will be consecutive terms in the sequence, and 8/65+i/65, 18/65+i/65 will be all the elements in the orbit of i with imaginary part 1/65 and real part in 0<=Re(z)<=1/2. The next level with two terms is A008784(21)=85.

MathStackExchange, Representation as a sum of two squares.

Cf. A008784, A057756.

Showing 1-3 of 3 results.

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

A002314 Minimal integer square root of -1 modulo p, where p is the n-th prime of the form 4k+1.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Extensions

A371479 Irregular triangle read by rows: row n lists the numbers k such that 1<=k<=N/2 and k/N + i/N is in the modular group orbit of i, for N = A008784(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs