Largest integer less than 999 with $(n-1)^2\mid n^{2016}-1$

Question

What is the largest integer $n<999$ such that $(n-1)^2$ divides $n^{2016}-1$?

I don't know how to approach this problem, I have tried factoring $n^{2016}-1$, do I randomly pick factors and try to guess the number?

Answer 1

$n-1$ divides $n^k-1$ automatically for nonnegative integer $k$, so we need the largest three-digit $n$ with $$n-1\mid 1+n+n^2+\dots+n^{2015}$$ Now $n^k\equiv1\bmod n-1$ and there are 2016 such powers in $\frac{n^{2016}-1}{n-1}$, so $n-1\mid 2016$. The largest three-digit factor of 2016 is $2016/3=672$, so the required $n$ is 673.

Answer 2

Let $n-1=m$

so $m^2$ divides $(m+1)^{2016}-1=m^2\sum_{r=2}^m\binom{2016}rm^{r-2}+\binom{2016}1m$

So, we need $m|2016$

Answer 3

Note: $$\frac{n^{2016}-1}{(n-1)^2}=\frac{(n-1)(1+n+n^2+\cdots +n^{2015})}{(n-1)^2}=\\ \frac{1+(n-1+1)+(n^2-1+1)+\cdots +(n^{2015}-1+1)}{n-1}=\\ \frac{1}{n-1}+\left(1+\frac{1}{n-1}\right)+\left(n+1+\frac{1}{n-1}\right)+\cdots+\left(n^{2014}+n^{2013}+\cdots +1+\frac{1}{n-1}\right)=\\ \frac{2016}{n-1}+1+(n+1)+\cdots (n^{2014}+n^{2013}+\cdots +1).$$ The divisors of $2016$ are: $$1;2;3;4;6;7;8;9;\\ 12;14;16;18;21;24;28;32;36;42;48;56;63;72;84;96;\\ 112;126;144;168;224;252;288;336;504;672;1008;2016.$$ So, the largest three digit number is: $$n-1=672 \Rightarrow n=673.$$