Short answer: invert b mod p-1 , not mod p . (If b not reversibly mod p-1 , the problem is unsolvable.)
While in the case x ≡ y (mod p) , then x^z ≡ y^z (mod p) , we cannot conclude that z^x ≡ z^y (mod p) . For example, by Fermat’s small theorem,
x^p ≡ x (mod p)
although p ≡ 0 (mod p) and x^0 = 1 .
However, Fermat’s Little Theorem gives us a solution. For integers x and y and a prime module p , if we can find the multiplicative inverse z for y mod p-1 , then
(x^y)^z = x^(yz) = x^(k(p-1) + 1) for some k = (x^(p-1))^k * x
If x ≡ 0 (mod p) , then (x^(p-1))^k * x ≡ x (mod p) , since both sides are congruent to 0.
If x !≡ 0 (mod p) , then we can get x^(p-1) ≡ 1 (mod p) from x^p ≡ x (mod p) , and we have (x^(p-1))^k * x ≡ 1^k * x ≡ x (mod p) .
Thus, (x^y)^z ≡ x (mod p) .
On the other hand, if y not invertible mod p-1 , then it turns out that we cannot restore x from x^y , since there are several possible values of x . For example, with x = 2, y = 3, p = 7 we have x^y ≡ 1 (mod p) , but x can be 1 .