Last three digits of 23^320

Question

What is the best way to compute the last three digits of $23^{320}$? I know one way is by starting of $23^2$ and finding the last three digits, then squaring those (calculating $23^4 \pmod {1000}$) and getting the last three digits and so on until you reach $23^{320}$. Is there any easier method?

Answer 1

The period of $1000$ in any base is the $\operatorname{lcm}(\varphi(125)\varphi(8))$, where $\varphi()$ is the Euler totient function, and $125$ and $8$ are prime-powers that multiply to $1000$. This is then $\varphi(125)=100$, and $\varphi(8)=4$, but in fact, the powers of 2 contains an orthogonal element, so it's actually 2.

This means the last three decimal digits of any $x^n$ is periodic over 100 places.

So, $320 = 20 \pmod{100}$. So $23^{320}$ ends in the same three digits as $23^{20}$.

We see that $23=-1 \pmod 8$, so $23^{2n}=1 \pmod 8$. For $5$, we need to approach this carefully. $23^2 = 529$, $529^2 = 841 \pmod{1000}$ , being the fourth power.

We now calculate the fifth power of this, not directly, but by the rule of

$$(x+1)^5 = x^5 + 5x^4 + 10x^3 + 10x^2 + 5x^1 + 1$$

When $x=840$, then everything $x^2$ and greater reduces to $0 \pmod {1000}$. So all we need to find here is $5x+1 = 201 \pmod{1000}$.

The process is much easier for finding $a^n \pmod{b^2}$, because if one finds some $a^x$ in the form $cb+1$, then $a^{xy}= (cy)b+1$. For example, to find the last four digits of $7^{23}$, it helps to know that $7^4=24\;01$, and hence $7^{4x}=24x\;01$. Here, we can use $x=5$ and $5\times24 = 1\;20$, to get $7^{20} = 20\;01$ It is straight forward to multiply this by $343$ to get $63\;43$ as the last four digits of that number.

For example, the final four digits of $23^{320}$, goes like this.

$23 ^ 2 = 529$, $529^2 = 500^2 + 2\cdot 500 \cdot 29 + 29^2 \pmod{10000}$, This reduces to $0 + 9000 + 841 = 9841 \pmod {10000}$. for the fourth power.

We now use $(x+1)^5 = x^5 + 5x^4 + 10x^3 + 10x^2 + 5x + 1$, with $x=9840$. Most of these are multiples of $10,000$, so we need only to consider $10x^2 + 5x + 1$

The first term gives $4^2 = (1)6$ gives $6000$. The second term gives $5\times 9840$, gives $4\;9200$. The third term is $1$, the total is $52\;01$, the 20th power.

We now find from $52\times 16$ gives $32$, and so the last four digits is $3201$. Nothing more complex than mental arithmetic, really.

Answer 2

$201$ (Using "23**320" in Python3.)

Or, a marginally different twist that does not involve totients (directly, at least):

Since $320 = 5 \cdot 2^6$, we have

$23^5 = 343 \mod 1000$

$343^2 = 649 \mod 1000$

$649^2 = 201 \mod 1000$

Now notice that $(200n+1)^2 = 200(2n)+1 \mod 1000$, hence $(200n+1)^{2^4} = 200(16)+1 = 201\mod 1000$.

Answer 3

Some ideas:

Since $10^3=5^3\times 2^3$, we can try work independently. And use the Chinese remainder theorem

The totient function of $125$ is easily seen to be $100$, so acording to Euler's theorem you have that $23^{100} \equiv 1 \pmod{125}$, and therefore $23^{300}\equiv1 \pmod{125}$. Additional computation shows that $23^{320}\equiv 76 \pmod{125}$. Set $a_1=76$.

The other case is maybe easier, since $\phi(8)=4$, then $23^4 \equiv 1 \pmod{8}$. Since $4$ divides $320$ then you have that $23^{320}\equiv 1 \pmod{8}$. Set $a_2=1$.

The last step would be to use the Chine Remainder Theorem to recover the whole answer. We need to solve two congruences to apply this theorem to obtain numbers $b_1$ and $b_2$. $$ 8x \equiv 1 \pmod{125}$$ $$ 125x \equiv 1 \pmod{8}$$ The solutions are $47$ in the first case and $5$ in the second case. From here we obtain the following expression (it's just the recipe of the Chinese remainder theorem) $$x\equiv 8*a_1*b_1 +125*a_2*b_2 = 8*76*47+125*5= 29201 \equiv 201 \pmod{1000}$$

This doesn't seem simple enough though. But is another approach. This answer is correct. I verified.

Answer 4

As $1000=2^3\cdot5^3$ where $(2,5)=1$

Now, we have $23^2\equiv1\pmod{ 2^3}\implies 23^{320}=(23^2)^{160}\equiv1^{160}\pmod{ 2^3}$ $\implies 23^2\equiv1\pmod8\ \ \ \ (1)$

and as $23=25-2$ $\implies 23^{320}=(25-2)^{320}=(2-25)^{320}=2^{320}-320\cdot2\cdot25+25^2(\cdots)\equiv2^{320}\pmod{125}$

As $(2,125)=1$ and $\phi(125)=100, 2^{100}\equiv1\pmod{ 125}\implies 2^{320}\equiv2^{20}\pmod{125}$

Again, $2^{10}=1024\equiv24\pmod{125}\implies 2^{20}\equiv24^2\pmod{125}\equiv76$

$\implies23^{320}\equiv2^{320}\equiv2^{20}\equiv76\pmod{125}\ \ \ \ (2)$

Method $1:$ Apply CRT on $(1),(2)$

Method $2:$

From $(1)$ and $(2)$ we have $x=8a+1$ and $x=125b+76$ respectively where $a,b$ are integers

$\implies 8a+1=125b+76\iff 8a=125b+75\iff 8a=25(5b+3)\ \ \ \ (3)$

$\displaystyle\iff\frac{8a}{25}=5b+3$ which is an integer

$\displaystyle\implies25$ divides $8a\implies 25|a$ as $(25,8)=1$

$a=25c$(say) where $c$ is an integer

$(3)$ reduces to $8c=5b+3\iff 8(c-1)=5(b-1)\iff \frac{5(b-1)}8=c-1$ which is an integer

As $(5,8)=1,8$ must divide $b-1\implies b-1=8d$ for some integer $d$

$\implies x=125b+76=125(8d+1)+76\equiv201\pmod{1000}$