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

Author

Robert Israel and Thomas Ordowski, Jan 11 2018

Keywords

• nonn
• hard
• more

Comments

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

Examples

			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).
		

Links

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

Crossrefs

Cf. A239452, A292559, A298310.

Programs

Maple

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);

Mathematica

{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 *)

PARI

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

Formula

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

Extensions

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