Composite residuosity statement.

41 Views Asked by At

Consider the following definition.

A number $z$ is said to be $n$-th residue modulo $n^2$ , if there exists a number $y \in \mathbb{Z}_{n^2}^*$ such that $$z\equiv y^n \mod n^2$$

Let us take $n=6$

then $$\Bbb{Z}_{n^2}^*=\{1,5,7,11,13,17,19,23,25,29,31,35\}$$

After performing $y^6\mod 36$ operation on all elements in above set , I am getting single value $1$. So 1 is only the $n$-th residue modulo $n^2$according to definition ?

I am understandng like this ..

$$\Bbb{Z}_{n^2}=\{0,1,2,3,\cdots35\}$$

On perform $y^6\mod 36$ on all elements on above set I am getting $0,1,9,28$. So , these values are the $n$-th residue modulo $n^2$ .

Which is correct ? In the definition it is given that $y \in Z_{n^2}^*$ , where I am going wrong ?