This is an easy problem i guess..but don't know why I haven't made much headway in it. Would appreciate a clear solution t this :).

Find the number of natural numbers strictly not greater than 10000 such that 2^n-n^2 is divisible by 7.

I analyzed using mod upto 20 and found 5 cases positive but after that I found there was no consistent pattern and left it.

I would kindly request one and all to come forward and solve this. Thanks

## Comments

Sort by:

TopNewestHi Krishna, here is a solution: Make a table with \(n, 2^n, n^2\) as the headings. Then evaluate these values in mod 7 from n=1 to n=21. When \(2^n \bmod 7 = n^2 \bmod 7\), then \(2^n-n^2\) must be divisible by 7.

You find that \(2^n\) cycles (2,4,1) every three, \(n^2\) cycles (1,4,2,2,4,1,0) every seven. Hence the values of \((2^n-n^2) \bmod 7\) cycle every 21. In every cycle, you find that \(2^n \bmod 7 = n^2 \bmod 7\) 6 times, hence from 1 to 10000 this would happen 10000/21*6 = 2856 times, plus the two more times at n=9998, 10000, hence the answer is 2860.

Hopefully my working was correct, but if it is isn't, I hope you know how to solve it now :) – Michael Ng · 2 years, 8 months ago

Log in to reply

– Krishna Ar · 2 years, 8 months ago

Exactly. I did uptil 20 and found 5 cases positive. After a chain till 21, yes there are 6 positive cases. And does this completely prove that if there are two cycles( here- n^2 and 2^n) you have to multiply them to find something like a net cyclicity ( here we multiplied 3 and 7 to get 21).....???Log in to reply

@Michael Ng – Krishna Ar · 2 years, 8 months ago

This is exactly what I did but I left it in the middle :/..... Thanks a lotLog in to reply

– Finn Hulse · 2 years, 8 months ago

But can you prove why?Log in to reply

– Michael Ng · 2 years, 8 months ago

Hi Finn and Krishna, the cycles of three and seven repeat every 21 because 21 is the LCM of 3 and 7. In fact, the LCM of any two coprime integers is their product.Log in to reply

– Finn Hulse · 2 years, 8 months ago

No no no dude that's obvious but can you prove exactly why it's a pattern and not just by guesswork? In olympiads you can never just say "and it's a pattern etc." and hope to do well. :OLog in to reply

– Krishna Ar · 2 years, 8 months ago

Yes, so could you please tell me how to do so? I would be gratefulLog in to reply

– Daniel Liu · 2 years, 8 months ago

They cycle at \(21\) because \(\text{lcm}(3,7)=21\). I don't really see why there needs to be any more proving to do here.Log in to reply

\[1, 2, 3, 1, 2, 3, \dots\]

is a pattern without knowing the next term? You're just making an educated guess. :P – Finn Hulse · 2 years, 8 months ago

Log in to reply

– Finn Hulse · 2 years, 8 months ago

I did the same as Michael just I proved why they cycled.Log in to reply

– Krishna Ar · 2 years, 8 months ago

What more needs to be proved? o.O?Log in to reply

– Krishna Ar · 2 years, 8 months ago

Hi! In what way did you approach the problem? Was it not by this method?.... And dude, you must tell me about the Mathcounts too.. how to improve in those kind of problems and al...Log in to reply

I'm going to rewrite it with \(\LaTeX\) so I can get a better feel for the problem. :D

\[7 \mid 2^n-n^2\]

And just for clarification, is \(n\) less than \(10000\) or is the expression less than \(10000\)? – Finn Hulse · 2 years, 8 months ago

Log in to reply

@Daniel Liu @Finn Hulse – Krishna Ar · 2 years, 8 months ago

Log in to reply

– Finn Hulse · 2 years, 8 months ago

Wow this is an excellent problem. I'll have to take a look at it later though, I have to go to school. :DLog in to reply

@Finn Hulse - Don't tell me that you have school in May also. Then when would you have vacations? Life in India totally sucks... :( :/ – Krishna Ar · 2 years, 8 months ago

Log in to reply

@Daniel Liu YOU TOO :p.. And both of you, please tell me how to solve problems in Mathcounts with expertise like you. I couldn't solve even problems like these - " find the number of numbers that divide 6^2014 but not 6^2013." Hoping that you would help :) – Krishna Ar · 2 years, 8 months ago

Finn, once you come back don't forget to solve it.Log in to reply

\[2015^2-2014^2=4029 \times 1=4029\]

to get the answer. @Daniel Liu I think I did this right, right? Anyways that's just the number of factors of \(6^{2014}\) minus the number of factors of \(6^{2013}\) so really not too hard. :D – Finn Hulse · 2 years, 8 months ago

Log in to reply

To summarize, the numbers hat divide \(6^{2014}\) but not \(6^{2013}\) is the number of factors of \(6^{2014}\) minus the number of factors of \(6^{2013}\). – Daniel Liu · 2 years, 8 months ago

Log in to reply

– Krishna Ar · 2 years, 8 months ago

Oh! Yes! You're right ...how lame of me :(Log in to reply

– Finn Hulse · 2 years, 8 months ago

Dude it's okay. I'm constantly failing on all sorts of things. By the way where did you get that problem?Log in to reply

– Krishna Ar · 2 years, 8 months ago

I got this problem form a book called Mathematical AdventuresLog in to reply

@Finn Hulse @Daniel Liu - Sorry for tagging you people repeatedly... I wanted to know whether you guys get coached for solving these types of problems..or else how do you do so? – Krishna Ar · 2 years, 8 months ago

Log in to reply

@Daniel Chiu for advice just like you but now it's reversed! But as far as advice goes, keep a running tab on what you DON'T know, and try to learn it. Get really down and dirty with one topic, and make it perfect. For example, I just finished with tangent spheres/sectors and stuff dealing with circles. :D – Finn Hulse · 2 years, 8 months ago

I dunno usually I fail but I've gotten exponentially better. It used to be me askingLog in to reply

Also, search up "Competition Math for Middle School" by Batterson. That's also a good book. – Daniel Liu · 2 years, 8 months ago

Log in to reply

– Krishna Ar · 2 years, 8 months ago

Thanks a lot! :D But unfortunately these books are NEVER available in India ... ::( ..... life here sucks :'(Log in to reply

here.

AoPS ship their books worldwide. You can see their booksHowever, international shipping does cost a hefty amount (about 40 USD) so you might want to see if you can get a copy of the book somewhere else. – Daniel Liu · 2 years, 8 months ago

Log in to reply

– Krishna Ar · 2 years, 8 months ago

Exactly....somewhere online maybe...You know where?Log in to reply

– Finn Hulse · 2 years, 8 months ago

Yeah okay. If Daniel says it's true, it's probably true. :DLog in to reply

NO! I just spent an hour writing a huge solution, and then deleted one of my other comments and my solution disappeared! @Silas Hundt I'm so mad! :O – Finn Hulse · 2 years, 8 months ago

Log in to reply

@Krishna Ar! :O – Finn Hulse · 2 years, 8 months ago

SorryLog in to reply