Determine the minimum value of a positive integer M, such that (1997^M – 1) is divisible by 2¹⁹⁹⁸.

Note: For an extra challenge, solve this puzzle without the aid of a computer program.

I can't see how a computer, without some analysis, would help here - the numbers seem too big - but maybe I'm missing something...

Assume that M = 2^m where m is an integer (*Justification later).

Then:    1997^M - 1 can be written as 1997^{2^m} - 1 and factorised as follows:

(1997-1)(1997+1)(1997²+1)(1997⁴+1)(1997⁸+1)......(1997^{2^(m-1)}+1)     (1)

[replacing the first two brackets by a single bracket and then repeating the

process reduces the complete product (1) to the required 1997^{2^m} - 1]

Now, the first bracket in (1) contains the factor 2² (1996 = 2² * 449), while

the remaining m brackets each contain the factor 2 to power 1 only. This is true

since each such bracket is of the form (4n + 1)^{2^r} + 1, which can be reduced

using the binomial theorem to the form 4n + 2 = 2(2n + 1).

Thus (1) contains 2^m+2, and so to be divisible by 2¹⁹⁹⁸, we need m + 2 = 1998,

giving m = 1996, and M = 2¹⁹⁹⁶, as the smallest possible value of M.

_________________________

* If M is not a power of 2, but lies between 2^m and 2^m+1, then it can be written

in the form M = 2^a + 2^b + 2^c +...+ 2^m  where a < b < c ...< m.

Now, writing A = 1997^{2^a} - 1, B = 1997^{2^b} - 1 ..., it follows

that   1997^M - 1 = (1997^{2^a} 1997^{2^b} 1997^{2^c}.......) - 1

                        = [(A + 1)(B + 1)(C + 1)....] - 1                                      (2)

From the initial theory, A contains a factor of 2^a+2, B contains 2^b+2 etc, so when

(2) is expanded (and the '1's drop out), the term containing the lowest

power of 2 is A. Thus 2^a+2 is the highest power of 2 that divides (2), and this

shows that 1997^M - 1 would contain a smaller power of 2 than 1997^{2^m} - 1,

and so justifies the assumption that M = 2^m gives the minimum value for M.

Edited on January 5, 2011, 6:55 pm

Posted by Harry on 2011-01-04 10:50:21