Let n be a positive integer and let k be the number of positive integers less than 2^n that are invertible modulo 2^n. If 2^n = 8 (mod 13), then what is the remainder when k is divided by 13?
Firstly, a number is invertible mod n if and only if it’s relatively prime to n. So the numbers that are invertible mod 2^n are just the odd numbers. k=2^n−1, so 2k=2^n.
Substituting that into your equation means 2k≡8 mod 13. Since 2 is relatively prime to 13, it is invertible, so we can divide it off to get k≡4 mod 13.
