Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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)

share|cite|improve this question
Since there are only 5040 permutations of {1,2,..,7}, one can simply check all of them. That does not increase your understanding, though. =) – Jens Aug 18 '10 at 14:40
up vote 10 down vote accepted

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.

share|cite|improve this answer
Is is possible for $1$ times $k$ to be congruent to $1$ (modulo $9$) when $2\le k\le 8$? – Robin Chapman Aug 18 '10 at 14:40
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. – yatima2975 Aug 18 '10 at 14:42

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.

share|cite|improve this answer

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.