Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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)

share|improve this question
add comment

2 Answers

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]$.

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

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.

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.