Find a reduced residue system modulo $2^m$ where m is a positive integer
Please, help.

Question

Find a reduced residue system modulo $2^m$ where m is a positive integer
Please, help.

loser66 · Answer

I know that 2^m is an even number and its reduce residue is all odd number in the set $\{1,2, 3, ......,2^{m-1}\} $. That is $\{2k -1| 1< k < 2^{m-1}\}$
All I want is finding it by $\phi (2^m)$ but I don't know how.

ganeshie8 · Answer

I don't get the question... could you please share full details...

loser66 · Answer

Is my answer correct? I meant reduce residue modulo $2^m = \{2k-1 | 1<k < 2^{m-1}\}$

imqwerty · Answer

yes

loser66 · Answer

And we have some formula to find $\phi (2^m)$, right?

imqwerty · Answer

but i don't know what is  ϕ(2^m)

ganeshie8 · Answer

sorry i still don't understand the question...

loser66 · Answer

$\phi (2^m)= $ number of the terms in residue of 2^m, namely a, such that  (a, 2^m) =1

ikram002p · Answer

ur answer is correct for the reduced residues

ganeshie8 · Answer

$\phi(p^k) = p^k - p^{k-1}$

loser66 · Answer

Like this. if number is 5, then $\phi (5) = 4$ because in {0,1,2,3,4}, (1,5)=1, (2,5) =1, (3,5) =1 and (4,5) =1
we have 4 number "a" satisfy (a,5) =1
@imqwerty

ikram002p · Answer

but in mean while phi(2^m) it counted terms in ur set =D

ganeshie8 · Answer

Notice that the integers that are "not" relatively prime to $2^m$ are :
$$\{1*2, 2*2, 3*2, \ldots, 2^{m-1}*2\}$$

that means there are exactly $2^{m-1}$ integers less than $2^m$ that are "not" relatively prime to $2^m$

ikram002p · Answer

what is good about about 2^m is that the odd set less that 2^m satisfy the reduced residue which is what u did @Loser66 .

loser66 · Answer

@ganeshie8  I got you

loser66 · Answer

@ikram002p  I want to solve it by arithmetic way,

ikram002p · Answer

=)

ganeshie8 · Answer

$\phi$ is a multiplicative function, so we can evaluate it for any integer using :
$$\phi(ab) = \phi(a)*\phi(b)$$

where $(a,b)=1$

ganeshie8 · Answer

for example : 
$\phi(15) = \phi(3*5) = \phi(3)*\phi(5) = (3-1)(5-1)=8$

that means, there are exactly 8 positive integers less than 15 that are coprime with 15.

ganeshie8 · Answer

since every positive integer less than a prime is relatively prime, we also have : 
$\phi(p)=p-1$ 

for a prime, $p$

ganeshie8 · Answer

those two properties allow you to compute $\phi(n)$ for any integer $n$

loser66 · Answer

how? if n is not prime, how can you compute phi (n) ?