https://artofproblemsolving.com/community/q2h1498365p8825819

Goodgood

Let's prove that $m=7^{n - 1}$ satisfies the given condition. We have to prove $-1- 3^{m}-5^{m} \equiv 0 \pmod {7^{n}}$, firstly, we claim that $-3^{m} \equiv 4^{m} \pmod {7^{n}}$ and $-5^{m} \equiv 2^{m} \pmod {7^{n}}$. It's equivalent to proving $7^{n}$ divides $2^{m}+5^{m}, 3^{m}+4^{m}$. Since $m$ is odd, using Lifting The Exponent we have $\nu_7(2^{m} + 5^{m}) = \nu_7(m) +\nu_7(2 + 5) = n$ so $7^{n}$ divides $2^{m} + 5^{m}$. Similarly we can prove that $7^{n}$ divides $3^{m} + 4 ^ {m}$. Now it's left to show that we indeed have $1 + 2^{m} + 4^{m} \equiv 0 \pmod {7^{n}}$. Since $1 + 2^{m} + 4 ^{m} = \dfrac{2 ^ {3m} - 1}{2^{m} - 1}$, it's enough to prove that $7^{n}$ divides $2^{3m} - 1$ and $7$ doesn't divide $2^{m} - 1$. Since order of $2$ mod $7$ is $3$ and $3$ doesn't divide $m=7^{n-1}$, latter is obvious. Using Lifting The Exponent again, we have $\nu_7(2^{3m} - 1) = \nu_7(2^{3} -1) + \nu_7(m) = n$. PS

Ignore...

Sketch of solution: We show this by induction on $n$. The base case is trivial. Suppose we have that for $n$ this is true. Now, let $m$ be the number for which this is true for $n$, and suppose the remainder of $m$ modulo $7^{n-1}.6=\phi(7^n)$ is $c$. Then we write $m=c+7^{n-1}.6.k$, and notice that modulo $\phi(7^{n+1})$, this assumes 7 values. Now we want to show that one of those values satisfy the induction hypothesis. To show this, we change the induction to another one that will implicate the first induction obviously: For some fixed residue of $m$ modulo $\phi(7^{n-1})$, the sums $3^m+5^m$ are different modulo $7^n$ and one of those is one. Notice that because of the fixed residue, those sums achieve at maximum (actually exactly, which we will prove later) 7 distinct residues. We now proceed by induction. Suppose this is false for $n+1$, and it is true for $n$. Letting $$m=c+7^{n-1}.6.k$$be the residue that generated 1 before, vary $k=1,2...,7$. Notice now that $x^{7^{n-1}.6}=y$ is a 7th root of unity of $y^7 - 1$, and the sets of numbers that are those roots of units are $1,w,w^2,...,w^6$. Also notice that if a number $w$ is a 7th "root of unity" modulo $7^n$, then by LTE $w^7$ is the root of unity modulo $7^{n+1}$, and this set is $1,w^7,...,w^{42}$. Back to the problem, suppose we have $3^m+5^m\equiv 3^n+5^n (mod 7^{n+1})$, with $m,n$ being both numbers that generated residue 1 modulo $7^n$, that is, both of them have the same residue $c$ mentioned before. Substituting $m=c+6.7^{n-1}.k,n=c+6.7^{n-1}.j$, and $3^{7^{n-1}.6}$ by $w^7$, and $5^{7^{n-1}.6}$ by $w^{7b}$ where $w$ is a root of unity modulo $7^n$; we get that after some manipulations: $$3^c(w^{7j}-w^{7k})\equiv 5^c(w^{7bk}-w^{7bj}) (mod 7^{n+1})$$Which after expanding $x^7-y^7$ and noticing that the ugly therms cut out because both of their exponents are complete residues mod 7, we would have that $3^c(w^j - w^k)\equiv 5^c(w^bk-w^bj)$, but this is true mod $7^{n+1}$, which implies it is true mod $7^n$, which is a contradiction by the induction hypothesis on the sums being disjoint. Now, notice that as we supposed there was a sum generating residue 1 mod $7^n$, then notice the new residues will be $7^n.1+1,7^n.2+1,...,7^n.7+1$, and as all the sums are disjoint, all those 7 values (including the last one) will be generated, concluding the induction hypothesis. Nice one, the main step was recognising the root of unity from $7^n$ to $7^{n+1}$.