SpecialSequence EulerFermatTheorem Difficult

Problem - 4269
Let sequence $\{a_n\}$ be $a_n=2^n + 3^n + 6^n - 1$ where $n\ge 1$. Find the sum of all positive integers which are co-prime to all the $a_n$.

Clearly, $(1, a_n)=1$ holds for every $n$. We are going to show that $1$ is the only positive integer satisfying this requirement. If so, the answer is $\boxed{1}$.

Let $m > 1$ be a positive integer which is co-prime to all $a_n$ and $p$ be a prime divisor of $m$.

First, because $a_2=48$, $p$ can be neither $2$ nor $3$. Otherwise, we will have $(m, a_2)\ne 1$.

If $p > 3$, by Fermat's little theorem, we have $2^{p-1}\equiv 1\pmod{p}$, $3^{p-1}\equiv 1\pmod{6}$, and $6^{p-1}\equiv 1\pmod{p}$.. Then $$a_{p-2}=2^{p-2}+3^{p-2}+6^{p-2}-1\equiv \frac{1}{2}+\frac{1}{3}+\frac{1}{6}-1\equiv 0\pmod{p}$$

This means $p$ divides both $m$ and $a_{p-2}$, i.e. $(m, a_{p-2}) > 1$.

Hence, we conclude $1$ is the only positive integer that is co-prime to all $a_n$.

report an error