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

Home > Just Math
Power and Divisibility Puzzle (Posted on 2015-08-12) Difficulty: 3 of 5
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 |
(In reply to re(2): computer solution by Ady TZIDON)

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
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (9)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information