\[\sum_{k = 1}^{1000} 2^{(k!)!} \equiv n\pmod{1000}\]\(n\) is a three-digit number.

- ParthKohli

\[\sum_{k = 1}^{1000} 2^{(k!)!} \equiv n\pmod{1000}\]\(n\) is a three-digit number.

- Stacey Warren - Expert brainly.com

Hey! We 've verified this expert answer for you, click below to unlock the details :)

- schrodinger

I got my questions answered at brainly.com in under 10 minutes. Go to brainly.com now for free help!

- ParthKohli

@amistre64 Phi function?

- ParthKohli

Well, \((k!)!\) would be divisible by all positive numbers under \((k!)!\)

- ParthKohli

How can I proceed with that information?

Looking for something else?

Not the answer you are looking for? Search for more explanations.

## More answers

- amistre64

well, 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

im 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

Yup, know that property. :-)

- ParthKohli

Idea of mine.

- ParthKohli

Or would it be recognizing some pattern?

- amistre64

it might be patternable ... if your mod reductions simplify down to a repetition
what are the first 10 terms .. or 5 terms?

- amistre64

1!, 2!, 6!, 24!, 120!, 720!, ....
that can be a nightmare, but might be reduceable by phis

- ParthKohli

a1 = 2 = 0 (mod 1000)
a2 = 4 = 4 (mod 1000)
a3 = 2^(720!) = O_O (mod 2)

- ParthKohli

a3 = 2^(6!) = 2^(720) sorry

- ParthKohli

2^(1!) = 2 = 2 (mod 1000)
2^(2!) = 4 = 4 (mod 1000)
2^(3!) = 64 = 64 (mod 1000)
2^(4!) = 216 (mod 1000)
Hmm

- ParthKohli

Do you see any pattern? o_O

- amistre64

not yet ...
when does 2^n equal a multiple of 1000? i know 2^10 = 1024, which is 24 mod 1000

- ParthKohli

2^2 = 4
4^3 = 64
64^4 has the last three digits 216
216^5 has last three digits equal to 216

- ParthKohli

no, 576.

- amistre64

lol, dont look at this: http://www.wolframalpha.com/input/?i=2%5E%28n%21%29%21%2C+n%3D1..3

- ParthKohli

Super-exponential function! :-O

- amistre64

i see a pollard factorization method that might be useful ... but might not

- ParthKohli

Dag nab those fancy names.

- amistre64

2^(p-1)=1 (mod p) per fermat little thrm.

- ParthKohli

Yup.

- amistre64

if k! = (p-1)q for some interger q, then that reduces to 1 mod p

- ParthKohli

Hmm... :-|

- ParthKohli

Is there anything to do now? :-\

- ParthKohli

Oh.\[k! \equiv 2^{(p - 1)} \pmod{p}\]Is it so?

- amistre64

thats fermats little thrm i believe

- ParthKohli

Were you able to solve it then?

- ParthKohli

Gotta sleep, or rather: gotta sleep on the problem. ;-)
If you have any solution, feel free to post.

- ParthKohli

Thanks for your time!

- amistre64

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

Thanks anyway sire!

- amistre64

ive got my elementary number theory textbook that im looking thru, and might be able to determine something in about a day :)

- ParthKohli

@experimentX Any ideas on this one?

- experimentX

I don't know ... but let me see.

- ParthKohli

What does Mathematica compute?

- ParthKohli

:-|

- experimentX

overflow :(((

- ParthKohli

Oh . . . what do you mean by overflow? It isn't able to compute it due to the hugeness?

- experimentX

Yep ...

- ParthKohli

Darn. I thought Mathematica was smart.

- experimentX

Let me try finding the sum of mods first

- ParthKohli

Yeah, try it one-by-one, maybe we can find some pattern. Actually we did above, but let's see what we get for the further values.

- experimentX

Sum[Mod[2^((i!)!), 1000], {i, 1, 1000}]

- experimentX

returns overflow in computation ... let me try on matlab.

- experimentX

looks like application of Euler totient function. but let me compute it numerically first.

- ParthKohli

Yup, that.

- ParthKohli

But it would get harder and harder to compute \(\phi((n!)!)\) as \(n\) increases. :-|

- experimentX

trust me .. I don't know that ... I am least experience with number theory.

- ParthKohli

Me too :-(

- experimentX

damn!! even sum of these numbers is huge digit ... returns NaN

- ParthKohli

@Callisto Hi, any ideas?

- ParthKohli

Try calculating modulo 1000? Just an idea...

- experimentX

bug on my code .. :(((

- ParthKohli

Well, it's more like pattern recognition, I guarantee you that.

- experimentX

yeah i know ... my code was correct ,,, just 2^(,,(..)) is such a huge number. i guess Bigger than grahms number.

- ParthKohli

But still lesser than Googol.

- ParthKohli

Or is it?

- experimentX

Grahams number is bigger than googol

- experimentX

numerically it's a fiasco ... let me look for totient function.

- ParthKohli

Fiasco indeed.

- experimentX

I never used Totient function on my entire life. ... looks like worth it.

- ParthKohli

Ditto!

- experimentX

freaking group theory is again here.

- experimentX

up until now I managed to calculate 2^1000! mod 1000 numerically.

- experimentX

A 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

The answer is 454 ... Amazing, Apart for Euler theorem I managed to learn Euclid algorithm, System of linear congruence, Chinese Remainder theorem, ...

- ParthKohli

Is there a CRT here too?!

- experimentX

oh ... just step for understanding Euler's theorem. I have never done number theory in my entire life.

- ParthKohli

I see, number theory and contest mathematics combined is pretty hard!

- experimentX

quite hard ... i often have difficulty doing problems on most of them.

Looking for something else?

Not the answer you are looking for? Search for more explanations.