PDA

View Full Version : Number Theory


dfsacxzsdefa
Dec 7, 2010, 04:22 PM
Here's a toughie :):

Two six-digit numbers, A and B, have such a property that when cocatenated (like 5 and 34 to make 534), it is divisible by the product AB. Find A and B

There is only one answer!

ebaines
Dec 8, 2010, 12:48 PM
A=166667
B=333334

166667333334 is divisible by 166667*333334

:)

galactus
Dec 8, 2010, 02:50 PM
Interesting problem.

The concatenation of A and B equals A\cdot 10^{6}+B

And AB must divide into it

\frac{A\cdot 10^{6}+B}{AB}=p

where p is some integer and p>1.

Rearranging with some algebra, we get:

10^{6}=\frac{(Ap-1)B}{A}

From here, with some head-scratching, the numbers ebaines posted can be found. Try letting p=2 and p=3.

ebaines
Dec 8, 2010, 03:22 PM
Exactly my approach, except that from


\frac {A \cdot 10^6+B}{AB} = p


you can rearrange to get


10^6 + \frac B A = pB


and you can see that B must be a multiple of A. So let B = qA, and you get:


10^6 = q(pA-1)


Note that if we try p = 1 then 10^6 = q(A-1), which means B=qA is greater than 10^6 and hence not a 6-digit number. Hence as we proceed we can ignore the possibility that p = 1. So p>1.

In order for A to be a 6 digit number the product of q and p must be less than 10. Since q is a factor of 10^6, this means that q must be 1, 2, 4, 5, or 8. But since p >1, we can throw out q=5 and q=8. So let's try q=1, 2,or 4:

If q=1, then pA = 1,000,001. But the only prime factors of 1,000,001 are 101 and 9901, so the product qp is too big.

If q = 2, then pA = 500,001. The factors of 500,001 are 3 and 166,667. Hence p=3, A = 166,667, and B = 2* 166,667=333334. So this works!

if q = 4, then pA = 250,001. The smallest prime factor of this number is 53, and so qp > 10, which is no good.

Hence the solution I gave earlier is the only solution.