|
| |
|
|
A298076
|
|
Least k > 1 such that all divisors of (k^n-1)/(k-1) are == 1 (mod n).
|
|
6
|
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
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
|
|
|
|
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
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
