# What is the smallest natural number n?

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?

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

-
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). – 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.

-

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.

-
71 works so it doesn't have to end like that. – Carry on Smiling Jan 6 '14 at 18:56