Drexel dragonThe Math ForumDonate to the Math Forum



Search All of the Math Forum:

Views expressed in these public forums are not endorsed by Drexel University or The Math Forum.


Math Forum » Discussions » sci.math.* » sci.math.independent

Topic: Quick Solution to Puzzle?
Replies: 12   Last Post: Aug 13, 2013 6:11 AM

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
James Waldby

Posts: 308
Registered: 1/27/11
Re: Quick Solution to Puzzle?
Posted: Aug 8, 2013 3:19 AM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

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 7-digit 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 7-digit 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*(N-1) = 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*(N-1) = (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 least-absolute-value 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



Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© Drexel University 1994-2014. All Rights Reserved.
The Math Forum is a research and educational enterprise of the Drexel University School of Education.