Nice! As usual, let $ v_p(n)$ be the unique integer satisfying $ p^{v_p(n)}||n$ ($ p$ - prime), and $ ord_p(a,b) = \min \{ x \ge 1: p|a^x - b^x\}$ (the set $ \min \{ x \ge 1: p|a^x - b^x\}$ consists of all the multiplies of $ ord_p(a,b)$) ($ a,b$ are coprime non-zero integers). A well-known theorem states: for odd prime $ p$, if $ p|a^n - b^n$: $ v_p(a^n - b^n) = v_p(a^{ord_p(a,b)} - b^{ord_p(a,b)}) + v_p(\frac {n}{ord_p(a,b)})$. We'll use this theorem with $ b = - 1$. Notice that $ ((n - 1)^n + 1)^2$ is odd, hence divisible only by odd primes. Let $ x = (n - 1)^n + 1$. We need to show $ x^2|n((n - 1)^x + 1)$. Cleary, $ x = (n - 1)^n + 1|(n - 1)^x + 1$, since $ n|x$ ($ n$ is odd). It is enough to show that $ v_p(x) = t\ge 1 \implies v_p(n((n - 1)^x + 1)) \ge 2t$. Let $ ord_p(n - 1, - 1) = k$. $ v_p(x) = t\ge 1 \implies t = v_p(\frac {n}{k}) + v_p((n - 1)^{k} - ( - 1)^{k})$ $ (*)$. $ v_p(n((n - 1)^x + 1)) = v_p(n) + v_p(\frac {x}{k}) + v_p((n - 1)^{k} - ( - 1)^{k})$ Hence, we need to show that $ v_p(n) + v_p(\frac {x}{k}) + v_p((n - 1)^{k} - ( - 1)^{k}) \ge 2(v_p(\frac {n}{k}) + v_p((n - 1)^{k} - ( - 1)^{k}))$ Or (using $ v_p(ab) = v_p(a) + v_p(b)$, etc.): $ v_p(x) \ge v_p(\frac {n}{k}) + v_p((n - 1)^{k} - ( - 1)^{k})$ And from $ (*)$, we even have equality! Which means that $ (\frac {RHS}{LHS}, LHS) = 1$. If $ n$ is even, must of our arguments fail. Already for $ n = 4$ we get $ 41^2 | 9^{41} + 1$, which doesn't hold since by Fermat's Little Thereom: $ 9^{41} + 1 = 9 + 1 = 10 \pmod {41}$.

bambaman could you give me a link where I can find a proof of this well-known theorem?

It's lifting the exponent lemma. Google it

Thanks

Just to make it a bit more clear - let $ f_{a,b}(n) = a^n - b^n$. Then this problem is: \[ f_{a,b}(x) | \frac {xf_{a,b}(f_{a,b}(x))}{f_{a,b}(x)}\] with $ a = n - 1, b = - 1, x = f_{a,b}(1)$ Claim: $ f_{a,b}(x) | \frac {xf_{a,b}(f_{a,b}(x))}{f_{a,b}(x)}$ holds for $ x$ such that $ x|f_{a,b}(x)$ and $ a \neq b \pmod 2$. Proof: for $ p|f_{a,b}(x)$ we have: $ v_p(\frac {xf_{a,b}(f_{a,b}(x))}{f_{a,b}(x)}) = v_p(x) + v_p(\frac {f_{a,b}(x)}{x}) = v_p(f_{a,b}(x))$, and that's enough. In our case, $ x = f_{a,b}(1) | f_{a,b}(x)$ and $ n - 1 \neq - 1 \pmod 2$ so we can apply the claim. We don't need the strong version of 'Lifting the exponent': it is enough to use $ v_p(\frac{a^n-b^n}{a-b})\ge v_p(n)$ (for odd $ p$ and $ a,b$ s.t. $ p \nmid a,b$ and $ p|a-b$) which follows directly from $ p|a-b \implies p|\frac{a^p-b^p}{a-b}$.

Added problem: Find all even n such that the statement is true for it.

click text

Prove that for any odd prime $ p$ that divides $ (n - 1)^n + 1$ we should have $ ord_{p}(n - 1) = 4$. Then deduce that $ 2||n$ and also conclude that the set of primes dividing $ (n - 1)^2 + 1$ and $ (n - 1)^n + 1$ must be the same.then because of this well-known problem (see http://www.mathlinks.ro/viewtopic.php?t=150413) we will have $ n = 2^k$ for some integer k. but we had $ 2||n$. so $ n = 2$. DONE!

Let $(n-1)^n+1$ have prime factors $p_1,p_2,\cdots, p_k.$ Note that since $(n-1)^n+1$ is odd, $p_1,p_2,\cdots,p_k$ are all odd. Further, since $n$ is odd, $(n-1)^n+1 \equiv (-1)^n + 1 \equiv 0 \pmod{n}$. Thus, we can write $$(n-1)^{(n-1)^n+1}+1 = ((n-1)^n)^{\frac{(n-1)^n+1}{n}} + 1.$$ Then, since we know $\left(\frac{(n-1)^n+1}{n}\right)$ is odd, and that $\forall i \in \{1,2,\cdots, k\}$ we have $p_i \mid (n-1)^n-(-1)$ and $\gcd(p_i, -(n-1)^n) = 1$, we can apply LTE to get \begin{align*} v_{p_i}(n(n-1)^{(n-1)^n+1}+n) &= v_{p_i}(n) + v_{p_i}\left((n-1)^{(n-1)^n+1}+1\right)\\ &= v_{p_i}(n) + v_{p_i}\left(((n-1)^n)^{\frac{(n-1)^n+1}{n}} - (-1)^{\frac{(n-1)^n+1}{n}}\right)\\ &= v_{p_i}(n) + v_{p_i}((n-1)^n - (-1)) + v_{p_i}\left(\frac{(n-1)^n+1}{n}\right)\\ &= v_{p_i}(n) + v_{p_i}((n-1)^n+1) + v_{p_i}((n-1)^n+1) - v_{p_i}(n)\\ &= 2v_{p_i}((n-1)^n+1)\\ &= v_{p_i}(((n-1)^n+1)^2). \end{align*} Thus, we have that $((n-1)^n+1)^2 \mid n(n-1)^{(n-1)^n+1}+n$, as desired.

Let $p \mid (n-1)^n + 1$, and note that $n \mid (n-1)^n + 1$ because $n$ is odd. Then by LTE, \begin{align*} \nu_p(n(n-1)^{(n-1)^n+1}+n) &= \nu_p(n) + \nu_p((n-1)^{(n-1)^n+1}+1) \\ &= \nu_p(n) + \nu_p((n-1)^n + 1)+ \nu_p\left(\frac{(n-1)^n+1}n\right) \\ &= \nu_p(n) + 2\nu_p((n-1)^n + 1)-\nu_p(n) \\ &= 2\nu_p((n-1)^n + 1), \end{align*}so it follows that $((n-1)^n+1)^2$ divides $n(n-1)^{(n-1)^n+1}+n$, as required.

Notice $(n-1)^n+1\equiv (-1)^n+1\equiv 0\pmod{n},$ so we can let $Sn=(n-1)^n+1,$ where $S\in\mathbb{Z}.$ We note $S$ is odd as $(n-1)^n+1$ is odd. We also see \begin{align*}n(n-1)^{(n-1)^n+1}+n&=n\left((n-1)^{(n-1)^n+1}+1\right)\\&=n((n-1)^{Sn}+1)\\&=n((n-1)^n+1)\left(\sum_{k=0}^{S-1}(-1)^k((n-1)^n)^k\right)\\&=((n-1)^n+1)n\left(\sum_{k=1}^{S-1}(-1)^k(Sn-1)^k\right)\end{align*}by sum of powers for odd exponents. Since $$\sum_{k=1}^{S-1}(-1)^k(Sn-1)^k\equiv\sum_{k=1}^{S-1}(-1)^{2k}\equiv 0\pmod{S},$$we see $(n-1)^n+1=nS\mid n\sum_{k=1}^{S-1}(-1)^k(Sn-1)^k.$ Multiplying both sides of the division by $(n-1)^n+1\mid (n-1)^n+1$ finishes. $\square$

Since $n$ is odd, $(n-1)^n+1$ is odd. By the binomial theorem, $n\mid (n-1)^n+1$. Additionally, $\frac{(n-1)^n+1}{n}$ is odd since $(n-1)^n+1$ is odd. Let $p$ be a prime dividing $(n-1)^n+1$. Note that $p$ is odd. By LTE, \begin{align*} \nu_p\left(n(n-1)^{(n-1)^n+1}+n\right)&=\nu_p(n)+\nu_p\left(((n-1)^n)^\frac{(n-1)^n+1}{n}-(-1)^\frac{(n-1)^n+1}{n}\right)\\ &=\nu_p(n)+\nu_p\left(\frac{(n-1)^n+1}{n}\right)+\nu_p((n-1)^n+1)\\ &=\nu_p\left(((n-1)^n+1)^2\right), \end{align*}as desired. $\square$

Look at the exponent ftw! ($v_p$ and LTE stuff are both really cool!) Case 1: $p$ is a prime s.t. $p \mid n$ Note that $v_p(((n-1)^n+1)^2)=2(v_p(n)+v_p(n))=4v_p(n)$ and $v_p(n(n-1)^{(n-1)^n+1}+n)=v_p(n)+v_p(n)+v_p((n-1)^n+1)=4v_p(n)$ therefore in this case we have $v_p(((n-1)^n+1)^2) \le v_p(n(n-1)^{(n-1)^n+1}+n)$ (in fact they are equal). Case 2: $p$ is a prime with $p \mid (n-1)^n+1$ but $p \not\; \mid n$ Then $v_p(((n-1)^n+1)^2)=2v_p((n-1)^n+1)$ and $v_p(n(n-1)^{(n-1)^n+1}+n)=v_p((n-1)^n)^{\frac{(n-1)^n+1}{n}}+1)=2v_p((n-1)^n+1)$ therefore we also have $v_p(((n-1)^n+1)^2) \le v_p(n(n-1)^{(n-1)^n+1}+n)$ (they are equal in fact) as desired. If $p$ did not divide $(n-1)^n+1$ then we don't need to check anything because LHS would be $0$. Therefore $((n-1)^n+1)^2 \mid n(n-1)^{(n-1)^n+1}+1$ as desired thus we are done