show there exists an integer k such that $2013^k$ ends with '0001' Prove that there exists an integer k so that $2013^k$ ends with '0001'.
we couldn't figure this out.
i thought we might try to prove that we can find an integer m such that $m*10^4 +1 = 2013^k$, but was unable to get any clues.
both hints and similar solutions are welcome.
Thanks in advance!
 A: Since $gcd(2013,10^4)=1$, we will have $2013^{\varphi(10000)}\equiv1 \mod 10000$.
$\varphi(10000)=(5-1)(2-1)(5^3)(2^3)=4000$, so $10000|2013^{4000}-1$.
It leads us to there is a $m$ such that $2013^{4000}=10^4m+1$ ( the desired $k$ is $4000$ here)
A: Remember Euler's theorem. Assume $k\ge 2$.
$(2013^k$ ends in $0001)\iff 2013^k\equiv 1\pmod{\! 10\, 000}$
Since $(2013,10\, 000)=1$, it is sufficient that $\varphi(10\, 000)\mid k\iff 4000\mid k$.
There exist infinitely many such integers $k$ ($k=4000m$ with $m\in\Bbb Z^+$ is sufficient).
It is also sufficient (and in fact necessary, so $\text{ord}_{10^4}(2013)=500$ (see Wikipedia for what it denotes), but I won't prove it here) that $k=500m$ for some $m\in\Bbb Z^+$ because of Carmichael's function, since $\lambda(10\, 000)=500$ and $(2013,10\, 000)=1$ (Carmichael's function is just a stronger version of Euler's theorem).
A: Suppose $S=\{2013^1,2013^2,2013^3,\cdots,2013^{10001}\}$
Then by Pigeonhole principle, there are at least two distinct elements of $S$ with same remainder modulo $10^4$, namely ,
$\exists i,j(i>j)$ s.t $2013^i\equiv2013^j \mod 10000$
$\Rightarrow 10000|2013^i-2013^j$
$\Rightarrow10000|2013^j(2013^{i-j}-1)$
Since $gcd(2013,10000)=1$, so $gcd(2013^j,10000)=1$. Thus we could conclude from the above:
$10000|2013^{i-j}-1$
Now the desired $k$ would be $i-j$, and there is $m$ such that:
$2013^{i-j}=10^4m+1.$
A: You have to prove that for some $k$,
$$ 2013^{k}\equiv 1\pmod{10^4} $$
but since $2013=3\cdot 11\cdot 61$ and $10^4=2^4\cdot 5^4$, we have $\gcd(2013,10^4)=1$, so $2013$ is an element of the group $\mathbb{Z}_{/10^4\mathbb{Z}}^*$, and its order is a divisor of $\varphi(10000)=4000$ by Euler's theorem and Lagrange's theorem.
You may also prove that $k=\color{red}{500}$ works.
