Is there a fixed positive integer for which $2^{2017} \mid n^n-2017$?

Question

I have checked to find a positive integer n for which :$2^{2017} \mid n^n-2017$ But I didn't get, I guess about Fermat little theorem using this idea if :$-1+2^{2017} \mid n^n-2018$ then $2^{2017} \mid n^n-2017$. Two cases I should treat, for $n$ even and odd, so: in the first we try to deal with: $2^{2017} |2k^{2k}-2017$, But now idea to study divisibility by this. Now Is there any way to show existence or non existence of a positive integer such that there is a fixed positive integer for which $2^{2017}\mid n^n-2017$?

Answer 1

If $n$ is even then $n^n-2017$ is odd and cannot be a multiple of a non-trivial power of $2$. So $n$ must be odd.

Using $\phi(2^{k+1})=2^k$ for $k\ge1$ and Euler, $$\tag1 (n+2^k)^{n+2^k}= (n+2^k)^n\cdot (n+2^k)^{2^k}\equiv (n+2^k)^n\pmod{2^{k+1}}$$ and $$\tag2(n+2^k)^n=n^n+{n\choose 1}n^{n-1}\cdot 2^k +\left(\cdots\right)\cdot2^{2k}\equiv n^n\cdot(2^k+1)\pmod{2^{k+1}}.$$

Assume thet $n^n\equiv 2017\pmod {2^k}$. Then there exists $m$ with $m^m\equiv 201\pmod{2^{k+1}}$: Indeed, either already $n^n\equiv 2017\pmod{2^{k+1}}$ and we can take $m=n$, or $n^n\equiv 2017+2^k\pmod{2^{k+1}}$ and from $(1)$ and $(2)$, we have $$(n+2^k)^{n+2^k}\equiv (2017+2^k)(2^k+1)=2017+2018\cdot 2^k+2^{2k}\equiv 2017\pmod{2^{k+1}} $$ so that $m^m\equiv 2017\pmod{2^{k+1}}$ with $m:=n+2^k$.

As $1^1\equiv 2017\pmod{2^1}$, it follows by induction that there for every natural $k$, there exists $n$ with $n^n\equiv 2017\pmod{2^k}$.

In fact, using this as a recipe, we arrive at $$\begin{align}n = 2,879,214, &740,256,591,173,006,874,828,800,460,767,\\ &993,061,340,172,419,727,801,780,189,441,\\ &777,858,355,464,095,813,878,763,077,078,\\ &707,828,746,027,430,436,884,325,107,483,\\ &231,645,013,652,031,890,712,628,660,652,\\ &382,916,312,094,740,631,739,589,839,968,\\ &983,466,456,741,375,380,587,136,311,182,\\ &741,166,346,627,215,704,818,549,017,474,\\ &615,836,980,286,258,097,410,543,624,182,\\ &414,893,115,529,901,235,482,662,654,296,\\ &008,684,993,592,400,643,258,908,066,826,\\ &081,309,469,837,725,387,624,916,241,805,\\ &459,185,972,698,949,924,633,669,564,906,\\ &802,777,948,657,836,740,725,140,493,879,\\ &654,322,663,393,687,072,004,201,866,772,\\ &611,932,290,631,534,682,102,128,952,718,\\ &147,830,715,003,140,870,603,217,259,141,\\ &888,575,011,134,612,454,307,904,386,009,\\ &243,920,673,274,212,820,657,861,714,448,\\ &124,909,943,939,883,841,513,372,337,121\end{align} $$ as a solution.

Answer 2

Yes.

We can actually show that for any $k$, there exists $n$ such that $n^n \equiv 2017 \pmod{2^k}$, by induction. Note that $2017 \equiv 1 \pmod{2^5}$. Also note that if exists, $n$ has to be odd.

If $k = 5$, let $n_5 = 1$ and we have ${n_5}^{n_5} \equiv 2017 \pmod{2^5}$.

If $k = 6$, take $n_6 = n_5 + 2^5m$. Then $$ \begin{aligned} n_6^{n_6} &= (n_5+2^5m)^{n_5} \times\left((n_5+2^5m) ^{2^5}\right)^m\\ &\equiv (n_5 + 2^5m)^{n_5} &&\text{(Euler's theorem)}\\ &\equiv n_5^{n_5} + 2^5m \pmod{2^6}. &&{\text{(Binomial theorem, and $n_5$ is odd)}} \end{aligned} $$

By either taking $m$ to be even or odd, you will find a suitable $n_6$.

Now proceed by induction.