# Power of 3 that ends in 001.

#### mathmaniac

##### Well-known member
Prove that there exists a power of 3 that ends in 001.

#### caffeinemachine

##### Well-known member
MHB Math Scholar
Prove that there exists a power of 3 that ends in 001.
consider the integers:
$3^1,3^2,\ldots,3^{1001}$

Some two distinct integers of these must leave the same remainder mod $1000$.
So there exist distinct $i$ and $j$ such that $3^i\equiv 3^j\pmod{1000}$.
WLOG $i<j$. Thus $3^i(3^{j-i}-1)\equiv 0\pmod{1000}$
Thus $3^{j-1}\equiv 1\pmod{1000}$ and we are done.

#### mathmaniac

##### Well-known member
Good work!!!So quick!!!
Now what odd numbers can we replace for 001???

Last edited:

#### caffeinemachine

##### Well-known member
MHB Math Scholar
Good work!!!So quick!!!
Now what odd numbers can we replace for 001???
I don't know if there's an analytic way to enumerate all such numbers. But it can be shown then the number of such numbers which are less then 1000 divides $\phi(1000)$.