A community for students. Sign up today!
Here's the question you clicked on:
 0 viewing
 one year ago
\[\sum_{k = 1}^{1000} 2^{(k!)!} \equiv n\pmod{1000}\]\(n\) is a threedigit number.
 one year ago
\[\sum_{k = 1}^{1000} 2^{(k!)!} \equiv n\pmod{1000}\]\(n\) is a threedigit number.

This Question is Closed

ParthKohli
 one year ago
Best ResponseYou've already chosen the best response.0@amistre64 Phi function?

ParthKohli
 one year ago
Best ResponseYou've already chosen the best response.0Well, \((k!)!\) would be divisible by all positive numbers under \((k!)!\)

ParthKohli
 one year ago
Best ResponseYou've already chosen the best response.0How can I proceed with that information?

amistre64
 one year ago
Best ResponseYou've already chosen the best response.0well, the sum of mods reduces each term .. might be useful. 23 = k (mod 3) k = 2; since 3(7) + 2 = 23 23 = 3+3+3+3+3+3+3+2 3+3+3+3+3+3+3+2 = k (mod 3) 0+0+0+0+0+0+0+2 = k (mod 3) k = 2

amistre64
 one year ago
Best ResponseYou've already chosen the best response.0im not sure how applicable the phi function might be, is it stated in the question by chance? or was that just an idea of yours?

ParthKohli
 one year ago
Best ResponseYou've already chosen the best response.0Yup, know that property. :)

ParthKohli
 one year ago
Best ResponseYou've already chosen the best response.0Or would it be recognizing some pattern?

amistre64
 one year ago
Best ResponseYou've already chosen the best response.0it might be patternable ... if your mod reductions simplify down to a repetition what are the first 10 terms .. or 5 terms?

amistre64
 one year ago
Best ResponseYou've already chosen the best response.01!, 2!, 6!, 24!, 120!, 720!, .... that can be a nightmare, but might be reduceable by phis

ParthKohli
 one year ago
Best ResponseYou've already chosen the best response.0a1 = 2 = 0 (mod 1000) a2 = 4 = 4 (mod 1000) a3 = 2^(720!) = O_O (mod 2)

ParthKohli
 one year ago
Best ResponseYou've already chosen the best response.0a3 = 2^(6!) = 2^(720) sorry

ParthKohli
 one year ago
Best ResponseYou've already chosen the best response.02^(1!) = 2 = 2 (mod 1000) 2^(2!) = 4 = 4 (mod 1000) 2^(3!) = 64 = 64 (mod 1000) 2^(4!) = 216 (mod 1000) Hmm

ParthKohli
 one year ago
Best ResponseYou've already chosen the best response.0Do you see any pattern? o_O

amistre64
 one year ago
Best ResponseYou've already chosen the best response.0not yet ... when does 2^n equal a multiple of 1000? i know 2^10 = 1024, which is 24 mod 1000

ParthKohli
 one year ago
Best ResponseYou've already chosen the best response.02^2 = 4 4^3 = 64 64^4 has the last three digits 216 216^5 has last three digits equal to 216

amistre64
 one year ago
Best ResponseYou've already chosen the best response.0lol, dont look at this: http://www.wolframalpha.com/input/?i=2%5E%28n%21%29%21%2C+n%3D1..3

ParthKohli
 one year ago
Best ResponseYou've already chosen the best response.0Superexponential function! :O

amistre64
 one year ago
Best ResponseYou've already chosen the best response.0i see a pollard factorization method that might be useful ... but might not

ParthKohli
 one year ago
Best ResponseYou've already chosen the best response.0Dag nab those fancy names.

amistre64
 one year ago
Best ResponseYou've already chosen the best response.02^(p1)=1 (mod p) per fermat little thrm.

amistre64
 one year ago
Best ResponseYou've already chosen the best response.0if k! = (p1)q for some interger q, then that reduces to 1 mod p

ParthKohli
 one year ago
Best ResponseYou've already chosen the best response.0Is there anything to do now? :\

ParthKohli
 one year ago
Best ResponseYou've already chosen the best response.0Oh.\[k! \equiv 2^{(p  1)} \pmod{p}\]Is it so?

amistre64
 one year ago
Best ResponseYou've already chosen the best response.0thats fermats little thrm i believe

ParthKohli
 one year ago
Best ResponseYou've already chosen the best response.0Were you able to solve it then?

ParthKohli
 one year ago
Best ResponseYou've already chosen the best response.0Gotta sleep, or rather: gotta sleep on the problem. ;) If you have any solution, feel free to post.

ParthKohli
 one year ago
Best ResponseYou've already chosen the best response.0Thanks for your time!

amistre64
 one year ago
Best ResponseYou've already chosen the best response.0me? no, i got no idea what the solution would be for this. number theory is too far behind and too little used for me to think clearly about it.

ParthKohli
 one year ago
Best ResponseYou've already chosen the best response.0Thanks anyway sire!

amistre64
 one year ago
Best ResponseYou've already chosen the best response.0ive got my elementary number theory textbook that im looking thru, and might be able to determine something in about a day :)

ParthKohli
 one year ago
Best ResponseYou've already chosen the best response.0@experimentX Any ideas on this one?

experimentX
 one year ago
Best ResponseYou've already chosen the best response.2I don't know ... but let me see.

ParthKohli
 one year ago
Best ResponseYou've already chosen the best response.0What does Mathematica compute?

ParthKohli
 one year ago
Best ResponseYou've already chosen the best response.0Oh . . . what do you mean by overflow? It isn't able to compute it due to the hugeness?

ParthKohli
 one year ago
Best ResponseYou've already chosen the best response.0Darn. I thought Mathematica was smart.

experimentX
 one year ago
Best ResponseYou've already chosen the best response.2Let me try finding the sum of mods first

ParthKohli
 one year ago
Best ResponseYou've already chosen the best response.0Yeah, try it onebyone, maybe we can find some pattern. Actually we did above, but let's see what we get for the further values.

experimentX
 one year ago
Best ResponseYou've already chosen the best response.2Sum[Mod[2^((i!)!), 1000], {i, 1, 1000}]

experimentX
 one year ago
Best ResponseYou've already chosen the best response.2returns overflow in computation ... let me try on matlab.

experimentX
 one year ago
Best ResponseYou've already chosen the best response.2looks like application of Euler totient function. but let me compute it numerically first.

ParthKohli
 one year ago
Best ResponseYou've already chosen the best response.0But it would get harder and harder to compute \(\phi((n!)!)\) as \(n\) increases. :

experimentX
 one year ago
Best ResponseYou've already chosen the best response.2trust me .. I don't know that ... I am least experience with number theory.

experimentX
 one year ago
Best ResponseYou've already chosen the best response.2damn!! even sum of these numbers is huge digit ... returns NaN

ParthKohli
 one year ago
Best ResponseYou've already chosen the best response.0@Callisto Hi, any ideas?

ParthKohli
 one year ago
Best ResponseYou've already chosen the best response.0Try calculating modulo 1000? Just an idea...

experimentX
 one year ago
Best ResponseYou've already chosen the best response.2bug on my code .. :(((

ParthKohli
 one year ago
Best ResponseYou've already chosen the best response.0Well, it's more like pattern recognition, I guarantee you that.

experimentX
 one year ago
Best ResponseYou've already chosen the best response.2yeah i know ... my code was correct ,,, just 2^(,,(..)) is such a huge number. i guess Bigger than grahms number.

ParthKohli
 one year ago
Best ResponseYou've already chosen the best response.0But still lesser than Googol.

experimentX
 one year ago
Best ResponseYou've already chosen the best response.2Grahams number is bigger than googol

experimentX
 one year ago
Best ResponseYou've already chosen the best response.2numerically it's a fiasco ... let me look for totient function.

experimentX
 one year ago
Best ResponseYou've already chosen the best response.2I never used Totient function on my entire life. ... looks like worth it.

experimentX
 one year ago
Best ResponseYou've already chosen the best response.2freaking group theory is again here.

experimentX
 one year ago
Best ResponseYou've already chosen the best response.2up until now I managed to calculate 2^1000! mod 1000 numerically.

experimentX
 one year ago
Best ResponseYou've already chosen the best response.2A very interesting property \[ a^{\phi (n)} = a^{mn} = k \mod n \] So the problem is asking, for what value of \( k \ge n \), \((k!)! = 0 \mod \phi(1000)\)

experimentX
 one year ago
Best ResponseYou've already chosen the best response.2The answer is 454 ... Amazing, Apart for Euler theorem I managed to learn Euclid algorithm, System of linear congruence, Chinese Remainder theorem, ...

ParthKohli
 one year ago
Best ResponseYou've already chosen the best response.0Is there a CRT here too?!

experimentX
 one year ago
Best ResponseYou've already chosen the best response.2oh ... just step for understanding Euler's theorem. I have never done number theory in my entire life.

ParthKohli
 one year ago
Best ResponseYou've already chosen the best response.0I see, number theory and contest mathematics combined is pretty hard!

experimentX
 one year ago
Best ResponseYou've already chosen the best response.2quite hard ... i often have difficulty doing problems on most of them.
Ask your own question
Ask a QuestionFind more explanations on OpenStudy
Your question is ready. Sign up for free to start getting answers.
spraguer
(Moderator)
5
→ View Detailed Profile
is replying to Can someone tell me what button the professor is hitting...
23
 Teamwork 19 Teammate
 Problem Solving 19 Hero
 Engagement 19 Mad Hatter
 You have blocked this person.
 ✔ You're a fan Checking fan status...
Thanks for being so helpful in mathematics. If you are getting quality help, make sure you spread the word about OpenStudy.