1994 OIM Problems/Problem 1
Problem
A natural number is said to be "sensible" if there exists an integer , with , such that the representation of in base 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 Is a "sensible" number as it can be expressed as , where there are
Part Let us prove that cannot be expressed as such. Notice that is a prime, which means that as it cannot be or else . Therefore, we need to prove that there does not exist such that Assume on the contrary, there exists such . Then we have Notice that taking mod results in . Notice plugging in some small values, , they don’t work And similarly. So the next smallest value of is , implying that because As grows faster than when and when
So
If then , which is not true because .
If then , which is not true because So there is no solution.
Part Let us show that is sensible.
Comment: any composite number other than , where is a prime is sensible as E.g ~Archieguan