Determine the total number of positive integer values of N < 20150 such that:
2^N - N² is divisible by 17

This was more complicated than I thought.
Consider the moduli of  2^N and N² mod 17:

N   2N  N2 
0   1   0
1   2   1
2   4   4 *
3   8   9
4  16  16 *
5  15   8
6  13   2
7   9  15
8   1  13
9   2  13
10  4  15
11  8   2
12 16   8
13 15  16
14 13   9
15  9   4
16  1   1 *
17      0

2^N and N² each have cycles of different length.  2^N is length 16 whereas N² is length 17.  So it's really only every 16*17=272 steps that the great-cycle of their difference repeats. 

For 2^N - N² to be divisible by 17, their moduli must be equal, which I will refer to as a match up.

The N² cycle contains every number in the 2^N twice plus an extra 0.  As the two cycles overlap, each number in N² cycle will twice match up with a number from the 2^N cycle (except for the 0) so we have 16*2=32 match ups per great-cycle.

20150/272 = 74 + 22/272

32*74=2368 match ups in the 74 full great-cycles. 

The 22 extra steps have 3 more match-ups -- those marked by * in the table (the next actually occurs at 21)

Final tally: 2368+3=2371

Posted by Jer on 2015-08-13 10:38:31