Integers that are power of a fixed integer mod every prime If $a,b \in \mathbb Z$ and the following property holds:
For every prime p in $\mathbb Z$, there exists an integer $n_p$ such that $b \equiv a^{n_p} \operatorname{mod} p $
Then can we deduce that there exists an integer n such that $b=a^n$?
 A: Yes.
First I prove the claim when $a$ and $b$ are positive.
To do this the first step is to prove by contradiction that $a^s = b^t$ for some integers $s,t$.
Suppose not. Then there are two primes $p$ and $q$ such that $v_p(a)v_q(b) \neq v_q(a)v_p(b)$.
Pick a prime $k$ large enough such that $a$ and $b$ are not $k$th powers and $v_p(a)v_q(b) \neq v_q(a)v_p(b) \pmod k$, and finally look at the primes $l$ congruent to $1$ mod $k$.
Since $a$ and $b$ are not $k$th powers, they are a $k$th power modulo $l$ around $1/k$ of the time (thanks to the Cebotarev density theorem).
However, your hypothesis implies that if $a$ is a $k$th power modulo $l$, then so is $b$. And so the primes $l$ that split in the Galois closure of $\Bbb Q(\sqrt[k]b)$ must be almost exactly the primes that split in the Galois closure of $\Bbb Q(\sqrt[k]a)$ (in fact, with a finite number of exception but you need slightly deeper stuff to prove it)
Still with the Cebotarev density theorem, we can then deduce that $\Bbb Q(\sqrt[k]a) = \Bbb Q(\sqrt[k]b)$, and then that one among $b/a, b/a^2, \ldots b/a^{k-1}$ is a $k$th power.
But this contradicts $v_p(a)v_q(b) \neq v_q(a)v_p(b) \pmod k$

Now we can assume that $a^s = b^t$, where $s$ and $t$ are coprime.  
Suppose $t \neq 1$. if $p$ divides $t$, then $a^s$ is a $p$th power, and so $a$ is also a $p$th power (because $p$ doesn't divide $s$), and so it is a $p$th power modulo every prime $l$. With your hypothesis we get that $b$ is also a $p$th power modulo every prime, which is enough to deduce that $b$ is a $p$th power. But then $a$ becomes a $p^2$th power, and then so does $b$ etc. This implies $a=b=1$, and we are done.
If $t = 1$ then we have $b=a^s$ and we are also done.

Now I prove the more general case with $a,b \in \Bbb Z$.
The case where $a$ or $b$ is zero is immediate.
If not then we look at $a^2$ and $b^2$.
If $b=a^{n_p} \pmod p$, then $b^2 = (a^2)^{n_p} \pmod p$, and so $a^2$ and $b^2$ still satisfy the hypothesis, and are positive, so we can apply the result we have just proven to them to get that $b^2 = (a^2)^s$ for some $s$.
Then $b = a^s$ or $b= -a^s$.
If $b= -a^s$ then $-1 = a^{n_p-s} \pmod p$ forall $p$ not dividing $a$. Let $p$ be a prime dividing $a-1$. Then $-1 = 1 \pmod p$ and so $p=2$. Also, $a$ can be a square mod $p$ only when $-1$ is, which means that $-a$ is a square, which leaves $a=-1$ as the only possibility (if $a = (-2^k)+1 = -c^2$ then $2^k = c^2+1 = 1,2 \pmod 4$ so $k=0$ or $k=1$).
Then $b = -a^s = a(a^s) = a^{s+1}$ is still a power of $a$.
