# Number Theory congruence classes

if $n=p^2$ ($p$ is prime)

if $[x]=[1]\mod p$,

Then What is $[x]$ in$\mod n$?

i.e. $[x]=[?]\mod n$

where [x] belongs to (Zn)*

where (Zn)* = {[x] belonging to Zn such that gcd(x.n)=1)

-

All we can say is that $x\equiv 1+kp\pmod{p^2}$ for some $k$ with $0\le k\le p-1$.

So the congruence class $[x]$ of $x$ modulo $p^2$ can be any one of the $[1+kp]$.

-
n= p^2 it should be either {[1] or [n-1]} as the answer demands! –  UNM Jul 21 '13 at 3:52

By the Chinese Remainder Theorem, if $n$ is not a multiple of $p$, then $[x]$ could be any equivalence class modulo $n$. If $n$ is a multiple of $p$, then @Andre's answer applies; there is a little structure.

-
n= p^2 it should be either {[1] or [n-1]} as the answer demands! –  UNM Jul 21 '13 at 3:45
@user85221, that is incorrect. For example, if $p=7$ and $n=49$, consider $x=1,8,15,22$. All of these satisfy $[x]=[1]$ mod $p$, but they are $[1], [8], [15], [22]$ mod $49$, respectively. –  vadim123 Jul 21 '13 at 4:08
That is a completely different question; Andre and I answered the question that you asked. –  vadim123 Jul 21 '13 at 4:17