Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
Drexel University or The Math Forum.



Re: Quick Solution to Puzzle?
Posted:
Aug 8, 2013 3:19 AM


On Wed, 07 Aug 2013 21:25:27 0400, Jim Burns wrote: > On 8/7/2013 8:12 AM, J.B. Wood wrote: ... >> Find a 7digit phone number (I told you the book was old) such that when >> the first three digits are subtracted from the last four and the result >> squared you obtain the original 7digit number. The answer is 1201216. >> I'm uncertain if there are any other integer solutions. The problem >> can be reduced to a quadratic in two unknowns and numbers substituted >> until the answer is obtained. Does anyone know of an alternative, >> relatively fast (pencil & paper) solution? Thanks for your time and >> comment. [snip] > N*(N1) = 10001*M > > Note that 10001 factors to 73*137. [snip] > What I want is a multiple of 73 and a multiple of 137 > that differ by 1. Muddling about: > 137  73 = 64 > 73  64 = 9 = 2(73)  137 > 64  7(9) = 1 = 8(137)  15(73) > Bingo. > > Let N = 8*137 = 1096 and N  1 = 15*73 = 1095. > Then N*(N1) = (137*73)*(8*15) = 10001*120 > and K = N + M = 1096 + 120 = 1216 > and the telephone number is 1201216. > > I have not checked for uniqueness of the solution. > I think that someone better at finding solutions > to 73*a + 137*b = +1 or 1 would be able to help > there.
Since 73 and 137 are primes, their GCD is 1, so it is straightforward to use the extended Euclidean algorithm to obtain 1 = 15 * 73 + 8 * 137 for "a multiple of 73 and a multiple of 137 that differ by 1." Although integers p, q such that 1 = p*137 + q*73 are not unique, by Bezout's lemma 8 and 15 are the leastabsolutevalue such integers.
<http://en.wikipedia.org/wiki/Greatest_common_divisor> <http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm> <http://en.wikipedia.org/wiki/B%C3%A9zout%27s_identity>
 jiw



