Eötvös 1911/3 solution

Problem 3

Prove that 3ⁿ + 1 is not divisible by 2ⁿ for n > 1.

Solution

We have 3² = 1 mod 8, so for n even 3ⁿ + 1 = 2 mod 8, and 3ⁿ + 1 is not divisible by 2². So since n ≥ 2 for n even, 3ⁿ + 1 is not divisible by 2ⁿ.

For n odd we have 3ⁿ + 1 = 4 mod 8, which is not divisible by 2³. So since n ≥ 3 for n odd, 3ⁿ + 1 is not divisible by 2ⁿ.