Waste less time on Facebook — follow Brilliant.
×

Help for a problem

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

Note by Krishna Ar
3 years, 2 months ago

No vote yet
1 vote

Comments

Sort by:

Top Newest

Hi 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 · 3 years, 2 months ago

Log in to reply

@Michael Ng 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).....??? Krishna Ar · 3 years, 2 months ago

Log in to reply

@Michael Ng This is exactly what I did but I left it in the middle :/..... Thanks a lot @Michael Ng Krishna Ar · 3 years, 2 months ago

Log in to reply

@Michael Ng But can you prove why? Finn Hulse · 3 years, 2 months ago

Log in to reply

@Finn Hulse 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. Michael Ng · 3 years, 2 months ago

Log in to reply

@Michael Ng 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. :O Finn Hulse · 3 years, 2 months ago

Log in to reply

@Finn Hulse Yes, so could you please tell me how to do so? I would be grateful Krishna Ar · 3 years, 2 months ago

Log in to reply

@Krishna Ar 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. Daniel Liu · 3 years, 2 months ago

Log in to reply

@Daniel Liu No I'm saying how can you prove that it is indeed a pattern? Like how can you tell

\[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 · 3 years, 2 months ago

Log in to reply

@Krishna Ar I did the same as Michael just I proved why they cycled. Finn Hulse · 3 years, 2 months ago

Log in to reply

@Finn Hulse What more needs to be proved? o.O? Krishna Ar · 3 years, 2 months ago

Log in to reply

@Finn Hulse 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... Krishna Ar · 3 years, 2 months ago

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 · 3 years, 2 months ago

Log in to reply

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

Log in to reply

@Krishna Ar Wow this is an excellent problem. I'll have to take a look at it later though, I have to go to school. :D Finn Hulse · 3 years, 2 months ago

Log in to reply

@Finn Hulse @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 · 3 years, 2 months ago

Log in to reply

@Finn Hulse 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 :) Krishna Ar · 3 years, 2 months ago

Log in to reply

@Krishna Ar Okay. Wow a lot of comments for improvement lately from me. Yay! Okay, here's how you can solve the problem. Here's how I would do the problem given. You could count them all, but the cool way is to factor

\[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 · 3 years, 2 months ago

Log in to reply

@Finn Hulse Yes, I think you did it correctly.

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 · 3 years, 2 months ago

Log in to reply

@Daniel Liu Oh! Yes! You're right ...how lame of me :( Krishna Ar · 3 years, 2 months ago

Log in to reply

@Krishna Ar Dude it's okay. I'm constantly failing on all sorts of things. By the way where did you get that problem? Finn Hulse · 3 years, 2 months ago

Log in to reply

@Finn Hulse I got this problem form a book called Mathematical Adventures Krishna Ar · 3 years, 2 months ago

Log in to reply

@Finn Hulse @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 · 3 years, 2 months ago

Log in to reply

@Krishna Ar I dunno usually I fail but I've gotten exponentially better. It used to be me asking @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 · 3 years, 2 months ago

Log in to reply

@Krishna Ar Well, I was sometimes coached, but I usually just learned them myself. Have you tried reading the Art of Problem Solving book series? They have extremely helpful books! I suggest Volume 1, it's great.

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

Log in to reply

@Daniel Liu Thanks a lot! :D But unfortunately these books are NEVER available in India ... ::( ..... life here sucks :'( Krishna Ar · 3 years, 2 months ago

Log in to reply

@Krishna Ar AoPS ship their books worldwide. You can see their books here.

However, 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 · 3 years, 2 months ago

Log in to reply

@Daniel Liu Exactly....somewhere online maybe...You know where? Krishna Ar · 3 years, 2 months ago

Log in to reply

@Daniel Liu Yeah okay. If Daniel says it's true, it's probably true. :D Finn Hulse · 3 years, 2 months ago

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 Finn Hulse · 3 years, 2 months ago

Log in to reply

@Finn Hulse Sorry @Krishna Ar! :O Finn Hulse · 3 years, 2 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...