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\equiv 3\pmod{13}\), then what is the remainder when k is divided by 13 ?
2^n mod 13 = 3, solve for n
n = 12 m + 4 , where m =0, 1, 2, 3........etc.
The smallest n = 4 and 2^n =2^4 == 16.
So, the positive integers < 16 that are invertible modulo 16, which = k are:
1 - The mmi = 1 [mmi stands for "modular multiplicative inverse"]
3 - The mmi = 11
5 - The mmi = 13
7 - The mmi = 7
9 - The mmi = 9
11 - The mmi = 3
13 - The mmi = 5
15 - The mmi = 15
So, k == 8 and 8 mod 13==8
