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

No vote yet

1 vote

×

Problem Loading...

Note Loading...

Set Loading...

## 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 :)

Log in to reply

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

This is exactly what I did but I left it in the middle :/..... Thanks a lot @Michael Ng

Log in to reply

But can you prove why?

Log in to reply

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

Log in to reply

Log in to reply

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

Log in to reply

Log in to reply

Log in to reply

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\)?

Log in to reply

@Daniel Liu @Finn Hulse

Log in to reply

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

Log 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... :( :/

Log in to reply

Finn, once you come back don't forget to solve it.@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 :)

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

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}\).

Log in to reply

Log in to reply

Log in to reply

Log 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?

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

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.

Log in to reply

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.

Log in to reply

Log in to reply

Log 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

Log in to reply

Sorry @Krishna Ar! :O

Log in to reply