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

#NumberTheory #HelpMe! #Help #brillianthelp #Pleasehelp

Easy Math Editor

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.
Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

Markdown	Appears as
`italics` or `_italics_`	italics
`bold` or `__bold__`	bold
- bulleted - list	bulleted list
1. numbered 2. list	numbered list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1 paragraph 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"

Math	Appears 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}$

Comments

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 - 7 years ago

But can you prove why?

Finn Hulse - 7 years 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...

Krishna Ar - 7 years 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.

Michael Ng - 7 years ago

@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 - 7 years ago

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

Krishna Ar - 7 years ago

@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 - 7 years ago

@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 - 7 years ago

@Krishna Ar – I did the same as Michael just I proved why they cycled.

Finn Hulse - 7 years ago

@Finn Hulse – What more needs to be proved? o.O?

Krishna Ar - 7 years ago

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

Krishna Ar - 7 years 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).....???

Krishna Ar - 7 years 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$ ?

Finn Hulse - 7 years ago

@Daniel Liu @Finn Hulse

Krishna Ar - 7 years 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

Finn Hulse - 7 years 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 :)

Krishna Ar - 7 years ago

@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 - 7 years ago

@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 - 7 years ago

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

Finn Hulse - 7 years ago

@Daniel Liu – Oh! Yes! You're right ...how lame of me :(

Krishna Ar - 7 years ago

@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 - 7 years ago

@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 - 7 years ago

@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 - 7 years ago

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

Krishna Ar - 7 years ago

@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 - 7 years ago

@Daniel Liu – Exactly....somewhere online maybe...You know where?

Krishna Ar - 7 years ago

@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 - 7 years ago

@Finn Hulse – I got this problem form a book called Mathematical Adventures

Krishna Ar - 7 years 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... :( :/

Krishna Ar - 7 years 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

Finn Hulse - 7 years ago

Sorry @Krishna Ar! :O

Finn Hulse - 7 years ago

Math	Appears 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}$