If 2n - 1 = ab and 2k is the highest power of 2 dividing 2n - 2 + a - b then k is even.
Solution
We have b = (2n - 1)/a, hence 2n - 2 + a - b = 2n - 2 + a - (2n - 1)/a = (2na - 2a + a2 - 2n + 1)/a = (2n + a - 1)(a - 1)/a. Now a divides 2n - 1, so it must be odd. Let 2m be the highest power of 2 dividing a - 1. Then m < n, so 2m is also the highest power of 2 dividing 2n + (a - 1). Hence k = 2m.
© John Scholes
jscholes@kalva.demon.co.uk
11 Apr 2002