1
$\begingroup$

Given a positive integer $n,$ prove that there is a positive integer $m$ that to base ten contains only the digits $0$ and $1$ such that $n|m.$ Prove that the same holds for digits $0$ and $2,$ or $0$ and $3,$ $\cdots,$ or $0$ and $9,$ but for no other pair of digits.

I tried solving it as follows:

We consider $n$ numbers $1,11,111,\cdots,\underbrace{ 111\cdots 1}_{\text{n 1's}}.$ We assume, neither of these numbers leave a remainder of $0$ when divided by $n.$ For if, there were such a number in the above list, we are done. So, the possible remainders on division by $n$ are $1,2,\cdots,n-1.$ So, we have, $n$ numbers and $n-1$ remainders. By PHP, there exists two numbers that leave the same remainder on dividing by $n.$ We call these two numbers in particular as $p=\frac{10^p-1}{9}$ and $q=\frac{10^q-1}{9}.$ Then, WLOG, let $p\gt q$ and we have, $m=\frac{10^p-10^q}{9}\equiv 0\pmod n$ and $m$ is in fact the required type of number.

Similarly, for a digit $2\leq i\leq 9$ we can proceed similarly by consider the list : $$i,ii,iii,\cdots, \underbrace {iii\cdots i}_{\text{n times}},$$ and then proceeding similarly as above.


But then, I don't know how to show, that this is not true "for no other pair of digits."

It seems they want us to show that, if $(a,b)$ is any other digit, $n$ won't divide it! This seems a little weird and difficult to show.

$\endgroup$
16
  • 1
    $\begingroup$ @ThomasFinley As far as I can tell, you have correctly answered the first part. As for the second part, your interpretation of "Prove $n\nmid m$ when $m$ is made up of any other pair of digits" is somewhat inaccurate. It should instead be phrased something like "Prove there's at least one $n$ where $n\nmid m$ when $m$ is made up of any other pair of digits". As for how to prove this, I've already given a fairly detailed explanation in my earlier comment. Also, as for it being "sufficient", I believe it should be, but that would be up to whoever is reading your answer to determine. $\endgroup$ Jul 21, 2023 at 6:03
  • 2
    $\begingroup$ @Prem, I'm looking at the book (exercise 50 on page 59), and that is the exact wording. (And, it's not ambiguous.) $\endgroup$ Jul 21, 2023 at 6:24
  • 1
    $\begingroup$ Let's write $P_{a,b}(m)$ for the statement, $m$ contains only the digits $a$ and $b$. The problem is, For all $n$, for all $a$, there exists $m$ such that $P_{0,a}(m)$ and $n$ divides $m$. Show that, if $ab\ne0$, then it is not true that for all $n$ there exists $m$ such that $P_{a,b}(m)$ and $n$ divides $m$. To do the second part, all you need is a single value of $n$ for which there is no such $m$. And $n=10$ is such an $n$. $\endgroup$ Jul 21, 2023 at 6:29
  • 1
    $\begingroup$ @Prem, "given $n$, there exists $m$" means "for every $n$, there exists $m$". $\endgroup$ Jul 21, 2023 at 6:41
  • 2
    $\begingroup$ "given $n$" means "for every $n$". "given $n$" means "for every $n$". "given $n$" means "for every $n$". "given $n$" means "for every $n$". "given $n$" means "for every $n$". "given $n$" means "for every $n$". "given $n$" means "for every $n$". "given $n$" means "for every $n$". "given $n$" means "for every $n$". "given $n$" means "for every $n$". "given $n$" means "for every $n$". "given $n$" means "for every $n$". @Prem $\endgroup$ Jul 21, 2023 at 6:48

1 Answer 1

3
$\begingroup$

As far as I can tell, you've correctly answered the first part of the problem.

Regarding the second part, since it's asking about using a pair of decimal digits other than $(0,1), (0,2), \ldots, (0,9)$, this means it's a pair of decimal digits where neither of them is $0$. However, then with the first part of "Given a positive integer $n$", if we choose something like $n = 10$, all integral multiples of it will have, in base $10$, a $0$ as the final digit. Thus, there's no positive integer $m$ where $n\mid m$ and $m$ contains, in base $10$, only $2$ non-zero digits.

Regarding the question's phrasing, I don't consider it to be ambiguous because it requires that, regardless of which positive integer $n$ is "given", we can always find a corresponding $m$ meeting the stated conditions. Nonetheless, I suggest the first part could be made a bit clearer by, for example, using "Prove that, for any given positive integer $n$, there is a positive integer $m$ ..." instead, or even just by changing the "a" in "Given a positive ..." to "any".

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .