+0  
 
0
81
1
avatar

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?

 Apr 9, 2022
 #1
avatar
0

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.

 Apr 10, 2022

12 Online Users

avatar