1994 OIM Problems/Problem 1

Problem

A natural number $n$ is said to be "sensible" if there exists an integer $r$ , with $1<r<n-1$ , such that the representation of $n$ in base $r$ has all its digits equal. For example, 62 and 15 are "sensible", since 62 is 222 in base 5 and 15 is 33 in base 4.

Prove that 1993 is NOT "sensible" but 1994 is.

~translated into English by Tomas Diaz. ~orders@tomasdiaz.com

Solution

Lemma: Every number that can be expressed as $b \cdot \frac{r^d-1}{r-1} , b < r$ Is a "sensible" number as it can be expressed as $b\cdots b _ r$ , where there are $d$ $r’s$

Part $1:$ Let us prove that $1993$ cannot be expressed as such. Notice that $1993$ is a prime, which means that $b = 1$ as it cannot be $1993$ or else $r > 1994$ . Therefore, we need to prove that there does not exist $d,r$ such that $\frac{r^d-1}{r-1} =1993$ Assume on the contrary, there exists such $d,r$ . Then we have $r^d - 1 = 1993r - 1993 \implies r^d = 1993r - 1992$ Notice that taking mod $(r)$ results in $r \mid 1992$ . Notice plugging in some small values, $r = 2,3,4,6,8,12,24$ , they don’t work $1992 \cdot 2 - 1992 = 1994 \neq 2^d$ And similarly. So the next smallest value of $r$ is $83$ , implying that $d < 3$ because $\text{when} \hspace{0.2cm} r \geq 45, r^3 > 1993r -1992$ As $r^3$ grows faster than $1992r$ when $r > \sqrt{1992} \implies r \geq 45$ and when $r = 45, 45^3 = 91125 > 87693 = 1993 \cdot 45 - 1992$

So $d = 1,2$

If $d = 1,$ then $1992(r-1) = 0 \implies r = 1$ , which is not true because $r>1$ . If $d = 2,$ then $(r-1)(r-1992) = 0 \implies r = 1,1992$ , which is not true because $1<r<1992$ So there is no solution.

Part $2:$ Let us show that $1994$ is sensible. $1994 = 2 \cdot 997 = 2\cdot (996 + 1) = 22_{996}$

Comment: any composite number other than $p^2$ , where $p$ is a prime is sensible as $n \cdot r = n \cdot (1 + (r-1)) = nn_{r-1}$ E.g $69 = 3\cdot 23 = 33_{22}$ ~Archieguan

Page

Toolbox

Search

1994 OIM Problems/Problem 1

Problem

Solution

See also