2

How could I find $$ 0 \leq a \leq 9 $$ such that

$$ \left \lfloor \frac{10^{20000}}{10^{100}+3} \right\rfloor \equiv a \mod 10 $$

?

Chon
  • 6,002

3 Answers3

5

HINT: $$\begin{align}10^{20000}=&(10^{100}+3)\cdot\bigl(10^{19900}-3\cdot 10^{19800}+9\cdot10^{19700}-27\cdot 10^{19600}\pm\ldots\\&+(-3)^{k}\cdot 10^{19900-100k}\pm\cdots+(-3)^{199}+\epsilon\bigr)\end{align}$$ with $\epsilon\approx 3^{100}10^{-100}>0$

Hagen von Eitzen
  • 374,180
  • 1
    Not that it makes a difference to the final answer, but I believe that $\epsilon\approx\left(\frac{9}{10}\right)^{100}$. – robjohn Feb 04 '13 at 14:38
5

This didn't work as a comment to Hagen von Eitzen's answer, so I post it here.

Writing the fraction as $$ \small\begin{align} &\frac{10^{20000}}{10^{100}}\frac1{1+3\cdot10^{-100}}\\ &=10^{19900}\left(1-3\cdot10^{-100}+\left(3\cdot10^{-100}\right)^2-\dots \color{#00A000}{-\left(3\cdot10^{-100}\right)^{199}}\color{#C00000}{+\left(3\cdot10^{-100}\right)^{200}-\dots}\right)\\ &\equiv\color{#00A000}{-3^{199}}\color{#C00000}{+\epsilon}\pmod{10^{100}} \end{align} $$ where $0\le\epsilon\le\left(\frac{9}{10}\right)^{100}$

Thus, $$ \begin{align} \left\lfloor\frac{10^{20000}}{10^{100}+3}\right\rfloor &\equiv-3^{199}\pmod{10^{100}}\\ &\equiv-\left(3^4\right)^{49}\,3^3\pmod{10}\\[6pt] &\equiv-1^{49}\,7\pmod{10}\\[12pt] &\equiv3\pmod{10} \end{align} $$

robjohn
  • 345,667
  • So $ \lfloor ... \rfloor \equiv -3^{199} \equiv 3 \pmod{10} $ Thanks a lot! – Chon Feb 04 '13 at 17:13
  • @Chon: yes, that's correct. I didn't mark this as a hint since it was intended as a comment to Hagen von Eitzen's answer (it is essentially the same). I guess I can add the final steps since it is obviously not giving anything away :-) – robjohn Feb 04 '13 at 17:23
0

NOTE: I just stumbled upon this (very) old question, and I think I might have a new (and hopefully, easier) perspective. This is not supposed to be entirely a new chain of thought, but I think that it might be a tad bit easier to understand.

$$\begin{align}10^{20000}\pmod{10^{100}+3}&\equiv10^{20000}-10^{19900}\times(10^{100}+3)\\ &\equiv-3\times10^{19900}\\ &\equiv-3\times10^{19900}+3\times10^{19800}\times(10^{100}+3)\\ &\equiv(-3)^2\times10^{19800} \end{align}$$ As we can guess (and prove, using induction) from this method, for any whole number $n\leq20$: $$10^{20000}\pmod{10^{100}+3}\equiv(-3)^n\times10^{20000-100n}$$ So, putting in $n=200$: $$\begin{align}10^{20000}\pmod{10^{100}+3}&\equiv(-3)^{200}\times10^{20000-100\times200}\\ &\equiv9^{100}\end{align}$$ Now, $9^{100}<10^{100}+3$, so, it is the remainder that we get when we divide $10^{20000}$ by $10^{100}+3$. Furthermore, we also know that: $$10^{20000}=(10^{100}+3)\times\left \lfloor \frac{10^{20000}}{10^{100}+3} \right\rfloor+\text{remainder}$$ Putting in $9^{100}$ as remainder: $$10^{20000}=(10^{100}+3)\times\left \lfloor \frac{10^{20000}}{10^{100}+3} \right\rfloor+9^{100}$$ Applying congruence modulo $10$: $$\begin{align}10^{20000}&\equiv(10^{100}+3)\times\left \lfloor \frac{10^{20000}}{10^{100}+3} \right\rfloor+9^{100}\pmod{10}\\ \implies0&\equiv3\times\left \lfloor \frac{10^{20000}}{10^{100}+3} \right\rfloor+1\pmod{10}\end{align}$$ So, we can conclude: $$\left \lfloor \frac{10^{20000}}{10^{100}+3} \right\rfloor\equiv3\pmod{10}$$

Soham Saha
  • 1,204