A292559 -id:A292559 - cp's OEIS frontend

A298076 Least k > 1 such that all divisors of (k^n-1)/(k-1) are == 1 (mod n).

2, 2, 2, 4, 2, 6, 2, 16, 8, 10, 2, 1260, 2, 28, 24, 16, 2, 162, 2, 2080, 6, 22, 2, 207480, 7, 52, 27, 420, 2, 43890, 2, 256, 21, 102, 370, 5988060, 2, 190, 12, 7412680, 2, 2016, 2, 507496, 495, 46, 2, 1486179696, 68, 5050, 476, 66300, 2, 3292758, 274, 72682120

Offset: 1

Robert Israel and Thomas Ordowski, Jan 11 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 n, where Phi_m(x) are the cyclotomic polynomials.
If n is a prime, then a(n) = 2.
It seems that if n is a composite, then a(n) > 2. We have a(91) = 3.
If n is even, a(n) is divisible by n.
The generalized Bunyakovsky conjecture (Schinzel's hypothesis H) implies that there exist k divisible by n such that Phi_m(k) is prime for all m > 1 dividing n, and thus that a(n) always exists.
If n is composite, n is a weak Fermat pseudoprime to base a(n).
a(n) >= A239452(n), with equality for primes and 1, 4, 9, 16, 21, 25, 39, 91, ... Are there infinitely many such numbers?
a(n) = n for n = 2, 4, 6, 10, 16, 22, 27, 46, ...
Problem: Are there infinitely many composite numbers n such that the number (n^n-1)/(n-1) has all divisors d == 1 (mod n)?
Conjecture (T. Ordowski, 2018): Let b be an integer with |b| > 1. Then the number (b^n-1)/(b-1) has all divisors d == 1 (mod n) for a composite n if and only if the number n is a weak Fermat pseudoprime to base |b| such that, for each prime divisor p of n, the number (b^p-1)/(b-1) has all prime divisors q == 1 (mod n).
Also: least k > 1 such that all prime factors of (k^n-1)/(k-1) are == 1 (mod n). - M. F. Hasler, Oct 14 2018

			a(10) = 10, because (10^10 - 1)/9 = 1111111111 = 11*41*271*9091 and all the prime factors p == 1 (mod 10), so all divisors d == 1 (mod 10).

Krzysztof Ziemak, PARI code for a(48)=1486179696

Cf. A239452, A292559, A298310.

g:= t -> convert(select(type,map(s -> s[1], ifactors(t,easy)[2]),integer),set):
F:= proc(n) local b,C,B,k,bb,Cb, easyf, c; uses numtheory;
   if isprime(n) then return 2 fi;
   C:= {seq(unapply(cyclotomic(m,t),t), m=divisors(n) minus {1})};
   B:= select(t -> C(t) mod n = {1}, [$0..n-1]);
   for k from 0 do
     for bb in B do
       b:= k*n+bb;
       if b < 2 then next fi;
       Cb:= remove(isprime,C(b));
       if Cb = {} then return b fi;
       easyf:= map(g, Cb) mod n;
       if not(`union`(op(easyf)) subset {1}) then next fi;
       if andmap(c -> factorset(c) mod n = {1}, Cb) then return b fi
     od
   od
end proc:
2, seq(F(n),n=2..30);

{2}~Join~Table[Block[{k = 2}, While[Union@ Mod[Divisors[(k^n - 1)/(k - 1)], n] != {1}, k++]; k], {n, 2, 19}] (* Michael De Vlieger, Jan 11 2018 *)

A298076(n,f=if(bittest(n,0),1,n))={forstep(k=max(f,2),oo,f, fordiv(n,m,m>1&& Set(factor(polcyclo(m,k))[,1]%n)!=[1]&& next(2));return(k))} \\ Becomes slow for multiples of 5 and 12 beyond n = 34. - M. F. Hasler, Oct 14 2018

a(n)^n == a(n) mod n.

a(48)-a(56) from Krzysztof Ziemak, Jan 15 2018

A292834 Numbers m, not powers of 2, such that the least prime factor of 2^m + 1 is congruent to 1 (mod m).

Original entry on oeis.org

24, 48, 112, 160, 192, 272, 448, 496, 656, 688, 832, 896, 1088, 1152, 1168, 1328, 1360, 1408, 1472, 1520, 1664, 1744, 1920, 1984, 2176, 2304, 2432, 2560, 2688, 2752, 2816, 2944, 2960, 3056, 3072, 3200, 3328, 3520, 3664, 3712, 3776, 4672, 4864, 4928, 5120, 5376, 5552, 5888, 6144

Offset: 1

Thomas Ordowski, Sep 24 2017

Problem: are there infinitely many such numbers?
Theorem: there are no numbers m in the sequence such that, for each prime factor p of 2^m + 1, p == 1 (mod m).
Proof: if all prime factors p of 2^m + 1 are p == 1 (mod m), then 2^m + 1 == 1 (mod m), thus 2^m == 0 (mod m), so m = 2^k.
From Theorem in A002586, all terms are == 0 (mod 8). - Robert G. Wilson v, Jan 02 2018

Robert G. Wilson v, Table of n, a(n) for n = 1..71

Cf. A002586, A292559.

Select[Range[200], And[! IntegerQ @ Log2 @ #, Mod[FactorInteger[2^# + 1][[1, 1]], #] == 1] &] (* Michael De Vlieger, Sep 24 2017 *)
fQ[n_] := If[ OddQ@ n || IntegerQ@ Log2@ n || PrimeQ[2^n +1], False, Block[{p = 3}, While[PowerMod[2, n, p] +1 != p, p = NextPrime@ p]; Mod[p, n] == 1]] (* Robert G. Wilson v, Jan 01 2018 *)

isok(n) = my(e = valuation(n, 2)); (2^e != n) && ((vecmin(factor(2^n+1)[,1]) % n) == 1); \\ Michel Marcus, Nov 13 2017

a(9)-a(15) from Robert G. Wilson v, Jan 01 2018

a(16)-a(49) from Robert G. Wilson v, Jan 02 2018

A350381 Composite numbers k such that the multiplicative order of 2 modulo lpf(2^k-1) is k, where lpf = least prime factor.

Original entry on oeis.org

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

Offset: 1

Jianing Song, Dec 28 2021

Obviously, if p is a prime, then the multiplicative order of 2 modulo lpf(2^p-1) is p.
It is easy to see that this is a subsequence of A292559 and A322568, so this sequence is included in the intersection of those two sequences. The inclusion is proper. 68231 is in A292559 and A322568 but not in this sequence: lpf(2^68231-1) = 136463 = 2*68231 + 1, the multiplicative order of 2 modulo 136463 is 2201 = 31 * 71 < 68231.
A semiprime in A322568 is in this sequence by definition. 20519, 48263, 63023, 138263, 216239, 341651, 421259, 480323 are examples of terms that are not semiprimes.
Every term is coprime to 2, 3, 5, 7, 11 and 23.

			169 is a term since the least prime factor of 2^169 - 1 is 4057, and the multiplicative order of 2 modulo 4057 is 169.
323 is a term since the least prime factor of 2^323 - 1 is 647, and the multiplicative order of 2 modulo 647 is 323.
1343 is not a term since the least prime factor of 2^1343 - 1 is 2687, and the multiplicative order of 2 modulo 2687 is 79 < 1343.

Cf. A049479 (lpf(2^n-1)), A292559, A322568.

b(n) = forprime(p=3, oo, if(n % znorder(Mod(2,p))==0, return(p)))
isA350381(n) = !isprime(n) && (n>1) && znorder(Mod(2,b(n)))==n \\ Warning: this program can only give the first 7 terms.

More terms from Jinyuan Wang, Jan 22 2025

cp's OEIS Frontend

A298076 Least k > 1 such that all divisors of (k^n-1)/(k-1) are == 1 (mod n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A292834 Numbers m, not powers of 2, such that the least prime factor of 2^m + 1 is congruent to 1 (mod m).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A350381 Composite numbers k such that the multiplicative order of 2 modulo lpf(2^k-1) is k, where lpf = least prime factor.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

Extensions