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

Reset to default
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$
    – Donald Splutterwit
    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$

You must log in to answer this question.

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