Last 3 digits of $3^{999}$

Question

I know that it's $3^{999} \mod 1000$ and since $\varphi(1000) = 400$ and $3^{400}\equiv1 \mod1000$ it will be equivalent to $3^{199} \mod 1000$ but what should I do from then? Or am I wrong about this from the start?

Answer 1

Using Carmichael function will be beneficial here as $\displaystyle\lambda(1000)=100$

$$\implies 3^{100n}\equiv1^n\pmod{1000}\equiv1$$ for any integer $n$

As $(3,1000)=1,$ this implies $$3^{100n-1}\equiv3^{-1}$$

As $\displaystyle 999\equiv-1\pmod{1000}\implies3^{-1}\equiv-333\equiv1000-333$

Answer 2

To know $3^n\bmod 1000$ it is enough to know $3^n\bmod 8$ and $3^n\bmod 125$. From $3^2\equiv 1\pmod 8$ we conclude $3^{1000}\equiv 1\pmod 8$. From $\phi(125)=100$, we conclude $3^{1000}=(3^{100})^{10}\equiv 1\pmod{125}$. Therefore $3^{1000}\equiv 1\pmod {1000}$. This implies $3^{999}\equiv 667\pmod{1000}$

Answer 3

Note $\,\ \phi(8)=4\mid\phi(125)=\color{#0a0}{100},\,$ so using this as a common period in modular order reduction

thus $\ {\rm mod}\ 8,\,125\!:\ 3^{999}\equiv (3^{\large \color{#0a0}{100}})^{10}/3\equiv 1/3\ $ by Euler's $\phi$ Theorem and $\,(3,8)\!=\!1\!=\!(3,125).$

thus $\ {\rm mod}\ 8\cdot 125\!:\ 3^{999}\equiv \color{#c00}1/3\equiv \color{#c00}{-999}/3 \equiv -333\,\ $ by $\,\ \color{#c00}{1 \equiv -999} \pmod {\!1000 }$

Remark $ $ The method above easily yields the following generaization of the Euler-Fermat theorem (see also Carmichael's theorem)

Theorem $\ $ Suppose that $\ m\in \mathbb N\ $ has the prime factorization $\:m = p_1^{e_{1}}\cdots\:p_k^{e_k}\ $ and suppose that for all $\,i,\,$ $\ e\ge e_i\ $ and $\ \phi(p_i^{e_{i}})\mid f.\ $ Then $\ m\mid a^e(a^f-1)\ $ for all $\: a\in \mathbb Z.$

Proof $\ $ If $\ p_i\mid a\ $ then $\:p_i^{e_{i}}\mid a^e\ $ by $\ e_i \le e.\: $ Else $\:a\:$ is coprime to $\: p_i\:$ so by Euler's phi theorem, $\!\bmod q = p_i^{e_{i}}\!: \ a^{\phi(q)}\equiv 1\,$ thus $\,a^f\equiv 1\, $ by $\: \phi(q)\mid f.\ $ Since all $\ p_i^{e_{i}}\,$ divide $\, a^e (a^f - 1)\ $ so too does their product $\,m\,$ by lcm = product for coprimes, or by unique prime factorization.

Examples $\ $ You can find many illuminating examples in prior questions, e.g. below

$\qquad\qquad\quad$ $24\mid a^3(a^2-1)$

$\qquad\qquad\quad$ $40\mid a^3(a^4-1)$

$\qquad\qquad\quad$ $88\mid a^5(a^{20}\!-1)$

$\qquad\qquad\quad$ $6p\mid a\,b^p - b\,a^p$

Answer 4

$$3^{999}=3(10-1)^{499}$$

Now, $$(10-1)^{499}\equiv-1+\binom{499}110^1-\binom{499}210^2\pmod{1000}$$

Again, $\displaystyle\binom{499}1=499\equiv-1\pmod{100}\implies\binom{499}110^1\equiv-10\pmod{100\cdot10}$

and $\displaystyle\binom{499}2=\frac{499\cdot498}2\equiv\frac{(-1)(2)}2\pmod{10}\equiv1\implies\binom{499}210^2\equiv100\pmod{10\cdot100}$

$\displaystyle\implies(10-1)^{499}\equiv-1-10-100\pmod{1000}\equiv-111$

The rest should be easy to deal with

Answer 5

I don't know number theory and lack math backgorund to understand any of the given answers. I came with this basic math solution while trying to answer a duplicate question. $$ 3^{999}=3^{512}\times3^{256}\times3^{128}\times3^{64}\times3^{32}\times3^{4}\times3^{2}\times3\\ \quad=9^{256}\times9^{128}\times9^{64}\times9^{32}\times9^{16}\times9^{2}\times9\times3\\ =81^{128}\times81^{64}\times81^{32}\times81^{16}\times81^{8}\times{81}\times9\times3 $$ From now on calculating only the last three digits, as $81^2$ exceeds three digits. $$ 3^{999}=..561^{64}\times..561^{32}\times..561^{16}\times...561^{8}\times..561^{4}\times{81}\times9\times3\\=..721^{32}\times..721^{16}\times..721^{8}\times.721^{4}\times..721^{2}\times81\times9\times3\\ =..841^{16}\times..841^{8}\times..841^{4}\times..841^{2}\times..841\times81\times9\times3\\ =..281^{8}\times..281^{4}\times..281^{2}\times..281\times..841\times81\times9\times3\\ =..961^{4}\times..961^{2}\times..961\times..281\times..841\times81\times9\times3\\ =..521^{2}\times..521\times..961\times..281\times..841\times81\times9\times3\\ =..441\times..521\times..961\times..281\times..841\times81\times9\times3\\ =(..441\times..521)\times(..961\times..281)\times(..841\times81)\times(9\times3)\\ =..761\times..041\times..121\times27\\ =..201\times..267\\ =..667 $$

Answer 6

Giving some structure to the answer by @fruitbat that is effectively using exponentiation by squaring, this answer ignores the advantages that are possible by the consideration of modular order (cycling of values) to focus on an example of what is possible if using a larger or less convenient modulus:

So, here's a tabular form of exponentiation by squaring:

• starting with the exponent, work down the left-hand column, subtracting $1$ from odd numbers and halving even numbers. then
• starting with the base, work up the right-hand column. multiplying by the base, $3$, or squaring as appropriate, taking the modulus each time.

$\newcommand{oddnote}{{x \mathit{\text{ odd, }{\times}\text{base}}}} \newcommand{evennote}{{x \mathit{\text{ even, square}}}}$ \begin{array}{c|c} x & 3^x \bmod 1000 & \mathit{\text{notes}}\\\hline \bbox[yellow]{\;999\;} & \fbox{667} & \oddnote \\ 998 & 889 & \evennote \\ 499 & 667 & \oddnote \\ 498 & 889 & \evennote \\ 249 & 83 & \oddnote \\ 248 & 361 & \evennote \\ 124 & 481 & \evennote \\ 62 & 809 & \evennote \\ 31 & 947 & \oddnote \\ 30 & 649 & \evennote \\ 15 & 907 & \oddnote \\ 14 & 969 & \evennote \\ 7 & 187 & \oddnote \\ 6 & 729 & \evennote \\ 3 & 27 & \oddnote \\ 2 & 9 & \evennote \\ 1 & \bbox[yellow]{\;3\;} & \mathit{\text{base}} \\ \phantom{\large\Rightarrow}\Downarrow\Downarrow\underset{\large\Rightarrow}{} &\underset{\large\Rightarrow}{}\Uparrow\Uparrow\phantom{\large\Rightarrow} \\ \end{array}