Order of an element 250 in U(641) $U(n)$ is the collection of positive integers which are coprime to n forms a group under multiplication modulo n.
What is the order of the element 250 in $U(641)$?
My attempt:
Here 641 is a prime number.
So $U(641)$ is a cyclic group. So this group is Isomorphic to $Z/640 Z$ under addition modulo 640.
I need to find the smallest positive integer n such that $250^n$ congruent to 1 (mod 641).
Any easy way to find this n?
Also I found that inverse of 250 in U(641) is 100.
Kindly provide some hints to find the required n.
Thanks in advance. 
 A: A priori, the order of $250$ could be any divisor of $640$.
Since you found the inverse and it is an obvious square ($100=10^2$), it is clear that the order of  $250$ is at worst a divisor of $320=2^6\cdot 5$, not of $640$. Seeing this was a bit of luck. We could try to find out whether we can easily take a fifth root of either $250$ or $10$ (or another square root of $10$, say). Unfortunately, numbers like $866$, $741$, or $651$ or even when adding yet another $641$ do not look like obvious squares or fifth powers, so systematic work seems unavoidable.
If we wanted to prove that the order is $320$ (if that were true), we'd only have to check that neither $250^{320/2}$ nor $250^{320/5}$ is $1$ (whereas we know from the first paragraph that $250^{320}\equiv 1$). If the actual order is smaller, we'd have to climb down the grid of divisors anyway. In partucular, it is somewhat unavoidable that we need to compute $250^{2^k}$ for $k=1,2,\ldots$ until either $k=6$ or we hit $1$ (or one step earlier $-1$), which is easily done by repeated squaring:
$$ 250^2=62500\equiv 323$$
$$ 323^2=62500\equiv 487$$
$$ 487^2=62500\equiv 640\equiv -1$$
and voila! Apparently, the order of $250$ is $16$ (and we fortunately need not check the numbers $250^{2^k5}$).
A: We have $641=625+16$ so that $5^4\equiv -2^4$ modulo $641$ 
and also $5\times 128\equiv -1$ so that $5^4\equiv 5\times 2^{11}$ and $5^3\equiv 2^{11}$ and $250\equiv 2^{12}$
Also $5^{24}\equiv 2^{24}$ (raising the first equation to the sixth power)and $5^{24}\equiv 2^{88}$ so that $2^{64}\equiv 1$
Now we have $250\equiv (2^4)^3$ and raising this to the power $16$ gives $250^{16}\equiv(2^{64})^3$
This gives us that $250^{16}\equiv 1$ 
There is an ad hoc nature about this, but it is easier than working with all the powers directly. 
We now need to check the status of $250^8$. Note that we now know that the value is $\pm 1$ because $641$ being prime implies that the only square roots of $250^{16}\equiv 1$ are $\pm 1$. We can therefore proceed confident that there is likely to be a way through. The strategy is to explore which powers of $2$ are congruent to $-1$. We begin by eliminating the $5$ from the existing expression for $-1$.
So using $5\times 2^7\equiv -1$ we can cube to obtain $5^3\times 2^{21}\equiv 2^{11}\times 2^{21}=2^{32}\equiv -1$
Hence (cubing again) $2^{96}\equiv -1$ but then $250^{8}\equiv (2^{12})^8=2^{96}\equiv -1$
A: By Lagrange the order of an element divides the order of the group. Since we have $640=2^7\cdot 5$, I tried powers of $2$. Then we see immediately that $250^{16}=1$ in $U(641)$. Since $250^8\neq 1$  we are done.
