Find all positive integers $k$, so that there are only finitely many positive odd numbers $n$ satisfying $n~|~k^n+1$.
Problem
Source: 2020 Vietnam TST P5
Tags: Vietnam, TST, ord
29.06.2020 20:51
Any solution?
29.06.2020 21:11
lol classic problem $k+1=2^c$ with $c \in \mathbb{N}$ are the only ones for which the proprety holds if $k+1$ is not a power of $2$, then it is well known.. https://artofproblemsolving.com/community/c6h1664169p10570998 (by zsigmondy and taking $p_0$ to be odd we can force our $n$'s to be odd) if $k+1=2^c$ then if we have $n|k^n+1$, let $p$ be the smallest prime number which divides $n$ so we have $p|k^{2n}-1$ and $p|k^{p-1}-1$ hence $p|k^{\gcd(p-1;2n)}-1$ by the minimality of $p$ we have $\gcd(p-1;2n)=2$ (we already have $n$ must be odd so $p-1$ is even) so we deduce that $p|k^2-1$ which implies that $p|k+1$ or $p|k-1$ (the second case is impossible because $p|k-1$ implies $p|k^n-1$ and hence $p|2$) so $p|k+1$ but $k+1$ is a power of $2$ !! so $n$ must be even
29.06.2020 22:41
The answer should be $k=1$ .This is a well-known problem , so I'll only provide the sketch . Otherwise if $k>1$ and : $(a)$ $k$ is even : Define an infinite sequence $n_1,n_2,\dots$ , where $n_1=k^n+1>n$ is odd, and $k^n+1\mid k^{n_1}+1$ , it's indeed true as $\frac{n_1}{n}$ is odd . $(b)$ $k$ is odd , $v_2(n)\le 1$ as $4\nmid k^n+1$ Also $n_1=k^n+1$ is even this time so $\frac{n_1}{n}$ is odd . So we can define a sequence with $n_{i+1}=k^{n_i}+1$ and we're done.
29.06.2020 23:20
Kamran011 wrote: The answer should be $k=1$ .This is a well-known problem , so I'll only provide the sketch . Otherwise if $k>1$ and : $(a)$ $k$ is even : Define an infinite sequence $n_1,n_2,\dots$ , where $n_1=k^n+1>n$ is odd, and $k^n+1\mid k^{n_1}+1$ , it's indeed true as $\frac{n_1}{n}$ is odd . $(b)$ $k$ is odd , $v_2(n)\le 1$ as $4\nmid k^n+1$ Also $n_1=k^n+1$ is even this time so $\frac{n_1}{n}$ is odd . So we can define a sequence with $n_{i+1}=k^{n_i}+1$ and we're done. $n$ must be odd :p
29.06.2020 23:26
I have solved generally , I proved that : For any $k>1$ there're infinitely many $n$ satisfying $n\mid k^n+1$
29.06.2020 23:29
lol ok but that's not what the problem asked for (:
29.06.2020 23:31
What ? This is exactly what the problem asks We have to find all $k$ s.t. there're finitely many $n$ satisfying $n~|~k^n+1$ and I showed that for any $k>1$ it's impossible. @below , sorry
29.06.2020 23:34
many positive odd numbers $n$
05.07.2020 13:48
Does anyone have the rest of the problems of this TST?