Counting down to 2016

Let $M = 2015^{2016} - 1$ .

First we will examine the case when $n$ is prime or a prime power. For $n=7,17,19,29$ , we see that $n-1$ divides $2016=2^53^27$ , so that $n|M$ by Fermat. Likewise, $\phi(2^4)=8$ and $\phi(3^3)=18$ divide 2016, so that $2^4|M$ and $3^3|M$ by Euler.

The prime factors $5,13,31$ of 2015 will not divide $M$ since they divide $M+1$ . We can verify that the two remaining primes, 11 and 23, do not divide $M$ . For example , $2015^{2016}\equiv 2^6=64\equiv 9 \pmod{11}$ so that $M\equiv 8 \pmod{11}$ .

Thus the integers $n\leq 31$ that do not divide $M$ are the primes $5,11,13,23,31$ and their multiples $10,15,20,25,30,22,26$ . The remaining $31-5-7=\boxed{19}$ integers do divide $M$ .

Why should the number one(1) be included? the answer should be 18.

We have to find positive integers 'n' less than or equal to 31 such that 2015^2016 is congruent to 1 mod n. Firstly, we note that 2015 = 5×13×31. We will use Euler's theorem. We fist find all the n < 32 such that gcd(n,2015) = 1. Later, for each n, we check if phi(n) divides 2016. Where phi(n) is the Euler totient function. And the number of such 'n' is the required number.