23
$\begingroup$

Prove that every positive integer divides a number such as $70, 700, 7770, 77000$, whose decimal representation consists of one or more $7$’s followed by one or more $0$’s.
Hint:$7$; $77$; $777$; $7777$

I know that I am supposed to use the pigeonhole principle, but I can't figure out how. I know that it probably comes down to proving that all odd numbers divide some number of the form $7, 77, 777$, etc.

$\endgroup$

2 Answers 2

55
$\begingroup$

Consider the set of numbers $7 \times \sum_{i=0}^{M} 10^i$ for $M=0, \cdots N$ (That is the set of numbers, of length $1$ to $N+1$, all of whose digits are $7$). There are $N+1$ elements. Now consider them modulo $N$ . By the pigeon hole principle, there must be two that are congruent, subtract these and they will be divisible by $N$.

Edit: Let $a_{M} = 7 \times \sum_{i=0}^{M} 10^i$ (The $M+1$ digit number consisiting of only $7$'s) and $a_{M} \equiv b_{M} \pmod {N}$. There are only $N$ possible values for the $b$'s, so by the PHP there exist two $M$ values that are equal, say $p$ and $q$ (with $p>q$). We have $ a_{p} \equiv a_q \pmod {N}$. "Subtract these" and we have
\begin{eqnarray*} a_{p} - a_q = \underbrace{7 \cdots 7 }_{p-q \text{ 7's}} \underbrace{0 \cdots 0 }_{q+1 \text{ 0's}} \equiv 0 \pmod {N}. \end{eqnarray*}

$\endgroup$
8
  • 1
    $\begingroup$ I know a different, much more complicated, proof. But this one is simply amazing! $\endgroup$
    – yo'
    Oct 9, 2017 at 6:42
  • $\begingroup$ Can you please elaborate on "subtract these"--from what? "they will be divisible by N"--who are they? To be completely honest, I don't really understand the question, because, obviously, as stated it doesn't make sense, since not every positive integer divides 70, let alone every number of that shape. I hoped to maybe understand it from the answer given, but it's not very helpful either :) $\endgroup$
    – wvxvw
    Oct 9, 2017 at 7:03
  • $\begingroup$ @wvxvw the two numbers from that set that are congruent mod N, subtract the smaller from the larger. The result will be a number of the requisite form (the smaller will cancel some of the 7s from the tail end of the larger, leaving 0s), which is a multiple of N (if a = b (mod N), then a - b = 0 (mod N)). The goal is to prove that every integer divides some number of the form, not all of them. So here we produce, on demand, a number which is a multiple of any given integer. $\endgroup$
    – hobbs
    Oct 9, 2017 at 7:28
  • 1
    $\begingroup$ @hobbs Thanks for adding that explanation. I have added an edit that essentially says the same thing. wvxvw: please read hobbs comment & my edit (Do not hesitate if your require further clarification). $\endgroup$ Oct 9, 2017 at 7:33
  • 1
    $\begingroup$ @wvxvw Note that not every odd number divides a number of the form 777... . 5, 15, 25, ... are all counterexamples. $\endgroup$
    – saulspatz
    Oct 9, 2017 at 13:06
8
$\begingroup$

Take some integer $n$. Consider the numbers $$x_i= \underbrace{77...77}_i \text{ mod } n\qquad\text{for $i\in\Bbb N$}$$

The pidgeonhole principle tells you that there are $x_i=x_j$ with $i> j$. Then we have $(x_i-x_j)\equiv 0 \pmod n$ (i.e. $n$ divides $x_i-x_j$), as well as

$$x_i-x_j = \underbrace{77...77}_{i-j}\overbrace{00...00}^{j}.$$

$\endgroup$

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.