Solve $\left(\frac mn\right)^k=0.\overline{x_1x_2...x_9}$ (no computers!) I got this problem from my son and he picked it from some local math competition. It's fairly simple:
For numbers $k,m,n\in N$ ($k\ge2)$ we know the following:

$$\left(\frac mn\right)^k=0.\overline{x_1x_2...x_9}\tag{1}$$

On the right side we have an infintely repeating sequence of exactly nine digits $x_i\in\{0,1,2,\dots9\}$ ($i=1\dots9)$ and these digits are not necessarily distinct. Find all possible values of expression (1).
The solution seems to be simple: we can replace the repeating sequence of digits with some number $a$:
$$a=\overline{x_1x_2...x_9}$$
Relation (1) now becomes:
$$\left(\frac mn\right)^k=\frac{a}{10^9-1}$$
$$m^k(10^9-1)=an^k$$
If we assume that $m$ and $n$ are coprime then:
$$n^k\mid10^9-1$$ 
If we are able to find prime factors of $(10^9-1)$ quickly, we are done. True, we can find a few prime factors fairly easily:
$$10^9-1=(10^3)^3-1=(10^3-1)(10^6+10^3+1)=9\times111\times1001001 \\
=3^2\times3\times 37\times3\times333667=3^4\times37\times333667$$
However, the last number (333667) is a tough nut to crack. We can proceed only if we know its factors. 
With some help from the computer you can easily find out that 333667 is a prime and the rest of the solution is fairly straightforward. 
However, suppose that you are in a real competition - you don't have a computer or a pocket calculator. Factoring 333667 by hand is a time consuming activity and you have other problems to solve as well.
Is there a better approach? 
Happy holidays :)
 A: You want to find whether there exists a prime $p$ such that $p^2\mid n$, where $n=333667$. Suppose that such $p$ exists.  Then, we know that
$$p\leq \sqrt{n}<578.$$
It is easily seen that $p>11$, so
$$13\leq p\leq 577.$$
However, if $p>67$, then $$\frac{n}{p^2}\leq \frac{n}{71^2}<66.$$
Thus, $n$ must have a prime divisor $q<66$ such that $q\mid n$ (noting that $n$ is not a perfect square per TonyK's comment under Ross Millikan's answer).  Therefore, $n$ must have a prime divisor that is inclusively between $13$ and $67$: $13$, $17$, $19$, $23$, $29$, $31$, $37$, $41$, $43$, $47$, $53$, $59$, $61$, and $67$.  We can easily rule out $37$ as $n-1$ is divisible by $111=3\cdot 37$.  This leaves $13$ primes to deal with.
There will be some cumbersome computations.  It is not too difficult (but a little bit tedious) to find the square root or the cubic root of $n$ by hand (the cubic root of $n$ is used to obtain $67$ when I say that if $p>67$ then there exists a prime divisor $q<66$).  And then you have to divide $n$ by $13$ primes.  This is doable, but not very nice.
A: To prove $333667$ is squarefree, you just have to show it has no prime factor smaller than $\sqrt[3]{333667} \approx 69$  The small ones can be done by divisibility rules, say $2,3,5,7,11$.  That leaves $14$ to try, which is not too bad.  You might even know the variants on the classic test for $7$ that you double the last digit and subtract it from the rest of the number.  This is based on the fact that $21$ is a multiple of $7$.  For $13$ you can note that $39$ is a multiple of $13$ and multiply the last digit by $4$ and add to the rest of the number.  For $17$ you can use $51$.  That gets you the next few.  It would be a few minutes, but if you are quick with arithmetic much less than $10$.
