Is an integer uniquely determined by its multiplicative order mod every prime Let $x$ and $y$ be nonzero integers and $\mathrm{ord}_p(w)$ be the multiplicative order of $w$ in $ \mathbb{Z} /p \mathbb{Z} $. If $\mathrm{ord}_p(x) = \mathrm{ord}_p(y)$ for all primes (Edit: not dividing $x$ or $y$), does this imply $x=y$? 

Yes. It is a consequence of Chebotarev's density theorem that if two Galois extensions $L_1, L_2$ of a number field $K$ have the property that the same primes split in both of them (or even almost all the same primes), then in fact $L_1 = L_2$. The condition in the OP implies that the polynomials $t^k - x, t^k - y$ split at the same primes over $\mathbb{Q}$ for all $k$, hence that their splitting fields over $\mathbb{Q}$ are identical. Let $L_k$ denote this splitting field. Then $\mathbb{Q}(\zeta_k) \subset L_k$ where $\zeta_k$ is a primitive $n^{th}$ root of unity; moreover, $L_k$ is a Kummer extension of $\mathbb{Q}(\zeta_k)$ with Galois group $\text{Gal}(L_k/\mathbb{Q}(\zeta_k)) \cong C_k$ acting on a root of either $t^k - x$ or $t^k - y$ by multiplication by a primitive $k^{th}$ root of unity.
Let $a^k = x, b^k = y$. WLOG a generator of $C_k$ acts on $a$ by multiplication by $\zeta_k$ and acts on $b$ by multiplication by $\zeta_k^m$ for some $m \in (\mathbb{Z}/k\mathbb{Z})^{\ast}$. It follows that $\frac{a^m}{b}$ is fixed under the action of $C_k$, hence $\frac{a^m}{b} \in \mathbb{Q}(\zeta_k)$ and 
$$\left( \frac{a^m}{b} \right)^k = \frac{x^m}{y}.$$
When $k = 2$ we conclude that $x, y$ have the same squarefree parts; in particular, $x, y$ have the same sign. In general, I want to conclude that 

For infinitely many $k$, we have $\frac{a^m}{b} \in \mathbb{Q}$ for some choice of $a, b$. 

Edit: This is true for all odd $k$. 
The above result allows us to finish. Given a prime $p$ let $\nu_p$ denote the function which, given an integer, returns the exponent of $p$ in the prime factorization of that integer. Given two primes $p_i, p_j$ and fixing $k$, the condition that $\frac{a^m}{b} \in \mathbb{Q}$ implies that
$$\nu_{p_i}(x) \nu_{p_j}(y) \equiv \nu_{p_j}(x) \nu_{p_i}(y) \bmod k.$$
If this is true for infinitely many $k$, it follows that $\nu_{p_i}(x) \nu_{p_j}(x) = \nu_{p_j}(x) \nu_{p_i}(x)$ for all $i, j$. Together with the fact that $x, y$ have the same sign, it follows that one of $x, y$ is a power of the other, say an $n^{th}$ power. If $n$ has a nontrivial odd factor $o$, then this is a contradiction by taking $k$ a sufficiently large power of $o$; otherwise, $n$ is a power of $2$, and by taking $k$ a sufficiently large power of $2$ we get a contradiction using the more detailed result in the link. 
