+0  
 
0
93
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\equiv 3\pmod{13}\), then what is the remainder when k is divided by 13 ?

 Dec 21, 2020
 #1
avatar
0

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

 Dec 21, 2020

28 Online Users

avatar
avatar