10
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Wojowu Jan 2 at 21:14
  • $\begingroup$ @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. $\endgroup$ – Oldboy Jan 2 at 21:17
  • $\begingroup$ 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... $\endgroup$ – Wojowu Jan 2 at 21:22
  • $\begingroup$ @JohnDouma A digit can be zero, I have clarified this. $\endgroup$ – Oldboy Jan 2 at 21:28
  • $\begingroup$ There was no need to clarify. I just misunderstood. That's why I deleted the comment. $\endgroup$ – John Douma Jan 2 at 21:30
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Ross Millikan Jan 2 at 22:40
2
$\begingroup$

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

$\endgroup$
  • 4
    $\begingroup$ 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$.) $\endgroup$ – TonyK Jan 2 at 22:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.