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

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

• Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
• Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
• Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold
- bulleted- list
• bulleted
• list
1. numbered2. list
1. numbered
2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in $$ ... $$ or $ ... $ to ensure proper formatting.
2 \times 3 $2 \times 3$
2^{34} $2^{34}$
a_{i-1} $a_{i-1}$
\frac{2}{3} $\frac{2}{3}$
\sqrt{2} $\sqrt{2}$
\sum_{i=1}^3 $\sum_{i=1}^3$
\sin \theta $\sin \theta$
\boxed{123} $\boxed{123}$

Sort by:

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

- 7 years, 2 months ago

But can you prove why?

- 7 years, 2 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...

- 7 years, 2 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.

- 7 years, 2 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. :O

- 7 years, 2 months ago

Yes, so could you please tell me how to do so? I would be grateful

- 7 years, 2 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.

- 7 years, 2 months ago

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

- 7 years, 2 months ago

I did the same as Michael just I proved why they cycled.

- 7 years, 2 months ago

What more needs to be proved? o.O?

- 7 years, 2 months ago

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

- 7 years, 2 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).....???

- 7 years, 2 months ago

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

- 7 years, 2 months ago

- 7 years, 2 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. :D

- 7 years, 2 months ago

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

- 7 years, 2 months ago

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

- 7 years, 2 months ago

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}$.

- 7 years, 2 months ago

Yeah okay. If Daniel says it's true, it's probably true. :D

- 7 years, 2 months ago

Oh! Yes! You're right ...how lame of me :(

- 7 years, 2 months ago

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

- 7 years, 2 months ago

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

- 7 years, 2 months ago

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.

- 7 years, 2 months ago

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

- 7 years, 2 months ago

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.

- 7 years, 2 months ago

Exactly....somewhere online maybe...You know where?

- 7 years, 2 months ago

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

- 7 years, 2 months ago

I got this problem form a book called Mathematical Adventures

- 7 years, 2 months ago

@Finn Hulse - Don't tell me that you have school in May also. Then when would you have vacations? Life in India totally sucks... :( :/

- 7 years, 2 months ago

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

- 7 years, 2 months ago

Sorry @Krishna Ar! :O

- 7 years, 2 months ago