Hint

Here is my solution at vmf. Lemma 1. $\text{gcd}(a^{m} - 1, a^{n} - 1) = a^{\text{gcd}(m, n)} - 1$ Proof. Let $d = \text{gcd}(a^{m} - 1, a^{n} - 1)$ Notice that $a^{\text{gcd}(m, n)} - 1 \mid a^{m} - 1, a^{n} - 1 \implies a^{\text{gcd}(m, n)} - 1 \mid d \implies d \ge a^{\text{gcd}(m, n)} - 1$ On other hand, $a^{m} \equiv 1 \pmod{d}$ and $a^{n} \equiv 1\pmod{p}$, therefore, $\text{ord}_{d}(a) \mid m, n \implies \text{ord}_{d}(a) \mid \text{gcd}(m, n)$ Or $a^{\text{gcd}(m, n)} \equiv 1 \pmod{d}$ hay $a^{\text{gcd}(m, n)} - 1 \ge d$. In conclusion, the result follows as desired. Lemma 2. The equation $3^{3^{u}} + 1 = 2^{t}$ has the only integer solution í $(u, t) = (0, 2)$. Proof. Induction shows that $3^{3^{u}} \equiv 3\pmod{8}$. Thus, the only solution is $(u, t) = (0, 2)$ Our problem is equivalent to if $p$ is a prime divisor of $a^{n} - 1$ then $p\mid d$ where $d = \text{gcd}(a^{n} - 1, a^{3^{2016}} - 1)$ Setting $n = 3^{u}.v$ where $\text{gcd}(v, 3) = 1$. Case 1. $u \le 2016$. According to the lemma 1, $d = a^{3^{u}} - 1$ i) If $v = 1$ then $a^{3^{u}} - 1 \mid a^{3^{2016}} - 1$. Our problem is true. ii) Consider $v \ge 2$, we have $a^{v} - 1\mid a^{n} - 1$. Then, the problem can be written as 'If $p\mid a^{v} - 1$ then $p\mid a^{3^{u}} - 1$. Consider $p$ is a prime divisor of $\frac{a^{v} - 1}{a - 1} \implies p\mid a^{v} - 1$. It means $p\mid \text{gcd}(a^{v} - 1, a^{3^{u}} - 1) = a - 1$ according to lemma 1. This means a set of prime divisors of $a^{v - 1} + a^{v - 2} + \cdots + 1$ must be a subset of a set of prime divisors of $a - 1$ (*) Now, let $A = a^{v - 1} + a^{v - 2} + \cdots + 1 = p_{1}^{d_{1}}p_{2}^{d_{2}}\cdots p_{k}^{d_{k}}$ where $p_{i} < p_{i + 1}$ are prime divisors of $A$. From (*), we have $a - 1 = p_{1}^{c_{1}}p_{2}^{c_{2}}\cdots p_{k}^{c_{k}}.P$ (This is the condition to use LTE's lemma) a) If $a$ is even then all of $p_{i}, P$ are odd. Apply LTE's lemma, we get $v_{p_{i}}(A) = v_{p_{i}}(a^{v} - 1) - v_{p_{i}}(a - 1) = v_{p_{i}}(v)$, which means $v = p_{1}^{d_{1}}p_{2}^{d_{2}}\cdots p_{k}^{d_{k}}Q$ Thus, $A \ge a^{v - 1} + 1 = a^{p_{1}^{d_{1}}p_{2}^{d_{2}}\cdots p_{k}^{d_{k}}Q - 1} + 1 \ge 3^{p_{1}^{d_{1}}p_{2}^{d_{2}}\cdots p_{k}^{d_{k}}Q - 1} + 1 > A$. It's a contradition. b) If $a = 4t + 1$. We can also use LTE's lemma where $4\mid a - 1$ implies $v_{2}(a^{v} - 1) = v_{2}(a - 1) + v_{2}(v)$. Similarly to part a), it yields no solutions. c) If $a = 4t + 3$. Note that if $v$ is odd, we get $v_{2}(A) = v_{2}(v) = 0$ then the rest is similar to part a). Consider $v$ is even, according to LTE's lemma $v_{2}(a^{v} - 1) = v_{2}(a - 1) + v_{2}(a + 1) + v_{2}(v) - 1 = v_{2}(a + 1) + v_{2}(v)$. Let $L = v_{2}(v)$, $K = v_{2}(A) = d_{1}$ and $J = v_{2}(a + 1) \; (J \ge 2)$. So we have $K = v_{2}(A) = v_{2}(a^{v} - 1) - v_{2}(a - 1) = L + J - 1$ (Note that $p_{1} = 2$) Thus, $A = 2^{L + J - 1}p_{2}^{d_{2}}\cdots p_{k}^{d_{k}}$ and $v = 2^{L}p_{2}^{d_{2}}\cdots p_{k}^{d_{k}}.Q$. On other hand, note that $v_{2}(a + 1) = J$ so $a + 1 \ge 2^{J} \iff a \ge 2^{J} - 1$. Now: $$A = a^{v - 1} + a^{v - 2} + \cdots + 1 \ge a^{v - 1} + 1 \ge (2^{J} - 1)^{v - 1} + 1 = [(2^{J} - 2) + 1]^{2^{L}p_{2}^{d_{2}}\cdots p_{k}^{d_{k}}Q} + 1 \ge 2^{L}p_{2}^{d_{2}}\cdots p_{k}^{d_{k}}Q(2^{J} - 2) + 2 \ge 2^{L + J}.p_{2}^{d_{2}}\cdots p_{k}^{d_{k}} - 2^{L + 1}p_{2}^{d_{2}}\cdots p_{k}^{d_{k}} + 2 \ge A$$The equality holds iff $v = 2$, $a = 2^{l} - 1$. We need to find $u$ satisfies every prime divisors of $a^{2.3^{u}} - 1$ is also prime divisors of $a^{3^{2016}} - 1$. Consider if $u \neq 0$, according to lemma 2, $a^{3^{u}} + 1$ has an odd prime divisor. Consider $q$ is a odd prime divisor of $a^{3^{u}} + 1$. We have $q\mid \frac{a^{3^{2016}} - 1}{a^{3^{u}} - 1}$. Setting $x = a^{3^{u}}$ and $y = 3^{2016 - u}$ ($y$ is odd) then $q\mid \frac{x^{y} - 1}{x - 1} = x^{y - 1} + x^{y - 2} + \cdots + 1 = x^{y - 2}(x + 1) + x^{y - 4}(x + 1) + \cdots + x(x + 1) + 1$ (From $y$ is odd) implies $q\mid 1$ since $q\mid x + 1$. A contradition. Thus, we implies that $n = 2$ In conclusion, $(a, n) = (2^{l} - 1, 2)$ is solution. Case 2. $n > 2016$ Similar case 1, if $v > 1$ we also have $n = 2$. Contradition. Consider $v = 1$. I claim that there is a prime divisor of $3^{3^{u}} - 1$ but not divide $3^{3^{2016}} - 1$ Assume contrary, it means there is a prime divisor $q$ of $v_{q}(3^{3^{u}}) > v_{q}(3^{3^{2016}})$. If $q$ is odd, since every prime divisor $q$ of $3^{3^{u}} - 1$ and $3^{3^{2016}} - 1$ is difference from $3$ then according to LTE's lemma: $v_{q}(3^{3^{u}} - 1) = v_{q}(3^{3^{2016}} - 1) + v_{q}(3^{u - 2016}) = v_{q}(3^{3^{2016}})$ To prove our problem, we just consider the equation $3^{3^{u}} - 1 = 2^{i}.(3^{3^{2016}} - 1)$, it's contradition since $v_{2}(3^{3^{u}} - 1) = v_{2}(3^{3^{2016}})$ Correct me if i made mistake . Thank you.

quangminhltv99 wrote: Find all $a,n\in\mathbb{Z}^+$ ($a>2$) such that each prime divisor of $a^n-1$ is also prime divisor of $a^{3^{2016}}-1$ Is it so easy or am I missing something ? Obviously $(a,3^{2016})$ is a solution for all $a$. Suppose $n>3^{2016}$. Then by Zsigmondy's Theorem, $a^n-1$ has a prime divisor not dividing $a^{3^{2016}}-1$, a contradiction. Suppose $n<3^{2016}$. Suppose $d=\gcd (n,3^{2016})$. If $n\not| 3^{2016}$, then $d<n$ and shinchiman's lemma together with Zsigmondy yields a contradiction. Then $n\mid 3^{2016}$, which is indeed a solution for all $a$. Note that we have ignored all exceptions of Zsigmondy. Checking those trivial cases separately, it is easy to finish off.

Ankoganit wrote: quangminhltv99 wrote: Find all $a,n\in\mathbb{Z}^+$ ($a>2$) such that each prime divisor of $a^n-1$ is also prime divisor of $a^{3^{2016}}-1$ Is it so easy or am I missing something ? Obviously $(a,3^{2016})$ is a solution for all $a$. Suppose $n>3^{2016}$. Then by Zsigmondy's Theorem, $a^n-1$ has a prime divisor not dividing $a^{3^{2016}}-1$, a contradiction. Suppose $n<3^{2016}$. Suppose $d=\gcd (n,3^{2016})$. If $n\not\mid 3^{2016}$, then $d<n$ and shinchiman's lemma together with Zsigmondy yields a contradiction. Then $n\mid 3^{2016}$, which is indeed a solution for all $a$. Note that we have ignored all exceptions of Zsigmondy. Checking those trivial cases separately, it is easy to finish off. Well yeah, of course it's easy with Zsigmondy.

CantonMathGuy wrote: Ankoganit wrote: quangminhltv99 wrote: Find all $a,n\in\mathbb{Z}^+$ ($a>2$) such that each prime divisor of $a^n-1$ is also prime divisor of $a^{3^{2016}}-1$ Is it so easy or am I missing something ? Obviously $(a,3^{2016})$ is a solution for all $a$. Suppose $n>3^{2016}$. Then by Zsigmondy's Theorem, $a^n-1$ has a prime divisor not dividing $a^{3^{2016}}-1$, a contradiction. What about a=2^k -1, n=3^c .2 , c<2017 Suppose $n<3^{2016}$. Suppose $d=\gcd (n,3^{2016})$. If $n\not\mid 3^{2016}$, then $d<n$ and shinchiman's lemma together with Zsigmondy yields a contradiction. Then $n\mid 3^{2016}$, which is indeed a solution for all $a$. Note that we have ignored all exceptions of Zsigmondy. Checking those trivial cases separately, it is easy to finish off. Well yeah, of course it's easy with Zsigmondy.

What about a=2^c-1 and n=3^k.2 , k<2017