Find all prime number $p$, such that there exist an infinite number of positive integer $n$ satisfying the following condition: $p|n^{ n+1}+(n+1)^n.$ (September 29, 2012, Hohhot)
Problem
Source: China Western Mathematical Olympiad 2012 P8
Tags: number theory proposed, number theory
29.09.2012 10:55
all primes except $2$ satisfies the problem's condition. step 1) $2$ doesn't work. it's obvious step 2) if for a prime $p$ there exist such $n$ then there exist infinitely many of them.consider numbers in the form $n+k.p.\varphi (p)$ for all natural numbers $k$ step 3)for an arbitrary odd prime number $p$ there exist such $n$. proof:assume that order of $2$ modulo $p$ is $d$.then let $n$ to be in the form $pk-2$ then we want to define $k$.so $p \mid (pk-2)^{pk-1}+(pk-1)^{pk-2}$ or $p \mid (-2)^{pk-1}+(-1)^{pk-2}$ since $pk-1 , pk-2$ have different parities so $p \mid 2^{pk-1}-1$.here we want to choose $k$ such that $d \mid pk-1$.this $k$ obviously exists because $(d , p)=1$ so we are done
02.10.2012 14:43
Just choosing $n=(pm+1)(p-1)-1$ we're done.
18.04.2013 14:16
mlm95 wrote: obviously exists because $(d , p)=1$ so we are done Does there exist infinitely many such $ k $?
18.02.2015 04:08
Since $n^{n+1}+(n+1)^n$ is odd so we must have $p$ is odd. We will show that for all odd primes $p$ there exist infinite number of positive integers $n$ such that $p | n^{n+1}+(n+1)^n.$ For a given odd prime $p$ we will choose $n=(p-2)^{p^j}$ where $j$ is any natural number. It is easy to see $p | (n+1)^n+1$ and $p | n^{n+1}-1$. Hence we are done.