Solve $\left(\frac mn\right)^k=0.\overline{x_1x_2...x_9}$ (no computers!)

Question

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 :)

Answer 1

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.

Answer 2

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$.