Determine all composite positive integers $n$ such that, for each positive divisor $d$ of $n$, there are integers $k\geq 0$ and $m\geq 2$ such that $d=k^m+1$.
Problem
Source: Baltic Way 2024, Problem 16
Tags: number theory, number theory proposed, Perfect Powers, Divisors
17.11.2024 12:25
Still solving but I got that $\nu_p(n) \leq 1$ for all primes $p$ due to Mihaelescu. And that all the prime divisors of $n$ must be $2$ or of the form $4l+1$ and if $p=k^m +1$ then $ord_p(k)=2m$.
17.11.2024 15:52
Funny, we claim that $n=10$ is the only solution. Let $p,q$ be two prime divisors of $n$, It is well known that if $a^t+1$ is prime for $a \in \mathbb{N}$ then $t$ is a power of $2$, WLOG $p>q$, let $p = a^2+1$ and $q=b^2+1$ then $c^r+1=pq = (a^2+1)(b^2+1)$, then if $r$ is not power of $2$ then by Zsigmondy, we get atleast three prime divisors contradiction. Claim 1: $N=pq$ can be represented as sum of two squares in exactly $2$ ways for $p,q$ primes of the form $4k+1$.
Let $(c)^{r/2} = c'$, then $c'^2+1=pq=(ab-1)^2+(a+b)^2=(ab+1)^2+(a-b)^2$, so $a=b+1$ and $c'=(ab+1)=b^2+b+1$, Now parity finishes
01.12.2024 11:33
Here's a simpler/motivated finishing to the above solution(s) for which first you need to show $n$ is square-free and prime divisors of $n$ can be written as $e^2+1, e\in \mathbb{Z}$ as shown in the above solutions and then proceed in the following way $:-$ We write $n=pq$, where $p<q$, we let $n=a^2+1$, $p=b^2+1$, $q=c^2+1$, so we have $c^2+1\mid a^2+1\implies a\equiv \pm c\pmod{q}$. For $a=c$ we get $p=1$ which is not possible and if $a=qm-c, m\in \mathbb{Z^+}$ we have $pq=a^2+1=q^2m^2+c^2+1-2qmc=q(qm^2-2mc+1)$, here $m=1$ because $a^2<n=pq<q^2$ then we have $q^2-2c+1$ which is even and it is also the value of $p$, this gives $q=2c+1\implies c=2\implies q=5\implies \boxed{n=10}$.
09.12.2024 14:00
See also: https://artofproblemsolving.com/community/c6h1555330p9482101