Fun with 2018 #11 (This is awesome)

Number Theory Level 5

For this exercise you can use Wolfram Alpha

a) I know that $2018^{76} \equiv 76 \text{ mod (100)}$ , and the smallest natural number $n > 1$ such that $2018^n \equiv 76 \text{ mod (100)}$ is $n = 4$ .

b) I know that $2018^{776} \equiv 776 \text{ mod (1000)}$ , and the smallest natural number $n > 2$ such that $2018^n \equiv 776 \text{ mod (100)}$ is $n = 16$ .

c) I know that $2018^{9776} \equiv 9776 \text{ mod (10000)}$ , and the smallest natural number $n > 3$ such that $2018^n \equiv 9776 \text{ mod (10000)}$ is $n = 76$ .

d) I can continue, and so on, for example, I know that $2018^{79776} \equiv 79776 \text{ mod (100000)}$ .

e) I know that $2018^{379776} \equiv 379776 \text{ mod (1000000)}$ .

f) I know that $2018^{1379776} \equiv 1379776 \text{ mod (10000000)}$ ...

My question is, how do I know this? ,

Enter the smallest natural number $n > 6$ such that $2018^n \equiv 379776 \text{ mod (1000000)}$ ?

The answer is 2276.

2 solutions

Shreyansh Mukhopadhyay
Feb 18, 2018

For this question, we can use the property that for any $n>k$ , $\large 2018^n\equiv2018^{n+4\cdot5^{k-2}} \text{ mod }(10^k)$ for any integer $k>1$

So putting $k=6$ , we get $2018^n\equiv2018^{n+2500} \text{ mod }(10^6)$

We are also given that $2018^{379776} \equiv 379776 \text{ mod (1000000)}$

So, whatever remainder we get after dividing 379776 from 2500 will yield the same last 6 digits.

So the answer is $\boxed{2276}$

Yes, fantastic!

Guillermo Templado - 3 years, 3 months ago

Giorgos K.
Feb 17, 2018

Mathematica

i=6;While[PowerMod[2018,i++,10^6]!=379776];i-1 yelds 2276

-or- you can use

MultiplicativeOrder[2018,10^6,{379776}]

Yup, I suppose that this is a way to do it, but I am waiting for a solution with number theory or algebra (or maths)...

Guillermo Templado - 3 years, 3 months ago

a solution is a solution... This is why ProjectEuler uses massive numbers in order to avoid brute force approaches and discover the hidden maths... Nowadays, you should consider when posting a problem, that everyone has access to calculations like this.

Giorgos K. - 3 years, 3 months ago

My solution don't use brute force. Here, there is a guideline of my solution . I can tell you a number $n$ with 100 digits or 1000 digits such that $2018^n \equiv n \text{ mod 10}^n)$ and this just starts to cause problems with a computer...

Guillermo Templado - 3 years, 3 months ago

@Guillermo Templado – sorry mod $10^{100}$ or mod $10^{1000}$

Guillermo Templado - 3 years, 3 months ago

@Guillermo Templado – this is what I'm talking about my friend.If you want to make nice challenges you must make it difficult for a computer to solve...that's why I mentioned ProjectEuler.. ever heard of it?

Giorgos K. - 3 years, 3 months ago

Fun with 2018 #11 (This is awesome)

The answer is 2276.

2 solutions

0 pending reports