Let us consider the expression M^M+1, where M is a positive integer.

It can be verified that M=3 is the least value for which 2² divides M^M+1.

Given that n is a positive integer, find the least value of M (in terms of n) for which M^M+1 is divisible by 2ⁿ.

(In reply to solution by Jer)

Jer,

I agree with the result, and comment only to suggest how the math can possibly be avoided.

It is clear that all  numbers M^M+1 will be divisible by 1.

Half of those will be divisible by 2, a quarter divisible by 4, an eighth divisible by 8, and so on. For a number to be divisible by 4, it must already be divisible by 2, for a number to be divisible by 8, it must already be divisible by 4, and so on.

This is just the same as saying that the 1st, 3rd, 5th, 7th etc. have 2 as a divisor; the 3rd, 7th, 11th, 15th etc. have 4 as a divisor; the 7th, 15th, 23rd, 31st etc. have 8 as a divisor; and so on; and by exclusion, the initial numbers in each instance must be the smallest possible.

Hence the result you have already obtained.

Edited on May 2, 2014, 9:46 am

Posted by broll on 2014-05-02 09:38:04