Mfrhtyj

I got this problem from my son and he picked it from some local math competition. It's fairly simple:

For numbers $k,m,nin N$ ($kge2)$ we know the following:

$$left(frac mnright)^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_iin{0,1,2,dots9}$ ($i=1dots9)$ 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 mnright)^k=frac{a}{10^9-1}$$

$$m^k(10^9-1)=an^k$$

If we assume that $m$ and $n$ are coprime then:

$$n^kmid10^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)=9times111times1001001 \
=3^2times3times 37times3times333667=3^4times37times333667$$

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

You want to find whether there exists a prime $p$ such that $p^2mid n$, where $n=333667$. Suppose that such $p$ exists. Then, we know that
$$pleq sqrt{n}<578.$$
It is easily seen that $p>11$, so
$$13leq pleq 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 $qmid 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=3cdot 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.

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