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

• Well, you need to somehow know at least that $333667$ is squarefree - otherwise, for its factor $p^2$, $1/p^2$ would have purely periodic expansion of length $9$. The problem at this point is actually equivalent to checking if $333667$ is squarefree. – Wojowu Jan 2 at 21:14
• @Wojowu Yes, that's the key point. If we know that 333667 is squarefree, we are done. But I have no idea how to prove it quickly. – Oldboy Jan 2 at 21:17
• Testing squarefree-ness is a known problem in computational complexity with no known polynomial-time algorithm. This doesn't exactly tell us there is no way to solve this problem easily, since $333667$ might have some magical properties which make it simpler, but I am being a little skeptical here... – Wojowu Jan 2 at 21:22
• @JohnDouma A digit can be zero, I have clarified this. – Oldboy Jan 2 at 21:28
• There was no need to clarify. I just misunderstood. That's why I deleted the comment. – John Douma Jan 2 at 21:30

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 cube root is not good enough because we could have $333667=p^2q$ for $p,q$ prime. But if we show there is no prime factor smaller than the cube root we are done. – Ross Millikan Jan 2 at 22:40
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$$.
• Well, you also have to show that $333667$ is not a perfect square. (But that's easy, because a perfect square can't end in $7$.) – TonyK Jan 2 at 22:18