OFFSET
1,1
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
LINKS
Krzysztof Ziemak, PARI code for a(48)=1486179696
FORMULA
a(n)^n == a(n) mod n.
EXAMPLE
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).
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 *)
PROG
(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
CROSSREFS
KEYWORD
nonn,hard,more
AUTHOR
Robert Israel and Thomas Ordowski, Jan 11 2018
EXTENSIONS
a(48)-a(56) from Krzysztof Ziemak, Jan 15 2018
STATUS
approved