A298076 -id:A298076 - cp's OEIS frontend

A292559 Composite numbers m such that lpf(2^m - 1) == 1 (mod m).

169, 221, 323, 611, 779, 793, 923, 1121, 1159, 1271, 1273, 1343, 1349, 1513, 1717, 1829, 1919, 2033, 2077, 2201, 2413, 2533, 2603, 2759, 2951, 3097, 3131, 3173, 3193, 3281, 3379, 3599, 3721, 3743, 3791, 3937, 3953, 4043, 4223, 4309, 4331, 4369, 4607, 4619, 4811, 4867, 4883, 4981, 5111, 5177, 5263, 5429, 5567, 5699

Offset: 1

Michel Marcus and Thomas Ordowski, Sep 19 2017

All terms are coprime to 2, 3, 5, 7, 11. - Robert Israel, Sep 20 2017
If p = lpf(2^m - 1) and A002326((p-1)/2) = m composite, then m is in this sequence. - Thomas Ordowski, Sep 20 2017
Conjecture: there are no numbers k in this sequence such that, for each prime factor q of 2^k - 1, q == 1 (mod k). - Thomas Ordowski, Sep 20 2017
Note: if all prime factors q of 2^k - 1 are q == 1 (mod k), then 2^k - 1 == 1 (mod k), thus 2^k == 2 (mod k), so k is a pseudoprime. The pseudoprime k = a(42) = 4369 = 17*257 is not a counterexample to this conjecture. A pseudoprime k = P*Q such that both 2^P - 1 and 2^Q - 1 are primes would be a counterexample, but the known Mersenne primes do not give such k. - Thomas Ordowski, Oct 02 2017
If lpf(2^n - 1) == 1 (mod n), then gpf(2^n - 1) == 1 (mod n). Cf. A291855. - Thomas Ordowski, Oct 20 2017
Composites m such that lpf(2^m - 1)*gpf(2^m - 1) is a Fermat pseudoprime to base 2, i.e., is in A214305. - Thomas Ordowski, Oct 29 2017

Subsequence of A236769.

Cf. A002326, A049479, A292834, A298076.

searchMax = 1000; Complement[Select[Range[searchMax], Mod[FactorInteger[2^# - 1][[1, 1]], #] == 1 &], Prime[Range[PrimePi[searchMax]]]] (* Alonso del Arte, Sep 19 2017 *)

lista(nn) = forcomposite(n=1, nn, sp = factor(2^n-1)[1,1]; if ((sp % n) == 1, print1(n, ", "))); \\ Michel Marcus, Sep 19 2017

A049479(m) == 1 (mod m).

a(10)-a(54) from Charles R Greathouse IV, Sep 19 2017

A298299 a(n) is the smallest b > 0 such that b^(2n) + 1 has all prime divisors p == 1 (mod 2n).

Original entry on oeis.org

2, 2, 6, 2, 10, 6, 14, 2, 36, 20, 66, 18, 26, 28, 120, 2, 170, 6, 570, 140, 2184, 88, 184, 42, 110, 312, 1440, 42, 116, 9060, 124, 2, 7656, 34, 13650, 132, 74, 228, 7800, 40, 1066, 4158, 430, 132, 6283590, 46, 94, 12, 1246, 1960

Offset: 1

Krzysztof Ziemak and Thomas Ordowski, Jan 16 2018

All the terms are even.
The number a(n)^(2n) + 1 has all divisors d == 1 (mod 2n).
Conjecture: a(n) exists for every n. This is implied by the generalized Bunyakovsky conjecture (Schinzel's hypothesis H).
Theorem: a(n) = 2 if and only if n is a power of 2.
Note: rad(2n) divides rad(a(n)), where rad(m) = A007947(m).
Even numbers 2n such that a(n) = rad(2n) are powers of two and 6, 10, 12, 14, 26, 36, ... Are there infinitely many such numbers?
We have a(n) = 2n = 2, 6, 10, 14, 20, 26, 28, ...
Problem: are there infinitely many even numbers m <> 2^k such that the number m^m + 1 has all divisors d == 1 (mod m)?
From Kevin P. Thompson, Mar 13 2022: (Start)
Additional terms: a(46) = 46, a(47) = 94, a(48) = 12, a(49) = 1246, a(50) = 1960, a(52) = 208, a(53) = 636, a(55) = 17600, a(56) = 476.
a(45) > 1000000 (sequence A298398 likewise has a very large value for n=45).
a(51) >= 16524 (a C241 remains to be factored to verify b=16524).
a(54) >= 6864 (a C201 remains to be factored to verify b=6864).
(End)

			a(5) = 10, because 10^10 + 1 = 10000000001 = 101*3541*27961 and all the prime factors p == 1 (mod 2*5), so all divisors d == 1 (mod 10).

Kevin P. Thompson, Factorizations to support known terms of a(n) for n = 1..56

Cf. A007947, A298076 (see PARI subroutines used for a(48)), A298398.

find_a_ORDOWSKI2(n=2, a=1, B_START=2, LIM=10^11,DEBUG=1)={
  my(B,FF,LL);
  my(fn="_THOMAS_ORDOWSKI_b_a_n.txt");
  LL=R2('b,a,n);   \\ R(b,a,n)=(b^n+a)
  FF=factor(LL);
  if(DEBUG==1,
    print(FF);
    print(LL);
  );
  if(Mod(n,2)==0,  \\ n-EVEN
    B=FIND_BASE(n,BSTART=B_START,LIM,STEP=2,FF);
  );
  if(B>0,
     return([n,B,[subst(FF,'b,B)]]);
  );
  return(0);
}

a(n) = min{b > 1: for all prime p, if p | (b^(2n) + 1) then p == 1 (mod 2n)}.

a(31)-a(44) from Kevin P. Thompson, Mar 13 2022

a(45)-a(50) from Daniel Suteu, Jul 01 2022

A298310 Least k > 1 such that all divisors d of (k^(2n+1)+1)/(k+1) satisfy d == 1 (mod 2n+1).

Original entry on oeis.org

2, 3, 2, 2, 9, 2, 2, 15, 2, 2, 15, 2, 32, 81, 2, 2, 55, 21, 2, 39, 2, 2, 4141, 2, 18, 51, 2, 551, 39, 2, 2, 21267, 21, 2, 1012, 2, 2, 826, 330, 2, 729, 2, 136, 204, 2, 3, 280, 20, 2

Offset: 0

Thomas Ordowski and Krzysztof Ziemak, Jan 17 2018

a(n) is the smallest k > 1 such that Phi_m(-k) has all its divisors == 1 (mod n) for all m > 1 dividing 2n+1, where Phi_m(x) are the cyclotomic polynomials.
By Schinzel's hypothesis H, a(n) exists for every n (see A298076).
If 2n+1 is a prime > 3, then a(n) = 2.
We have a(n)^(2n+1) == a(n) (mod 2n+1), so every composite number 2n+1 is a weak Fermat pseudoprime to base a(n).
a(n) >= A239452(2n+1).
a(42) requires factorization of a 132 digit composite. - M. F. Hasler, Oct 16 2018
From Kevin P. Thompson, Mar 30 2022: (Start)
Additional nontrivial terms: a(55) = 111, a(61) = 165, a(64) = 216, a(66) = 49.
a(49) >= 656811 (a C322 remains to be factored to verify k=656811).
a(52) >= 3547020 (a C288 remains to be factored to verify k=3547020).
a(57) >= 4900 (a C258 remains to be factored to verify k=4900).
a(58) > 784720.
a(59) >= 714 (a C299 remains to be factored to verify k=714).
a(60) >= 233 (a C240 remains to be factored to verify k=233).
a(62) >= 126 (a C191 remains to be factored to verify k=126). (End)

			a(170) = 2 wherein 2*170 + 1 = 341 = 11*31 is the smallest psp(2).
From _M. F. Hasler_, Oct 15 2018: (Start)
a(0) = 2 is the least integer k > 1 for which (k+1)/(k+1) == 1 (mod 1). (Here we even have equality, but any integer is congruent to any other integer, modulo 1.)
a(1) = 3 is the least k > 1 for which (k^3+1)/(k+1) = k^2 - k + 1 = P3(-k) == 1 (mod 3). Indeed, P3(-3) = 7 == 1 (mod 3), while P3(-2) = 3 == 0 (mod 3). (End)

Kevin P. Thompson, Factorizations to support known terms of a(n) for n = 1..68

Cf. A239452, A298076 (see Ordowski's conjecture for b < -1 and odd n).

Table[SelectFirst[Range[2, 100], AllTrue[Divisors[(#^(2 n + 1) + 1)/(# + 1)], Mod[#, 2 n + 1] == 1 &] &], {n, 21}] (* Michael De Vlieger, Feb 01 2018 *)

isok(k, n) = {fordiv((k^(2*n+1)+1)/(k+1), d, if (Mod(d, (2*n+1)) != 1, return (0));); return(1);}
a(n) = {my(k = 2); while (!isok(k, n), k++); k;} \\ Michel Marcus, Jan 19 2018

A298310(n)={n=n*2+1;for(k=2,oo,fordiv(n,m,m>1&&vecmax(factor(polcyclo(m,-k))[,1]%n)!=1&& next(2));return(k))} \\ M. F. Hasler, Oct 14 2018

a(n) = min{k > 1: for all prime p, if p | (k^(2n+1)+1)/(k+1) then p == 1 (mod 2n+1)}. - Kevin P. Thompson, Mar 18 2022

a(22) corrected by Robert Israel, Jan 18 2018
a(1) corrected by Michel Marcus, Jan 19 2018
a(27)-a(30) from Robert Price, Feb 17 2018
a(31)-a(41) from M. F. Hasler, Oct 15 2018
a(42)-a(48) from Kevin P. Thompson, Mar 18 2022

A321576 a(n) is the smallest b > 1 such that b^n - (b-1)^n has all divisors d == 1 (mod n).

Original entry on oeis.org

2, 2, 2, 3, 2, 4, 2, 45, 3, 6, 2, 301, 2, 15, 10, 121, 2, 64, 2, 2101, 7, 12, 2, 1900081, 6, 27, 18, 225, 2, 9241, 2, 31825, 12, 52, 31, 537850405, 2, 96, 26, 13568281, 2, 232, 2, 35421, 486, 24, 2, 4164776161, 7, 2101, 68, 10765, 2, 145180, 1925

Offset: 1

Thomas Ordowski, Nov 13 2018

For n > 1, a(n) is the least b > 1 such that b^n - (b-1)^n has all prime divisors p == 1 (mod n).
If n is prime, then a(n) = 2. Conjecture: If n is composite, then a(n) > 2.
From Kevin P. Thompson, May 27 2022: (Start)
Sequence continues for n = 56..95 (unconfirmed terms marked with a '?'): 20301625?, 171, 30, 2, ?, 2, 156, 18298, 405825?, 442, 361285?, 2, 8365, 553, 392106?, 2, ?, 2, 75, 4975?, 31351?, 1914, 247339?, 2, ?, 1513?, 42, 2, ?, 391, 87, 406?, ?, 2, ?, 39, ?, 63, 142, 145
a(60) > 1.3831*10^10.
a(72) > 1.34*10^8.
a(80) > 10^8.
a(84) > 2.29*10^8.
a(88) > 10^7.
a(90) > 10^8.
a(92) > 10^6. (End)

			a(6) = 4 since b^n - (b-1)^n = 4^6 - 3^6 = 3367 has divisors 1, 7, 13, 37, 91, 259, 481, and 3367, each of which is congruent to 1 (mod 6), and b = 4 is the smallest such number satisfying this requirement.

FactorDB, Status of 20301625^56-20301624^56
Kevin P. Thompson, Factorizations to support known terms for n = 1..95

Cf. A298076.

primes[n_]:=First@# & /@ FactorInteger[n]; bQ[m_, n_]:=AllTrue[primes[m] -1, Divisible[#, n]&] ; a[n_]:=Module[{b=2}, While[!bQ[b^n - (b-1)^n, n], b++]; b]; Array[a, 100] (* Amiram Eldar, Nov 13 2018 *)

A321576(n)=if(n<4||isprime(n),2,for(b=2,oo,Set(factor(b^n-(b-1)^n)[,1]%n)==[1]&&return(b))) \\ M. F. Hasler, Nov 18 2018

a(12)-a(23) from Amiram Eldar, Nov 13 2018

a(24)-a(55) from Kevin P. Thompson, May 27 2022

A352597 a(n) is the smallest k > 1 such that k^n + 1 has all prime divisors p == 1 (mod n).

Original entry on oeis.org

2, 2, 6, 2, 10, 6, 28, 2, 18, 10, 22, 6, 52, 14, 60, 2, 102, 36, 190, 20, 756, 66, 46, 18, 2550, 26, 2970, 28, 58, 120, 310, 2, 330, 170, 11550, 6, 148, 570, 156, 140, 82, 2184, 172, 88, 3040020, 184, 282, 42, 7252, 110, 7548, 312, 106, 1440, 41800, 42, 11172

Offset: 1

Kevin P. Thompson, Mar 21 2022

Equivalently, a(n) is the smallest k > 1 such that for all divisors d of k^n + 1, d == 1 (mod n).
A298299 is a subsequence.
All terms in this sequence are even since for odd k the expression k^n + 1 is divisible by 2 which is not congruent to 1 (mod n) for any n > 1.
If n is odd, a(n)^n + 1 is divisible by a(n) + 1. Therefore, a(n) + 1 == 1 (mod n) and so n | a(n) for odd n.
Theorem: a(n) = 2 if and only if n is a power of 2.

			a(3) = 6 since 6^3 + 1 = 217 = 7 * 31 and both factors are congruent to 1 (mod 3).

Cf. A298076, A298299 (bisection), A298310, A298398.

isok(k,n) = my(f=factor(k^n+1)); for (i=1, #f~, if (Mod(f[i,1], n) != 1, return(0))); return(1);
a(n) = my(k=2); while (!isok(k, n), k+=2); k; \\ Michel Marcus, Mar 22 2022

a(2n) = A298299(n).

cp's OEIS Frontend

A292559 Composite numbers m such that lpf(2^m - 1) == 1 (mod m).

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A298299 a(n) is the smallest b > 0 such that b^(2n) + 1 has all prime divisors p == 1 (mod 2n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

Extensions

A298310 Least k > 1 such that all divisors d of (k^(2n+1)+1)/(k+1) satisfy d == 1 (mod 2n+1).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

Extensions

A321576 a(n) is the smallest b > 1 such that b^n - (b-1)^n has all divisors d == 1 (mod n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A352597 a(n) is the smallest k > 1 such that k^n + 1 has all prime divisors p == 1 (mod n).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

Formula