Investigate if there exist infinitely many natural numbers $n$ such that $n$ divides $2^n+3^n$.
Problem
Source: Mongolia 1999 Grade 9 P4
Tags: number theory, Divisibility
05.05.2021 11:28
We will show that $5^m\mid 2^{5^m}+3^{5^m}$ for all non-negative integers $m$ by induction. The base case is obvious ( $1\mid 5 \Rightarrow 5^0\mid 2^{5^0}+3^{5^0}$). For the induction step, let $5^k\mid 2^{5^k}+3^{5^k}$ for some non-negative integer $k$. Let $2^{5^k}=x$ and $3^{5^k}=y$. We want to show that $5^{k+1}\mid x^5+y^5$ $x^5+y^5=(x+y)(x^4-x^3y+x^2y^2-xy^3+y^4)$ From $5^k\mid x+y$, it is enough to show that $5\mid x^4-x^3y+x^2y^2-xy^3+y^4$. From $5\mid x+y \Rightarrow y\equiv -x\pmod{5}$. $x^4-x^3y+x^2y^2-xy^3+y^4\equiv x^4-x^3(-x)+x^2(-x)^2-x(-x)^3+(-x)^4\equiv 5x^4\equiv 0 \pmod{5}$. Therefore, $5^{k+1}\mid 2^{5^{k+1}}+3^{5^{k+1}}$. $\Rightarrow 5^m\mid 2^{5^m}+3^{5^m}$ for all non-negative integers $m$. So, there exist infinitely many natural numbers $n$ such that $n\mid 2^n+3^n$. $\Box$
05.05.2021 13:39
Ok I will post a pretty simple solution. We will show that all powers of $5$ work. Indeed by LTE for any $k \geqslant 1$ $$v_5(2^{5^k} + 3^{5^k}) = 1 + k $$which means that $5^k \mid 2^{5^k} + 3^{5^k}$ and so we're done. @above you are doing LTE only but you are deriving it