Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
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. =) –  Jens Aug 18 '10 at 14:40

3 Answers 3

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|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
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. –  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|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|improve this answer

Your Answer

 
discard

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