All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 Power and Divisibility Puzzle (Posted on 2015-08-12)
Determine the total number of positive integer values of N < 20150 such that:
2N - N2 is divisible by 17

 No Solution Yet Submitted by K Sengupta No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
 re(3): computer solution | Comment 4 of 6 |

2^N mod 17 has a cycle of 8:

1,2,4,8,16,15,13,9, repeat
n^2 mod 17 has a cycle of 17:
0,1,4,9,16,8,2,15,13,13,15,2,8,16,9,4,1, repeat

We are looking for values of n where the two match
Consider the cycle of 17.
1 of the values (0) can never match.
For the other 16 values, they match one time out of 8.  Altogether, they match 2 times out of 17 for a complete cycle of 8*17 = 136 consecutive n.
In other words, they match 16 times in any set of 136 consecutive n.  Which explains the result.

The first ones that match are n = 2,4,16,31

 Posted by Steve Herman on 2015-08-13 10:24:46

 Search: Search body:
Forums (0)