Show that $3^{7^n}+5^{7^n}\equiv 1 \pmod{7^{n+1}}$ Show that $3^{7^n}+5^{7^n}\equiv 1 \pmod{7^{n+1}}$
I tried to induct on n:
For $n = 0$ we have $3+5 = 8$ and $8 \equiv 1 \pmod{7^{n+1}}$.
Suppose it is true for $n = k$: 
$$3^{7^k}+5^{7^k}\equiv 1 \pmod{7^{k+1}}$$
so $3^{7^k}+5^{7^k}=7^{k+1}*q_1+1$
For $n = k+1$:
$$3^{7^{k+1}}+5^{7^{k+1}}\equiv r \pmod{7^{k+2}}$$
so $3^{7^{k+1}}+5^{7^{k+1}}=7^{k+2}*q_2+r$
Now if we subtract them we get that:
$$3^{7^{k+1}}+5^{7^{k+1}}-3^{7^k}-5^{7^k}=7^{k+1}(7q_2-q1)+r-1$$
From Euler's theorem we know that $a^{\phi(7^{k+1})}\equiv 1 \pmod{7^{k+1}}$ 
and $\phi(7^{k+1}) = 6\cdot7^{k}$ so $3^{6\cdot7^{k}}\equiv 1 \pmod{7^{k+1}}$ and $5^{6 \cdot 7^{k}}\equiv 1 \pmod{7^{k+1}}$.
So $3^{7^{k+1}}+5^{7^{k+1}}-3^{7^k}-5^{7^k}\equiv3^{7^k}\cdot3^{6\cdot{7^{k}}}+5^{7^k}\cdot5^{6\cdot{7^{k}}}-3^{7^k}-5^{7^k}\equiv 0 \pmod{7^{k+1}}$
Finally I get that $r\equiv1\pmod{7^{k+1}}$.
Here I got stuck. I don't know how to show that $r=1$.

In this answer I will try to consider generalizations, and organize things better. My first answer was a proof discovered by ad-hoc methods.
Lemma
If $x \equiv y \pmod p$, then $x^{p^n} \equiv y^{p^n} \pmod {p^{n+1}}$ for all $n \geq 0$.
Proof
The case $n = 0$ is trivial. We now prove that if $x \equiv y \pmod {p^k}$ for some $k \geq 1$, then $x^p \equiv y^p \pmod {p^{k+1}}$. This follows from writing $x = m p^k + y$ and using the binomial theorem: $$x^p \equiv (m p^k + y)^p \equiv \sum\limits_{i = 0}^p {p \choose i} p^{ik} m^i y^{p - i} \equiv y^p \pmod {p^{k+1}}$$ because all terms with $i \geq 1$ are divisible by $p^{k+1}$.
I used the fact that ${p \choose i}$ is divisible by $p$ for $1 \leq i \leq p - 1$, and the fact that $kp \geq k + 1$ when $k \geq 1$ for the case $i = p$.
The result follows by induction on $n$.

Proposition
Suppose that $p \equiv 1 \pmod 6$ is a prime. Suppose $a$ and $b$ are the two distinct elements of order $6$ modulo $p$. Then for all $n \geq 0$, we have $(a + b)^{p^n} \equiv a^{p^n} + b^{p^n} \equiv 1 \pmod {p^{n+1}}$.
Note
The elements of order $6$ modulo $p$ must be roots of the $6$-th cyclotomic polynomial $X^2 - X + 1$, which has degree $\varphi(6) = 2$, so there are at most $2$ of them. If $p$ does not divide $6$, it has no multiple root, so the roots are distinct. The roots exist if and only if $p$ is odd and $-3$ is a square $\pmod p$, which means $p \equiv 1 \pmod 6$ by quadratic reciprocity.
The original question is a special case where $p = 7$. You can check that $3$ and $5$ are in fact the elements of order $6$ modulo $7$. One simple way to see this is to note that $3+5 \equiv 8 \equiv 1 \pmod 7$ and $3\cdot 5 \equiv 15 \equiv 1 \pmod 7$, so Vieta's formulas imply that they are roots of $X^2 - X + 1$.
Proof
We know that $a^6 \equiv b^6 \equiv 1 \pmod p$. Using the lemma, we see that $\left(a^{p^n}\right)^6 \equiv \left(b^{p^n}\right)^6 \equiv 1 \pmod {p^{n+1}}$.
It follows that $a^{p^n}$ and $b^{p^n}$ are roots of the equation $X^6 - 1 \equiv (X^3 - 1)(X+1)(X^2-X+1) \equiv 0 \pmod {p^{n+1}}$.
We know that $a^{p^n}$ and $b^{p^n}$ cannot be roots of the first two factors modulo $p$, because that would imply that the order of $a$ and $b$ modulo $p$ is not $6$ (here we use the fact that $p$ does not divide $6$, so the order of $a^{p^n}$ modulo $p$ is the same as the order of $a$ modulo $p$).
Since none of the other factors are divisible by $p$, we must have that $a^{p^n}$ and $b^{p^n}$ are roots of $X^2 - X + 1 \equiv 0 \pmod {p^{n+1}}$.
Note that both $a$ and $a^{-1}$ have order $6$ modulo $p$ (and are distinct), so in fact $b \equiv a^{-1} \pmod p$. That means $ab \equiv 1 \pmod p$, and the lemma implies that $a^{p^n}b^{p^n} \equiv (ab)^{p^n} \equiv 1 \pmod {p^{n+1}}$.
This means $a^{p^n}$ and $b^{p^n}$ are inverses modulo $p^{n+1}$.
If $a^{p^n} + b^{p^n} \equiv s \pmod {p^{n+1}}$, then $a^{p^n}$ and $b^{p^n}$ are roots of $\left(X - a^{p^n}\right)\left(X - b^{p^n}\right) = X^2 - sX + 1$. Since they are also roots of $X^2 - X + 1$, they are roots of the difference, $(s - 1)X = 0$. So $(s - 1)a^{p^n} \equiv 0 \pmod {p^{n+1}}$. But $a^{p^n}$ is invertible modulo $p^{n+1}$, so we conclude $s \equiv 1 \pmod {p^{n+1}}$.
Finally we see that $a^{p^n} + b^{p^n} \equiv 1 \pmod {p^{n+1}}$.

Another generalization
Let $p$ be a prime and $r$ a positive integer not divisible by $p$. Suppose there are $m = \varphi(r)$ distinct elements $a_1, \ldots, a_m$ of order $r$ modulo $p$. Then for all $n \geq 0$, we have $a_1^{p^n} + \cdots + a_m^{p^n} \equiv c \pmod {p^{n+1}}$, where $c$ is the negative of the coefficient of $X^{m-1}$ in the $r$-th cyclotomic polynomial $\Phi_r(X)$.
Note
Since $a_1, \ldots, a_m$ are roots of $\Phi_r(X)$ modulo $p$, their sum is $a_1 + \cdots + a_m \equiv c \pmod p$. The lemma then implies that $(a_1 + \cdots + a_m)^{p^n} \equiv c^{p^n} \pmod {p^{n+1}}$. So the theorem shows that whenever $c^{p^n} \equiv  c \pmod {p^{n+1}}$, we have $(a_1 + \cdots + a_m)^{p^n} \equiv a_1^{p^n} + \cdots + a_m^{p^n} \equiv c \pmod {p^{n+1}}$.
Proof
The lemma essentially allows lifting the roots of the $r$-th cyclotomic polynomial modulo $p$ to roots of the $r$-th cyclotomic polynomial modulo $p^{n+1}$. This comes from the fact that all roots of $\Phi_r(X) \pmod p$ have order $r$ modulo $p$, and raising to the $p^n$-th power preserves the order modulo $p$. So all $a_i^{p^n}$ have order $r$ modulo $p$, and are also roots of $X^r - 1$ modulo $p^{n+1}$ (by the lemma!). If they were not roots of $\Phi_r(X)$ modulo $p^{n+1}$, then they would be roots (modulo $p$) of a cyclotomic polynomial of smaller order dividing $r$, and so their order modulo $p$ would not be $r$.
So the $a_i^{p^n}$ are common roots modulo $p^{n+1}$ of the polynomials $\left(X - a_1^{p^n}\right)\cdots\left(X - a_m^{p^n}\right)$ and $\Phi_r(X)$ which both have degree $m$. They are also distinct, because if $a_i^{p^n} \equiv a_j^{p^n} \pmod {p^{n+1}}$ then this is also true modulo $p$, and then Fermat's little theorem implies $a_i \equiv a_j \pmod p$ so $i = j$.
We can use Euclidean division of $\Phi_r(X)$ by each $X - a_i^{p^n}$ (we work over $\mathbb{Z}/p^{n+1}\mathbb{Z}$, which is not a field, but since each factor is monic, the procedure still works). At each step, the degree of $\Phi_r(X)$ is reduced by $1$, and each remainder term is a constant which must be zero since the $a_i^{p^n}$ are roots. Since we repeat the step as many times as $m$, at the end there is nothing left. Therefore $\left(X - a_1^{p^n}\right)\cdots\left(X - a_m^{p^n}\right) \equiv \Phi_r(X) \pmod {p^{n+1}}$.
If follows from Vietas formulas that the sum $a_1^{p^n} + \cdots + a_m^{p^n}$ is the negative of the coefficient of $X^{m-1}$ in $\Phi_r(X)$.
