For fuck's sake, the goatfinger admin copied posts from here, now I know why you never replied to me. I fucking knew the guy was some imageboard autist who desperately wanted to run a textboard the moment he volunteered.
Anyway, what you are writing about is solvable through the Chinese remainder theorem if p ≠ q, and trivial otherwise.
According to the CRT,
φ :
ℤ/
pqℤ ->
ℤ/
pℤ ×
ℤ/
qℤφ(x + pqℤ) = (x + pℤ, x + qℤ))
is a ring isomorphism and thus bijective. This means that every one-sided inverse of φ is the two-sided inverse of φ. Consider then
ψ(a + pℤ, b + qℤ) = aqM + bpN + pqℤ,
where M is the inverse of q modulo p and N is the inverse of p modulo q.
ψ satisfies φψ = id
ℤ/pℤ × ℤ/qℤ by construction and is therefore the inverse of φ.
If p = q, the challenge boils down to calculating a square root modulo pq, which is equivalent to factorization. But you can easily check whether pq is a square, so this is simple. For
>>7, you have to apply the CRT twice.