mathschallenge.net

Problem

Consider the expression $x^x + 1$, where $x$ be a positive integer.

It can be verified that $x = 7$ is the least value for which $x^x + 1$ divides by $2^3$.

Given that $n$ is a positive integer, find the least value of $x$ for which $x^x + 1$ is divisible by $2^n$.

Solution

As $n \ge 1$, $2^n$ will be even and for $x^x + 1$ to be even it is clear that $x$ must be odd.

Consider the following factorisations:

$x^3 + 1 = (x + 1)(x^2 - x + 1)$
$x^5 + 1 = (x + 1)(x^4 - x^3 + x^2 - x + 1)$
$x^7 + 1 = (x + 1)(x^6 - x^5 + x^4 - x^3 + x^2 - x + 1)$

That is, for odd values of $x$, $x^x + 1 = (x + 1)(x^{x-1} - x^{x-2} + x^{x-3} - ... + x^2 - x + 1)$.

Each term in the second bracket will be odd and as $x$ is odd there will be an odd number of terms creating an odd sum. Hence $x^x + 1$ will be divisible by $2^n$ if and only if it divides $x + 1$.

Thus $x = 2^n - 1$ is the least value for which $x^x + 1$ is divisible by $2^n$.