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$?

Solution 1:

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.

Solution 2:

Note: The material below makes only a small amount of progress towards a solution of the problem.

Qiaochu Yuan remarked that if the order of $x$ is equal to the order of $y$ modulo every prime $p$ that divides neither $x$ nor $y$, then the square-free parts of $x$ and $y$ must be the same. The following is a response to a request from Marquis for the details of the argument. It is likely that the argument below is close to the one Qiaochu Yuan had in mind, but did not have time to write down.

Actually we only need to assume that the orders have the same parity for primes congruent to $3$ modulo $4$.

Let $p$ be a prime congruent to $3$ modulo $4$. Then all the quadratic residues of $p$ have odd order, and all the non-residues have even order. So if $p$ is congruent to $3$ modulo $4$, and the order of $x$ modulo $p$ is equal to the order of $y$ modulo $p$, then in particular $x$ and $y$ are both quadratic residues or are both quadratic non-residues modulo $p$.

Let $x_0$, $y_0$ be the square-free parts of $x$ and $y$. Whether a number is a residue or a non-residue is determined by the quadratic character of its square-free part. Suppose first that $x_0$ and $y_0$ are both positive and odd.

If $x_0 \ne y_0$, there is a prime that divides one of them but not the other. Suppose that $q$ divides $x_0$ but does not divide $y_0$.

We will build a prime $p$ that satisfies a certain bunch of congruences. First of all, we want $p \equiv 3 \pmod{4}$. Secondly, for every prime $p_i$ other than $q$ that divides $x_0$ or $y_0$, we want to make sure that $p_i$ is a quadratic residue of $p$.

This is not hard to arrange. If $p_i \equiv 1 \pmod{4}$, make sure that $p \equiv 1 \pmod {p_i}$. Then the Legendre symbol $(p/p_i)$ is equal to $1$, and therefore by Quadratic Reciprocity so is $(p_i/p)$. If $p_i \equiv 3 \pmod{4}$, make sure that $p \equiv -1 \pmod{p_i}$. Since $(-1/p_i)=-1$, it follows that $(p/p_i)=-1$, and so by Quadratic Reciprocity $(p_i/p)=1$.

Finally, make sure that $(q/p)=-1$. This is again easy to arrange. If $q \equiv 1 \pmod{4}$, make $p \equiv a \pmod {q}$, where $a$ is a quadratic non-residue of $q$, and if $q \equiv 3 \pmod{4}$, make $p \equiv a \pmod{q}$, where $a$ is a quadratic residue of $q$.

By the Chinese Remainder Theorem, the system of congruences we have described has a solution $b$ relatively prime to $M$, where $M=4q\prod p_i$.

But by Dirichlet's Theorem on primes in arithmetic progression, there are infinitely many primes congruent to $b$ modulo $M$. Let $p$ be such a prime. Then $y_0$ is a quadratic residue of $p$, and hence $y$ has odd order modulo $p$, while $x_0$ is a quadratic non-residue of $p$, meaning that $x$ has even order modulo $p$, contradicting the fact that $x$ and $y$ have the same order modulo $p$.

Other cases can be dealt with in the same way. If both $x_0$ and $y_0$ are positive and even, we want to make sure that $2$ is a quadratic residue of $p$. So instead of $p \equiv 3 \pmod{4}$, use the stronger congruence $p \equiv - 1 \pmod{8}$. This ensures that $(2/p)=1$. If one of $x_0$ and $y_0$ (say $x_0$) is even, and the other odd, we want $p \equiv 3 \pmod{8}$ to make sure that $2$ is a quadratic non-residue of $p$, and we make sure, in the same way as before, that for the remaining primes $p_i$ that divide $x_0$ or $y_0$, $(p_i/p)=1$.

Finally, we deal with the possibility that $x_0$, or $y_0$, or both, are negative. If $x_0$ is negative and $y_0$ is not, make sure that $|x_0|$ and $y_0$ are both quadratic residues of $p$ in the usual way. Then $x_0$ will be a non-residue. If $x_0$ and $y_0$ are both negative, make sure that $|x_0|$ is a non-residue and $|y_0|$ is a residue in the usual way. Then $x_0$ is a residue and $y_0$ is not, and again we reach a contradiction.

(We could have done things more uniformly by treating $-1$ as a "prime," and there really was no need to separate out the prime $2$, but there is not much harm in having extra two paragraphs, bytes are cheap.)

Continuation? This is only partway towards a solution of the real problem, and it is the easy, or at least routine, part. Maybe "quadratic" arguments can be exploited further. But I suspect that something quite different will be needed to push beyond the $x_0=y_0$ conclusion. Unfortunately, we know almost nothing about the relationship between orders modulo distinct primes, except in a very few special cases. And if there exist distinct $x$, $y$ which "always" have the same order, then there exist perfect squares $x$, $y$ with the same property.

Solution 3:

[This is an answer to the original form of the question. In the meantime the question has been clarified to refer to the multiplicative order; this seems like a much more interesting and potentially difficult question, though I'm pretty sure the answer must be yes.]

I may be missing something, but it seems the answer is a straightforward no. All non-identity elements in $\mathbb{Z} /p \mathbb{Z}$ have the same order $p$, which is different from the order $1$ of the identity element; so saying that all the orders are the same amounts to saying that $x$ and $y$ are divisible by the same primes. But different powers of the same prime, e.g. $x=2$ and $y=4$, are divisible by the same primes, and hence have the same orders.

Solution 4:

A related fact: integers are determined by their remainders modulo all the primes:

Let $p_1 < p_2 < ...$ be a list of distinct primes. Then (via the Chinese remainder theorem for example) $Z_{p_1 \times ... \times p_n}$ is isomorphic to $Z_{p_1} \times .... \times Z_{p_n}$ via the map $$a\pmod {p_1....p_n} \rightarrow (a\pmod {p_1},....,a\pmod {p_n})$$ Thus any two distinct numbers from $1$ to $p_1....p_n$ will have distinct residues mod $p_i$ for some $i$. Thus if $a$ and $b$ are any two distinct positive integers at all, by taking $n$ large enough so that $a$ and $b$ are both less than $p_1...p_n$, there will be some $p_i$ such that $a \pmod{p_i}$ is distinct from $b \pmod{p_i}$.