For each integer $2 \leq a \leq 10$, find the last four digits of $a^{1000}$.
$[$Hint: We need to calculate $a^{1000}$ mod $10000$. Use Euler’s theorem and Chinese remainder theorem.
For example, $10000 = 2^4 \cdot 5^4$; $2^{1000} \equiv 0$ mod $2^4$, and $2^{500} \equiv 1$ mod $5^4$.$]$
$\mathbf{My~Attempt:}$
$\mathbf{Case~1}$: If $a = 10$
Then, notice that $10^4 = 10000$ divides $a^{1000}$.
So, we have $a^{1000} \equiv 0 ~(\text{mod}~10000)$ if $a = 10$.
Therefore, the last four digits of $a^{1000}$ must be $0000$ if $a = 10$.
$\mathbf{Case~2}$: If $a \in \{ 3, 7, 9 \}$
Since, by the Euler's Theorem, we know that if $a, m \in \mathbb{N}$, $m > 1$ and $\text{gcd}(a, m) = 1$,
$~\hspace{82mm}$ then $a^{\phi(m)} \equiv 1 ~(\text{mod}~m)$.
Then, we notice if $a \in \{ 3, 7, 9 \}$, then $\text{gcd}(a, 10000) = 1$.
So, we have $a^{\phi(10000)} \equiv 1 ~(\text{mod}~10000)$.
Since, $\phi(10000) = \phi(2^4 \cdot 5^4) = \phi(2^4) \cdot \phi(5^4) = (2^4 – 2^3)(5^4 – 5^3) = 8 \cdot 500 = 4000$.
Then, we have $a^{4000} \equiv 1 ~(\text{mod}~10000)$. Which means $a^{4000} = (a^{1000})^4 \equiv 1^4 = 1 ~(\text{mod}~10000)$.
So, we have $a^{1000} \equiv 1 ~(\text{mod}~10000)$ if $a \in \{ 3, 7, 9 \}$.
Therefore, the last four digits of $a^{1000}$ must be $0001$ if $a \in \{ 3, 7, 9 \}$.
$\mathbf{Case~3}$: If $a \in \{ 2, 4, 6, 8 \}$
I only know $a^{1000} \equiv 9376$ (mod $10000$) but do not know how to find it !!
$\mathbf{Case~4}$: If $a = 5$
I only know $a^{1000} \equiv 625$ (mod $10000$) but do not know how to find it !!
$\mathbf{My~Questions:}$
First, I don't think for my $\mathbf{Case~2}$ is okay to say $a^{4000} = (a^{1000})^4 \equiv 1^4 = 1 ~(\text{mod}~10000)$ $\implies$ $a^{1000} \implies 1 ~(\text{mod}~10000)$ but I don't know what else I can write to get $a^{1000} \implies 1 ~(\text{mod}~10000)$.
Also, I am totally lost in Case 3 and Case 4. I know that $a^{1000} \equiv 9376$ (mod $10000$) if $a \in \{ 2, 4, 6, 8 \}$ and $a^{1000} \equiv 625$ (mod $10000$) if $a = 5$ but I don't know how to find these results.
Well in Case 3, I use the Chinese remainder theorem and can find out that $9376 \equiv 0$ mod $2^4$ and $9376 \equiv 1$ mod $5^4$. But have no idea on how to get $a^{1000} \equiv 9376$ (mod $10000$)
Best Answer
Your mistake, as @kingW3 points out, is casting aside CRT.
Plus you're forcing the issue (and making a bit of a mess).
As a hint, let's do $a=3$. Since $10000=2^45^4$ with $(2^4,5^4)=1$, we split it up with an eye towards applying CRT first, and then apply Euler's theorem: $3^{1000}\cong(3^8)^{125}\cong1\bmod{2^4}$ and $3^{1000}\cong(3^{500})^2\cong1\bmod{5^4}$.
Now by the constant case of CRT, we conclude $3^{1000}\cong1\bmod{10000}$.