# $a^n-1$ and $b^n-1$ have the same set of prime factors for each $n\in\Bbb{Z}^+$, show that $a=b$.

Let $$a,b$$ be two positive integers, if $$a^n-1$$ and $$b^n-1$$ have the same set of prime factors for each $$n\in\Bbb{Z}^+$$, then $$a=b$$.

It seems to be not hard, but I have no idea. Any hint is welcome.

Edit: As the comment points out, it is probably not easy. I thought it is easy because it is kind of intuitively correct. I tried to study the Zsigomondy primes as $$n$$ increases, but it is not successful.

• “It seems to be not hard”. I think this problem elementarily implies the N7 of the IMO Shortlist 2009. So... it probably isn’t easy. Commented Oct 30, 2020 at 22:29
• @Mindlack I looked at the N7 of the IMO 2009 shortlist. I don't see how this problem implies it. For any $a\neq b$, we got some $n$ such that $a^n-1$ and $b^n-1$ has different set of prime factors, but it does not (at least not directly) imply that $(a^n-1)(b^n-1)$ is not a perfect square. Commented Oct 30, 2020 at 22:45
• If $a,b$ are as in the N7: Assume there is some $n$ such that $a^n-1$ has a prime factor $p$ not dividing $b^n-1$. Then $a^n-1$ has an even $p$-adic valuation, as $(a^n-1)(b^n-1)$ is a square. So $(a^{pn}-1)(b^{pn}-1)$ also has an even $p$-adic valuation. But $b^{pn}-1=b^n-1$ mod $p$ so isn’t divisible by $p$, so the valuation of $a^{np}-1$ is even. But by LTE, the $p$-aduc valuation of $a^{np}-1$ is that of $a^n-1$ (which is even) plus one, so is odd. We get a contradiction, so by the problem of the OP $a=b$. That’s why I wrote “elementarily implies” instead of “obviously implies”. Commented Oct 30, 2020 at 22:53
• In any event @MathEric this is quite a good problem!
– Mike
Commented Oct 31, 2020 at 19:16

The condition that $$a^n-1$$ and $$b^n-1$$ have the same prime factors for every $$n$$ is equivalent to $$a$$ and $$b$$ having the same order mod $$p$$ for every $$p$$. Equivalently, for every positive integer $$k$$ and every prime $$p$$, $$a$$ is a $$k$$-th power mod $$p$$ if and only if $$b$$ is a $$k$$-th power mod $$p$$. I will argue that for fixed $$a\neq b$$ and every sufficiently large prime value of $$k$$, there is a positive proportion of primes $$p$$ for which $$a$$ is a $$k$$-th power mod $$p$$ but $$b$$ is not.
Suppose $$2\leq a< b$$. Let $$q>b$$ be a prime, and consider the field $$K=\mathbb{Q}(\sqrt[q]{a},\sqrt[q]{b},\zeta_q)$$, where $$\zeta_q$$ is a primitive $$q$$-th root of unity. Then $$G:=\operatorname{Gal}(L/\mathbb{Q})\cong \mathbb{F}_q^\times \ltimes\left(\mathbb{F}_q\times\mathbb{F}_q\right).$$ Then $$\mathbb{Q}(\sqrt[q]{a})$$ is the fixed field of $$H_1:=\mathbb{F}_q^\times \ltimes\left(\{0\}\times\mathbb{F}_q\right)$$, and $$\mathbb{Q}(\sqrt[q]{b})$$ is the fixed field of $$H_2:=\mathbb{F}_q^\times \ltimes\left(\mathbb{F}_q\times \{0\}\right)$$. If $$p$$ is a rational prime coprime to $$a$$, $$b$$, and $$q$$, then $$a$$ is a $$q$$-th power mod $$p$$ if and only if the Frobenius conjugacy class of $$p$$ in $$G$$ intersects $$H_1$$, and $$b$$ is a $$q$$-th power mod $$p$$ if and only if the Frobenius conjugacy class of $$p$$ in $$G$$ intersects $$H_2$$. Now, by the Chebotarev density theory, there exist a positive proportion of primes $$p$$ whose Frobenius conjugacy class contains $$(1,0,1)\in G$$. Then the conjugacy class intersects $$H_1$$ but not $$H_2$$, so for such $$p$$, $$a$$ is a $$q$$-th power mod $$p$$ but $$b$$ is not.
• Nice idea, but could you please detail the computation of the Galois group? It seems to fail for instance when $b$ is a power of $a$ (in this case, of course, we can solve the problem through other means, but perhaps there are other cases where the group isn’t this large)... Commented Oct 31, 2020 at 10:43