What is the smallest natural number n for which there is a natural k, such that, the lasts 2012 digit in the representation decimal of $n^k$ are equal to 1?

I don't even know how to start with it ...

  • $\begingroup$ It sounds a bit like a competition problem. Would you tell us where you had it from? $\endgroup$ – Harald Hanche-Olsen Dec 27 '13 at 18:46
  • $\begingroup$ Yes, of course. Here -> link. By the way, it is a competition problem. $\endgroup$ – Ewin Dec 27 '13 at 18:49
  • $\begingroup$ Olá Ewin! Gosto de seu sobrenome. $\endgroup$ – Ewan Delanoy Dec 27 '13 at 19:22
  • $\begingroup$ $$n=\sqrt[K]{a\cdot10^{2012}+\frac{10^{2012}-1}9}\in\mathbb{N}$$ $\endgroup$ – Lucian Dec 27 '13 at 19:27

Using a quick search with my computer, here’s what I found so far :

Looking only at the last digit, some power of $n$ must be congruent to $1$ modulo $10$, so $n$ must be congruent to $1,3,7$ or $9$ modulo $10$.

Looking at the last two digits, some power of $n$ must be congruent to $11$ modulo $100$, so $n$ must be congruent to $11,31,71$ or $91$ modulo $100$.

Looking at the last three digits, ome power of $n$ must be congruent to $111$ modulo $1000$, so $n$ must be congruent to one of $31, 71, 111, 191, 231, 271, 311, 391, 431, 471, 511, 591, 631, 671, 711, 791, 831, 871, 911, 991$ modulo $1000$.

Looking at the last four digits, ome power of $n$ must be congruent to $1111$ modulo $10000$, so $n$ must be congruent to one of $71, 1031, 2071, 3031, 4071, 5031, 6071, 7031, 8071, 9031$ modulo $10000$.

Do you see the pattern in those sequences ?

| cite | improve this answer | |
  • $\begingroup$ I see that the number of solutions goes down, so it would be a good idea to look at the next two steps. But it will be hard to note a pattern if you do not record the exponents (for example from 10 to 100, you lose solutions because they have an even exponent). $\endgroup$ – Phira Dec 28 '13 at 9:36

$n^k\equiv-1\bmod4$ so $k$ and $n$ are odd.

If n ends in 2012 zeroes we have $n^k\equiv\frac{-1}{9}\bmod10^{2012}$ such a $k$ exists if and only if there is a $t$ such that $n^t\equiv-9\bmod10^{2012}$.

$n^t\equiv1\bmod5,n^t\equiv7\bmod16$ .Since $\lambda(5),\lambda(16)=4$ we have $t=1$ or $3$ ($t$ is odd). Check this is only possible for $n\equiv7\bmod16$ and $n\equiv1\bmod5$ in other words $n\equiv71\bmod 80$.

Now we prove $n=71$ does the trick.

Check $2^{c+3}||71^{2^{c}}-1$ by lte. So $71^{2^{c}}\equiv {2^{c+2}}\bmod2^{y+1}$

Likewise $71^{5^c}\equiv 5^{c+1}+1\bmod5^{c+2}$

If there is a $w$ such that $2^w\equiv-9\bmod a^c$but $2^w\neq-9\bmod2^{c+1}$ then $2^w\equiv2^c-9$ which implies $2^{w+2^{c-2}}\equiv{-9}\bmod2^{c+1}$ so there is also a solution for $2^c+1$.

Likewise if there is $w$ so $5^w\equiv-9\bmod5^c$ then $ 71^w\equiv a5^c-9\pmod{5^{c+1}} $ for some a not divisible by 5. Then if $5|mb+a$ we have $ 71^{w+m5^{c-1}}\equiv(a5^c-9)(b5^c+1)^m\equiv(mb+a)5^c-9\equiv-9\pmod{5^{c+1}}$.

Now let $c=2012$. By the above there are $w_1$ and $w_2$ such that $71^{w_1}\equiv-9\bmod2^{2012}$ and $71^{w_2}\equiv -9 \bmod 5^{2012}$

By chinese remainder theorem there is a $w$ such that

$w\equiv w_1\bmod2^{c-3}$ and $w\equiv w_2 \bmod 5^{c-1}$

so $71^w\equiv -9\bmod10^c$ as desired.

| cite | improve this answer | |

Here is an expanded answer. I have to confess that I do not see a pattern at all. I am putting it here so someone else can see something I don't.

It is easily verified (and shown using Fermat's theorem) that last digit of cubes of 0 through 9 are all different.

Since I already showed that $d$ has to be odd, let me try $d=3$. To keep my English straight, I will count the digits right to left, the right most being digit #1.

clearly $n$ should end in a $1$. So $$ n = 10 x + 1, ~~~ n^3 = 1000 x^3 + 300 x^2 + \underbrace{30 x}_{\hbox{determines digit #2}} + 1$$ So the digit #2 is given by the last digit of $3x$. So $x$ ends in $7$ since $3x$ should end in 1

Now we have the last two digits of $n$. We can now write $$ n = 100 x + 71, ~~~ n^3 = 10^6 x^3 + 3\, 10^4 x^2+ 1512300 x+357911$$ So digit #3 is determined by $3x + 9$, so $3x$ should end in a $2$, or $x$ end in a 4.

So far we have $$ n = 1000 x + 471$$

You can proceed like this and at every stage you will get a condition that reads

3 $x$ should end in $y$

You have the answer in that you can calculate it. But the numbers you need will have 2012 digits and you clearly need a computer. I fail to see the pattern, may be you will.

Here are the last 50 digits of $n$ $$ 73772229236117172789893835778279858716637368288471 $$ and the last 100 digits of $n$ $$ 19112219622110520080833630979583032252654876813003\\73772229236117172789893835778279858716637368288471 $$ May be someone will notice a pattern.

| cite | improve this answer | |
  • $\begingroup$ 71 works so it doesn't have to end like that. $\endgroup$ – Jorge Fernández-Hidalgo Jan 6 '14 at 18:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.