4
$\begingroup$

This was asked to me by a friend. I tried this problem for a long time, but i couldn't solve it. Seems interesting though.

Prove that it is impossible to construct two different seven digit numbers, one of which is divisible by the other, out of the digits 1,2,3,4,5,6,7 (All seven digits must be in each number)

  • 3
    Since there are only 5040 permutations of {1,2,..,7}, one can simply check all of them. That does not increase your understanding, though. =)2010-08-18

3 Answers 3

10

Say the numbers are x and y and y divides x.

Consider the remainder upon dividing both numbers by 9. Both leave a remainder 1 (as sum of digits leaves a remainder 1).

So x = ky where 2 <= k <= 8 is not possible.

  • 0
    Is is possible for $1$ times $k$ to be congruent to $1$ (modulo $9$) when $2\le k\le 8$?2010-08-18
  • 1
    Since x = ky, this also holds modulo 9. 1=x=ky=k mod 9. Since the numbers have the same number of digits, k must be < 10, therefore k = 1.2010-08-18
2

HINT $\; ax = b,\; (a,m)=1 \;\Rightarrow\; x = b/a \;\;{\rm mod}\; m \;$ is the unique solution such that $\; \; 0\le x < m. \;$

Now put $\; m = 9, \;$ i.e. cast out nines. This is a ubiquitous technique for recreational problems of this ilk.

CHALLENGE Find a natural generalization to arbitrary length integers.

1

7654321/1234567 = 6. something

so x = ky where 2<=k<=6

sum of the digits are not divisible by 3 so no 3 and 6.

now x = ky where k = 2,4 or 5 so not possible.