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

A105222 Smallest integer m > 1 such that m^(n-1) == 1 (mod n).

Original entry on oeis.org

2, 3, 2, 5, 2, 7, 2, 9, 8, 11, 2, 13, 2, 15, 4, 17, 2, 19, 2, 21, 8, 23, 2, 25, 7, 27, 26, 9, 2, 31, 2, 33, 10, 35, 6, 37, 2, 39, 14, 41, 2, 43, 2, 45, 8, 47, 2, 49, 18, 51, 16, 9, 2, 55, 21, 57, 20, 59, 2, 61, 2, 63, 8, 65, 8, 25, 2, 69, 22, 11, 2, 73, 2, 75, 26

Offset: 1

Max Alekseyev, Apr 14 2005

Composite n are Fermat pseudoprimes to base a(n).

For n > 1; (5+(-1)^n)/2 <= a(n) <= n+(-1)^n. If n > 2 and a(n) > 2 then n is composite. - Thomas Ordowski, Dec 01 2013

			We have 2^(2-1) == 0, 3^(2-1) == 1 (mod 2), so a(2) = 3.

T. D. Noe, Table of n, a(n) for n = 1..10000
Eric Weisstein's World of Mathematics, Fermat Pseudoprime
Wikipedia, Fermat pseudoprime

Cf. A007535, A181780, A239452.

Table[k = 2; While[PowerMod[k, n - 1, n] != 1, k++]; k, {n, 2, 100}] (* T. D. Noe, Dec 07 2013 *)

a(n) = {m = 2; while ((m^(n-1) % n) !=  lift(Mod(1, n)), m++); m; } \\ Michel Marcus, Dec 01 2013

a(n) = my(m=2); while(Mod(m, n)^(n-1)!=1, m++); m \\ Charles R Greathouse IV, Dec 01 2013

a(p) = 2 for odd prime p.

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

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

A105222 Smallest integer m > 1 such that m^(n-1) == 1 (mod n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

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