Let $k$ be a positive integer. Show that there exist infinitely many positive integers $n$ such that $\frac{n^n-1}{n-1}$ has at least $k$ distinct prime divisors. Proposed by Adnan Sadik
Problem
Source: BdMO 2024 Higher Secondary National P8
Tags: number theory, prime divisor, NT construction
18.03.2024 21:11
Zsigmondy?
18.03.2024 22:36
I think the follow is works: Let $n=k^{100k!m}$ for naturals $m>2$ and let $k \geq 100$. Then by Zsigmondy there exists distincts prime numbers $p_1, p_2,..., p_k$ such a $ord_{p_i}n=100i$. But they all divide $n^n-1$ since $100i|100k!|n$ and don't divide $n-1$ (their order is too bigger), so $\frac{n^n-1}{n-1}$ has at least $k$ distinct pre divisors: $p_1,..., p_k$.
18.03.2024 22:44
Also I think here is elementary solution: Let $n=2m$ such a $2m+1$ has at least $k$ distinct odd prime divisors $p_1,...,p_k$ (so they are not divisors of $n-1=2m-1$). There is exist infinity many such $m$ by CRT, for example (for 1st step choose $p_1,...,p_k$ and for second find such $m$). In this case $p_1,..., p_k| \frac{n^n-1}{n-1}$, because $p_i \not | n-1$ and $p_i | n^2-1|n^n-1$, since $2 |n$. So, such $n$ works.
08.01.2025 11:30
$\frac{n^n-1}{n-1}=n^{n-1}+n^{n-2}+...+n+1$ Select $k$ distinct odd primes $p_1,p_2,...,p_k$ And $n=p_1p_2...p_km+1$ where $m$ is an odd positive integer Here $n$ is even $n \equiv -1 \pmod{p_i}$ for all $1 \leq i \leq k$ $n^{odd} \equiv -1 \pmod{p_i}$ and $n^{even} \equiv 1 \pmod{p_i}$ So $n^{n-1}+n^{n-2}+...+n+1 \equiv -1+1-1+..-1+1 \equiv 0 \pmod{p_i}$ So the number has atleast $k$ distinct prime factors and there are infinitely many. $\square$