Suppose $n$ divides $3^n + 4^n$. Show that $7$ divides $n$. Suppose $n \geq 2$ and $n$ is a divisor of $3^n + 4^n$. Prove that $7$ is a divisor of $n$.
My work so far:
I had a hypothesis that if $n| 3^n + 4^n$, then $n = 7^k$ for some $k\in\mathbb{N}$. But this is not necessarily so. Take $n = 7⋅379$, where $3^7 + 4^7 = 7^2⋅379$. Then, $3^7+4^7$ divides $3^n + 4^n$, and since $n$ divides $3^7+4^7$, we must have $n|3^n+4^n$.

First, we note that $3 \nmid 3^n + 4^n$ and $4 \nmid 3^n + 4^n$. So $3 \nmid n$ and $2 \nmid n$.
Now, reworking $3^n + 4^n \equiv 0 \pmod n$. Since n is odd, we find 
\begin{equation}
3^n \equiv (-4)^n \pmod n.
\end{equation}
Since $\gcd(3, n) = 1$, we can take the inverse of $3 \mod n$, i. e. there exists $3^{-1}$ so that $3 \cdot 3^{-1} \equiv 1 \pmod n$. Multiplying both sides by $(3^{-1})^n$ gives
\begin{equation}
(-4 \cdot 3^{-1})^n \equiv 1 \pmod n.
\end{equation}
Now, if $O_m(k)$ denotes the order of $k \mod m$, we know from algebra that
\begin{equation}
O(-4 \cdot 3^{-1}) \mid n.
\end{equation}
Now, to show that $7 \nmid n$ for any solution, let's assume $7 \nmid n$ for some $n \in \mathbb{N}$. Let's assume $n > 1$ is the smallest solution so that $7 \nmid n$ and $n \mid 3^n + 4^n$.
If we can show that either $n = 1$ or $7 \mid n$ or there exists an $m < n$ satisfying these properties, we're done.
Let's split 2 cases:
(Case 1): $O_n(-4 \cdot 3^{-1}) = 1$ Then we're done, since that implies (using uniqueness of inverses):
\begin{equation}
(-4 \cdot 3^{-1}) \equiv 1 \pmod n \implies -4 \cdot 3^{-1} \equiv 3 \cdot 3^{-1} \pmod n  \\ \implies -4 \equiv 3 \pmod n \implies n \mid 7 \implies n = 1 \vee n = 7.
\end{equation}
(Case 2): $O_n(-4 \cdot 3^{-1}) > 1$. Let $d = O_n(-4 \cdot 3^{-1})$.
Then $(-4 \cdot 3^{-1})^d \equiv 1 \pmod n$, and since $d \mid n$ we have $(-4 \cdot 3^{-1})^d \equiv 1 \pmod d$. $d$ is also odd, and
\begin{equation}
-4^d (3^{-1})^d \equiv 1 \pmod d \implies -4^d \equiv 3^d \pmod d
\end{equation}
If $O_d(-4 \cdot 3^{-1}) = 1$, then by the reasoning above $d \mid 7$. Since $d > 1$, we have $d = 7$. Since $d \mid n$, $7 \mid n$.
If $O_d(-4 \cdot 3^{-1}) > 1$, let m = $O_d(-4 \cdot 3^{-1})$. Then $m > 1$, $7 \nmid m$ and $m \mid 3^m + 4^m$. $m < n$, since $m \mid \varphi(n)$. So we found an $m < n$ satisfying the above conditions, implying $n$ is not the smallest.
