Saudi Arabian IMO Booklet

Let $d=3^{n-1}+5^{n-1}$. We want $d\mid 3^n+5^n$.

Note that: $$3^n+5^n=3\cdot 3^{n-1}+5\cdot 5^{n-1}=3d-2\cdot 3^{n-1}+5d-4\cdot 5^{n-1}=(3+5)d-2\cdot 3^{n-1}-4\cdot 5^{n-1}=8d-(2\cdot 3^{n-1}+4\cdot 5^{n-1})$$

So $d\mid 3^n+5^n$ if and only if $d\mid 2\cdot 3^{n-1}+4\cdot 5^{n-1}$.

But $d=3^{n-1}+5^{n-1}$, so $d\mid 2\cdot 3^{n-1}+4\cdot 5^{n-1}$.

Let us check small values of $n$:

For $n=1$: $d=3^0+5^0=1+1=2$ $3^1+5^1=3+5=8$ $2\mid 8$ is true.

For $n=2$: $d=3^1+5^1=3+5=8$ $3^2+5^2=9+25=34$ $8\mid 34$? $34/8=4.25$, so no.

For $n=3$: $d=3^2+5^2=9+25=34$ $3^3+5^3=27+125=152$ $34\mid 152$? $152/34=\mathrm{4.470...}$, so no.

For $n=4$: $d=3^3+5^3=27+125=152$ $3^4+5^4=81+625=706$ $152\mid 706$? $706/152\approx 4.64$, so no.

It seems only $n=1$ works.

Let us prove that $n=1$ is the only solution.

Suppose $n>1$. Let $d=3^{n-1}+5^{n-1}$. We want $d\mid 3^n+5^n=3\cdot 3^{n-1}+5\cdot 5^{n-1}$. So $d\mid 3\cdot 3^{n-1}+5\cdot 5^{n-1}$. But $d=3^{n-1}+5^{n-1}$, so $d\mid 3\cdot 3^{n-1}+5\cdot 5^{n-1}-k(3^{n-1}+5^{n-1})$ for any integer $k$.

Let $k=3$: $3\cdot 3^{n-1}+5\cdot 5^{n-1}-3(3^{n-1}+5^{n-1})=3\cdot 3^{n-1}+5\cdot 5^{n-1}-3\cdot 3^{n-1}-3\cdot 5^{n-1}=(5-3)\cdot 5^{n-1}=2\cdot 5^{n-1}$ So $d\mid 2\cdot 5^{n-1}$.

Similarly, let $k=5$: $3\cdot 3^{n-1}+5\cdot 5^{n-1}-5(3^{n-1}+5^{n-1})=3\cdot 3^{n-1}+5\cdot 5^{n-1}-5\cdot 3^{n-1}-5\cdot 5^{n-1}=(3-5)\cdot 3^{n-1}=-2\cdot 3^{n-1}$ So $d\mid 2\cdot 3^{n-1}$.

Therefore, $d\mid \gcd (2\cdot 3^{n-1},2\cdot 5^{n-1})=2$ (since $3^{n-1}$ and $5^{n-1}$ are coprime).

But $d=3^{n-1}+5^{n-1}\ge 3^{n-1}+1>2$ for $n>1$.

Therefore, the only solution is $n=1$.

Answer: $n=1$.