A209874 -id:A209874 - cp's OEIS frontend

A209877 a(n) = A209874(n)/2: Least m > 0 such that 4*m^2 = -1 modulo the Pythagorean prime A002144(n).

1, 4, 2, 6, 3, 16, 15, 25, 23, 17, 11, 5, 38, 49, 50, 22, 14, 40, 81, 56, 7, 61, 72, 32, 8, 41, 30, 114, 69, 144, 57, 74, 68, 21, 52, 137, 167, 10, 133, 196, 127, 191, 174, 24, 104, 143, 26, 59, 43, 12, 258, 238, 289, 97, 77, 252, 53, 29, 13, 283, 48, 190, 335, 361, 31, 228, 291, 159, 263, 123, 260, 325, 363, 247, 162

Offset: 1

M. F. Hasler, Mar 14 2012

nonn

Also: Square root of -1/4 in Z/pZ, for Pythagorean primes p=A002144(n).
Also: Least m>0 such that the Pythagorean prime p=A002144(n) divides 4(kp +/- m)^2+1 for all k>=0.
In practice these can also be determined by searching the least N^2+1 whose least prime factor is p=A002144(n): For given p, all of these N will have a(n) or p-a(n) as remainder mod 2p.

			a(1)=1 since A002144(1)=5 and 4*1^2+1 is divisible by 5; as a consequence 4*(5k+/-1)^2+1 = 100k^2 +/- 40k + 5 is divisible by 5 for all k.
a(2)=4 since A002144(2)=13 and 4*4^2+1 = 65 is divisible by 13, while 4*1^1+1=5, 4*2^2+1=17 and 4*3^2+1=37 are not. As a consequence, 4*(13k+/-4)^2+1 = 13(...)+4*4^1+1 is divisible by 13 for all k.

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

Cf. A209874.
Cf. A002496, A014442, A085722, A144255, A089120, A193432.
Cf. A002314, A177979.

f:= proc(p) local m;
   if not isprime(p) then return NULL fi;
   m:= numtheory:-msqrt(-1/4, p);
   min(m,p-m);
end proc:
map(f, [seq(i,i=5..1000,4)]); # Robert Israel, Mar 13 2018

f[p_] := Module[{r}, r /. Solve[4 r^2 == -1, r, Modulus -> p] // Min];
f /@ Select[4 Range[300] + 1, PrimeQ] (* Jean-François Alcover, Jul 27 2020 *)

apply(p->lift(sqrt(Mod(-1,p)/4)), A002144)

A089120 Smallest prime factor of n^2 + 1.

Original entry on oeis.org

2, 5, 2, 17, 2, 37, 2, 5, 2, 101, 2, 5, 2, 197, 2, 257, 2, 5, 2, 401, 2, 5, 2, 577, 2, 677, 2, 5, 2, 17, 2, 5, 2, 13, 2, 1297, 2, 5, 2, 1601, 2, 5, 2, 13, 2, 29, 2, 5, 2, 41, 2, 5, 2, 2917, 2, 3137, 2, 5, 2, 13, 2, 5, 2, 17, 2, 4357, 2, 5, 2, 13, 2, 5, 2, 5477, 2, 53, 2, 5, 2, 37, 2, 5, 2

Offset: 1

Cino Hilliard, Dec 05 2003

This includes A002496, primes that are of the form n^2+1.

Note that a(n) is the smallest prime p such that n^(p+1) == -1 (mod p). - Thomas Ordowski, Nov 08 2019

H. Rademacher, Lectures on Elementary Number Theory, pp. 33-38.

Michael De Vlieger, Table of n, a(n) for n = 1..10000

Cf. A002496, A014442, A085722, A144255, A193432.

[Min(PrimeDivisors(n^2+1)):n in [1..100]]; // Marius A. Burtea, Nov 13 2019

Array[FactorInteger[#^2 + 1][[1, 1]] &, {83}] (* Michael De Vlieger, Sep 08 2015 *)

smallasqp1(m) = { for(a=1,m, y=a^2 + 1; f = factor(y); v = component(f,1); v1 = v[length(v)]; print1(v[1]",") ) }

A089120(n)=factor(n^2+1)[1,1]  \\ M. F. Hasler, Mar 11 2012

a(2k+1)=2; a(10k +/- 2)=5, else a(26k +/- 8)=13, else a(34k +/- 4)=17, else a(58k +/- 12)=29, else a(74k +/- 6)=37,... - M. F. Hasler, Mar 11 2012

A089120(n) = 2 if n is odd, else A089120(n) = min { A002144(k) | n = +/- A209874(k) (mod 2*A002144(k)) }.

A248531 Numbers n such that the smallest prime divisor of n^2+1 is 41.

Original entry on oeis.org

50, 114, 196, 214, 296, 624, 706, 770, 870, 934, 1034, 1180, 1280, 1426, 1444, 1590, 1690, 1754, 1836, 1936, 2000, 2164, 2246, 2264, 2346, 2574, 2674, 2756, 2820, 2984, 3066, 3084, 3230, 3330, 3394, 3494, 3576, 3640, 3740, 3886, 3904, 4214, 4296, 4460, 4624

Offset: 1

Michel Lagneau, Oct 08 2014

Or numbers n such that the smallest prime divisor of n^2+1 is A002313(7).

a(n)== 32 or 50 (mod 82).

			50 is in the sequence because 50^2+1= 41*61.

Amiram Eldar, Table of n, a(n) for n = 1..10000

Cf. A089120, A002313, A209874, A248527, A248528, A248529, A248530.

[n: n in [2..5000] | PrimeDivisors(n^2+1)[1] eq 41]; // Bruno Berselli, Oct 08 2014

lst={};Do[If[FactorInteger[n^2+1][[1, 1]]==41, AppendTo[lst, n]], {n, 2, 2000}]; lst
Select[Range[5000],FactorInteger[#^2+1][[1,1]]==41&] (* Harvey P. Dale, Aug 15 2017 *)
p = 41; ps = Select[Range[p - 1], Mod[#, 4] != 3 && PrimeQ[#] &]; Select[Range[5000], Divisible[(nn = #^2 + 1), p] && ! Or @@ Divisible[nn, ps] &] (* Amiram Eldar, Aug 16 2019 *)

A248549 Numbers n such that the smallest prime divisor of n^2+1 is 61.

Original entry on oeis.org

194, 316, 416, 804, 904, 926, 1026, 1170, 1270, 1414, 1536, 1780, 2024, 2490, 2734, 2856, 3000, 3100, 3244, 3344, 3366, 3610, 3954, 3976, 4320, 4564, 4830, 4930, 5074, 5196, 5540, 5684, 6394, 6416, 6516, 6760, 6904, 7004, 7126, 7270, 7370, 7514, 7614, 7736

Offset: 1

Michel Lagneau, Oct 08 2014

Or numbers n such that the smallest prime divisor of n^2+1 is A002313(9).

a(n)== 50 or 72 (mod 122).

			194 is in the sequence because 194^2+1= 61*617.

Amiram Eldar, Table of n, a(n) for n = 1..10000

Cf. A089120, A002313, A209874, A248527-A248531, A248549-A248553.

lst={};Do[If[FactorInteger[n^2+1][[1, 1]]==61, AppendTo[lst, n]], {n, 2, 10000}]; lst
p = 61; ps = Select[Range[p - 1], Mod[#, 4] != 3 && PrimeQ[#] &]; Select[Range[8000], Divisible[(nn = #^2 + 1), p] && ! Or @@ Divisible[nn, ps] &] (* Amiram Eldar, Aug 16 2019 *)

A248553 Numbers n such that the smallest prime divisor of n^2+1 is 101.

Original entry on oeis.org

10, 414, 596, 1000, 1020, 1606, 1626, 2030, 2414, 2434, 2616, 3444, 3626, 3646, 4030, 5040, 5060, 5646, 5666, 6070, 6454, 6474, 6656, 6676, 7060, 7464, 7666, 7686, 8070, 8090, 8474, 8696, 9080, 9504, 10090, 10494, 10696, 10716, 11504, 11706, 12534, 12716, 12736

Offset: 1

Michel Lagneau, Oct 08 2014

Or numbers n such that the smallest prime divisor of n^2+1 is A002313(13).

a(n)== 10 or 192 (mod 202).

			414 is in the sequence because 414^2+1= 101*1697.

Amiram Eldar, Table of n, a(n) for n = 1..10000

Cf. A089120, A002313, A209874, A248527-A248531, A248549-A248553.

lst={};Do[If[FactorInteger[n^2+1][[1, 1]]==101, AppendTo[lst, n]], {n, 2, 10000}]; lst
p = 101; ps = Select[Range[p - 1], Mod[#, 4] != 3 && PrimeQ[#] &]; Select[Range[13000], Divisible[(nn = #^2 + 1), p] && ! Or @@ Divisible[nn, ps] &] (* Amiram Eldar, Aug 16 2019 *)
Select[Range[13000],FactorInteger[#^2+1][[1,1]]==101&] (* Harvey P. Dale, Oct 01 2024 *)

A248529 Numbers n such that the smallest prime divisor of n^2+1 is 29.

Original entry on oeis.org

46, 104, 186, 220, 244, 360, 394, 510, 534, 626, 766, 800, 916, 940, 974, 1056, 1090, 1114, 1206, 1264, 1346, 1380, 1404, 1496, 1520, 1554, 1694, 1810, 1844, 1926, 1960, 2076, 2100, 2134, 2216, 2250, 2366, 2390, 2424, 2506, 2564, 2680, 2714, 2796, 2830, 2854

Offset: 1

Michel Lagneau, Oct 08 2014

Or numbers n such that the smallest prime divisor of n^2+1 is A002313(5).

a(n)== 12 or 46 (mod 58).

			46 is in the sequence because 46^2+1= 29*73.

Amiram Eldar, Table of n, a(n) for n = 1..10000

Cf. A089120, A002313, A209874, A248527, A248528.

[n: n in [2..3000] | PrimeDivisors(n^2+1)[1] eq 29]; // Bruno Berselli, Oct 08 2014

lst={};Do[If[FactorInteger[n^2+1][[1, 1]]==29, AppendTo[lst, n]], {n, 2, 2000}]; lst
p = 29; ps = Select[Range[p - 1], Mod[#, 4] != 3 && PrimeQ[#] &]; Select[Range[3000], Divisible[(nn = #^2 + 1), p] && ! Or @@ Divisible[nn, ps] &] (* Amiram Eldar, Aug 16 2019 *)
Select[Range[2,3000,2],FactorInteger[#^2+1][[1,1]]==29&] (* or *) Select[ Flatten[ #+{12,46}&/@(58*Range[0,60])],FactorInteger[#^2+1][[1,1]]==29&](* Harvey P. Dale, Jul 01 2022 *)

A248530 Numbers n such that the smallest prime divisor of n^2+1 is 37.

Original entry on oeis.org

6, 80, 154, 290, 364, 376, 524, 586, 660, 734, 894, 1030, 1104, 1116, 1190, 1326, 1400, 1486, 1634, 1770, 1856, 1930, 2004, 2066, 2226, 2300, 2510, 2584, 2596, 2744, 2806, 2880, 2966, 3040, 3114, 3176, 3250, 3324, 3484, 3546, 3620, 3694, 3706, 3780, 3854, 3916

Offset: 1

Michel Lagneau, Oct 08 2014

Or numbers n such that the smallest prime divisor of n^2+1 is A002313(6).

a(n)== 6 or 68 (mod 74).

			80 is in the sequence because 80^2+1= 37*173.

Amiram Eldar, Table of n, a(n) for n = 1..10000

Cf. A089120, A002313, A209874, A248527, A248528, A248529.

[n: n in [2..4000] | PrimeDivisors(n^2+1)[1] eq 37]; // Bruno Berselli, Oct 08 2014

lst={};Do[If[FactorInteger[n^2+1][[1, 1]]==37, AppendTo[lst, n]], {n, 2, 4000}]; lst
p = 37; ps = Select[Range[p - 1], Mod[#, 4] != 3 && PrimeQ[#] &]; Select[Range[4000], Divisible[(nn = #^2 + 1), p] && ! Or @@ Divisible[nn, ps] &] (* Amiram Eldar, Aug 16 2019 *)

A336883 a(n) = ((A002144(n) - 1)/2)! (mod A002144(n)) where A002144(n) is the n-th Pythagorean prime.

Original entry on oeis.org

2, 5, 13, 12, 31, 9, 23, 11, 27, 34, 22, 91, 33, 15, 37, 44, 129, 80, 162, 81, 183, 122, 144, 64, 16, 187, 217, 53, 138, 288, 114, 189, 213, 42, 104, 274, 63, 381, 266, 29, 254, 382, 348, 48, 301, 286, 489, 439, 483, 24, 77, 125, 578, 423, 487, 149, 555, 615, 651, 135, 96, 380, 87, 39, 707

Offset: 1

Hiroyuki Hara, Aug 06 2020

nonn

Let p(n) = A002144(n) be the n-th Pythagorean prime.
Pythagorean prime p can be divided into a pair of integers (a,b) such as p =a+b and a*b==1 mod p. And (p-2)!==1 mod p because of Wilson's Theorem (p-1)!==-1 mod p. It can be divided into two parts (a,b) such as {2*3*4*...*((p(n)-1)/2)==a(n) mod p(n)} and {((p(n)-1)/2+1)*...*(p(n)-4)*(p(n)-3)*(p(n)-2)==-a(n)==(p(n)-a(n)) mod p(n)}. The pair numbers make a(n)+(p(n)-a(n))=p(n) and a(n)*(p(n)-a(n))==1 mod p(n). The left integer of the pair numbers is a(n). The right integer (p(n)-a(n)) is A336884(n).
The set of selecting odd numbers from {a(n)} and A336884 is A206549. The set of selecting even numbers from {a(n)} and A336884 is A209874 except for the number 1. A256011 never appears in {a(n)} or A336884. It is related to nonexistence of numbers that the largest prime factor of n^2+1 is greater than n.
The odd number of the difference |a(n)-A336884(n)|=|a(n)-(p(n)-a(n))|=|2*a(n)-p(n)| is A186814(n). A282538 never appears in the set of the difference |a(n)-A336884(n)|.
If p(n) is unknown, p(n) can be derived from a(n) using following equation. From a*b==1 mod p, a*b=k*p+1. With p=a+b, it can transform to b(n)=(k*a(n)+1)/(a(n)-k), k is an odd integer parameter when the fraction makes an integer. If there are many k's, select the minimum k in those. Then a(n)+b(n)=p(n). b(n) is A336884(n).

			p(1)=5: (5-2)!=2*3=a(1)*(5-a(1))==1 mod 5. 5=2+3.
p(2)=13: (13-2)!=(2*3*4*5*6)*(7*8*9*10*11)=(2*3*4*5*6)*((p-6)*(p-5)*(p-4)*(p-3)*(p-2))==5*(-5)==5*(13-5)=5*8==a(2)*(13-a(2))==1 mod 13. 13=5+8.
a(n)=13: b(n)=(k*13+1)/(13-k)=(3*13+1)/(13-3)=4, k=3. p(n)=13+4=17.
a(n)=12: b(n)=(k*12+1)/(12-k)=(7*12+1)/(12-7)=17, k=7. p(n)=12+17=29.

Hiroyuki Hara, Table of n, a(n) for n = 1..4783 [reformatted and restored by _Georg Fischer_, Oct 15 2020]

Cf. A336884, A002144 (Pythagorean primes), A206549, A209874, A256011, A186814, A282538.

Map[Mod[((# - 1)/2)!, #] &, Select[4 Range[192] + 1, PrimeQ]] (* Michael De Vlieger, Oct 15 2020 *)

my(v=select(p->p%4==1, primes(100))); apply(x->(((x-1)/2)! % x), v) \\ Michel Marcus, Aug 07 2020

n_start=5
n_end=n_start+10000
k = 1
for n in range(n_start, n_end, 4):
    c=(n-1)//2
    r=1
    for i in range(2, c+1):
        r=r*i % n
        if r==0:
            break
    if (n-r)*r % n ==1:
        print(k, r)
        k = k + 1
# modified by Georg Fischer, Oct 16 2020

A336884 a(n) = A002144(n) - A336883(n) where A002144(n) is the n-th Pythagorean prime.

Original entry on oeis.org

3, 8, 4, 17, 6, 32, 30, 50, 46, 55, 75, 10, 76, 98, 100, 105, 28, 93, 19, 112, 14, 107, 89, 177, 241, 82, 60, 228, 155, 25, 203, 148, 136, 311, 269, 115, 334, 20, 143, 392, 179, 67, 109, 413, 208, 235, 52, 118, 86, 553, 516, 476, 35, 194, 154, 504, 106, 58, 26, 566, 613, 353, 670, 722

Offset: 1

Hiroyuki Hara, Aug 06 2020

nonn

For more information see A336883.

			p(1)=5: (5-2)!=2*3=A336883(1)*a(1)==1 mod 5. 5=2+3.
p(2)=13: (13-2)!=(2*3*4*5*6)*(7*8*9*10*11)=(2*3*4*5*6)*((p-6)*(p-5)*(p-4)*(p-3)*(p-2))==5*(-5)==5*(13-5)=5*8==A336883(2)*a(2)==1 mod 13. 13=5+8.
a(n)=4: A336883(n)=(k*4+1)/(4-k)=(3*4+1)/(4-3)=13, k=3. p(n)=13+4=17.
a(n)=17: A336883(n)=(k*17+1)/(17-k)=(7*17+1)/(17-7)=12, k=7. p(n)=12+17=29.

Hiroyuki Hara, Table of n, a(n) for n = 1..4783 [reformatted and restored by _Georg Fischer_, Oct 16 2020]

Cf. A336883, A002144 (Pythagorean primes), A206549, A209874, A256011, A186814, A282538.

v = Select[Prime[Range[1000]], Mod[#, 4] == 1&];
v - Mod[((v-1)/2)!, v] (* Jean-François Alcover, Oct 24 2020, after PARI *)

my(v=select(p->p%4==1, primes(100))); apply(x->x - (((x-1)/2)! % x), v) \\ Michel Marcus, Aug 07 2020

n_start=5
n_end=n_start+100000
k=1
for n in range(n_start, n_end, 4):
    c=(n-1)//2
    r=1
    for i in range(2, c+1):
        r=r*i % n
        if r==0:
            break
    if (n-r)*r % n ==1:
        print(k, n-r)
        k = k + 1
# modified by Georg Fischer, Oct 16 2020

a(n) == (A002144(n) - 2)!/((A002144(n) - 1)/2)! == -((A002144(n) - 1)/2)! == -A336883(n) == A002144(n) - A336883(n) mod A002144(n).

A248532 Numbers n such that the smallest prime divisor of n^2+1 is 53.

Original entry on oeis.org

76, 136, 454, 500, 560, 666, 924, 984, 1196, 1454, 1514, 1666, 1726, 2090, 2196, 2256, 2620, 2726, 2786, 3044, 3104, 3150, 3210, 3256, 3316, 3680, 3786, 4104, 4210, 4270, 4316, 4634, 4694, 4800, 4846, 5224, 5330, 5694, 5800, 5860, 5906, 5966, 6224, 6330, 6390

Offset: 1

Michel Lagneau, Oct 08 2014

Or numbers n such that the smallest prime divisor of n^2+1 is A002313(8).

a(n)== 30 or 76 (mod 106).

			76 is in the sequence because 76^2+1= 53*109.

Amiram Eldar, Table of n, a(n) for n = 1..10000 (terms 1..1000 from Harvey P. Dale)

Cf. A089120, A002313, A209874, A248527, A248528, A248529, A248530, A248531.

[n: n in [2..7000] | PrimeDivisors(n^2+1)[1] eq 53]; // Bruno Berselli, Oct 08 2014

lst={};Do[If[FactorInteger[n^2+1][[1, 1]]==53, AppendTo[lst, n]], {n, 2, 2000}]; lst
Select[Range[7000],FactorInteger[#^2+1][[1,1]]==53&] (* Harvey P. Dale, Aug 04 2016 *)
p = 53; ps = Select[Range[p - 1], Mod[#, 4] != 3 && PrimeQ[#] &]; Select[Range[7000], Divisible[(nn = #^2 + 1), p] && ! Or @@ Divisible[nn, ps] &] (* Amiram Eldar, Aug 16 2019 *)

cp's OEIS Frontend

A209877 a(n) = A209874(n)/2: Least m > 0 such that 4*m^2 = -1 modulo the Pythagorean prime A002144(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

A089120 Smallest prime factor of n^2 + 1.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Magma

Mathematica

PARI

PARI

Formula

A248531 Numbers n such that the smallest prime divisor of n^2+1 is 41.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

A248549 Numbers n such that the smallest prime divisor of n^2+1 is 61.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A248553 Numbers n such that the smallest prime divisor of n^2+1 is 101.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A248529 Numbers n such that the smallest prime divisor of n^2+1 is 29.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

A248530 Numbers n such that the smallest prime divisor of n^2+1 is 37.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica