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$.
 A: Lemma: Suppose $n \geq 0$. Then ${7^n\choose k}7^k$ is divisible by $7^{n+1}$ for all $1 \leq k \leq 7^n$.
Proof: Legendre's formula says that the largest power of $7$ dividing $m!$ is $\sum\limits_{i=0}^\infty\left\lfloor\frac{m}{7^i}\right\rfloor$ (this is really a finite sum). Now use the formula ${m\choose k} = \frac{m!}{k!(m-k)!}$ to conclude that the largest power of $7$ dividing ${m\choose k}$ is $\sum\limits_{i=0}^\infty\left(\left\lfloor\frac{m}{7^i}\right\rfloor - \left\lfloor\frac{k}{7^i}\right\rfloor - \left\lfloor\frac{m - k}{7^i}\right\rfloor\right)$.
When $m = 7^n$, this is $\sum\limits_{i=0}^n\left(\left\lfloor\frac{7^n}{7^i}\right\rfloor - \left\lfloor\frac{k}{7^i}\right\rfloor - \left\lfloor\frac{7^n - k}{7^i}\right\rfloor\right) = \sum\limits_{i=0}^n\left(7^{n-i} - \left\lfloor\frac{k}{7^i}\right\rfloor - \left\lfloor7^{n-i}-\frac{k}{7^i}\right\rfloor\right) = \sum\limits_{i=0}^n\left(-\left\lfloor\frac{k}{7^i}\right\rfloor-\left\lfloor-\frac{k}{7^i}\right\rfloor\right)$
This equals $\sum\limits_{i=v_7(k)+1}^{n} 1 = n - v_7(k)$, where $v_7(k)$ is the largest power of $7$ dividing $k$. I used the result that $-\lfloor x\rfloor - \lfloor -x\rfloor = 0$ if $x$ is an integer and $1$ otherwise (in our case, $\frac{k}{7^i}$ is an integer iff $i \leq v_7(k)$).
So the largest power of $7$ dividing ${7^n\choose k}7^k$ is $n + k - v_7(k) \geq n + k - \log_7(k) \geq n + 1$ when $k \geq 1$.

Proof of main result
Now use the binomial theorem and the preceding lemma to find $5^{7^n} \equiv (7-2)^{7^n} \equiv \sum\limits_{k=0}^{7^n}{7^n\choose k}7^k(-2)^{7^n-k} \equiv (-2)^{7^n} \equiv -2^{7^n} \pmod{7^{n+1}}$.
Similarly, $3^{7^n} \equiv (7 - 4)^{7^n} \equiv \sum\limits_{k=0}^{7^n}{7^n\choose k}7^k(-4)^{7^n-k} \equiv (-4)^{7^n} = -2^{2\cdot 7^n} \pmod {7^{n+1}}$.
Then $3^{7^n} + 5^{7^n} \equiv -2^{2\cdot 7^n} - 2^{7^n}\pmod{7^{n+1}}$.
Now let $x = 2^{7^n}$. Since $2^3 = 8 = 7 + 1$, we have $x^3 \equiv (7+1)^{7^n} \equiv 1 \pmod{7^{n+1}}$, by another use of the binomial theorem and the lemma.
From here it follows that $(x-1)(x^2+x+1) \equiv 0 \pmod{7^{n+1}}$.
Note that $3^{7^n} + 5^{7^n} \equiv -x^2-x \pmod {7^{n+1}}$.
So if $x \not\equiv 1 \pmod 7$ (we do not use $7^{n+1}$ here, this needs to be prime) then it follows that $x^2 + x + 1 \equiv 0 \pmod{7^{n+1}}$, which means $3^{7^n} + 5^{7^n} \equiv 1 \pmod{7^{n+1}}$.
We check that $2^{7^n} \not\equiv 1 \pmod{7}$. But the order of $2$ modulo $7$ is $3$, and $7^n$ is not a multiple of $3$.
A: 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)$.
A: Quick solution using Lifting the Exponent Lemma:
Note that $3^{7^n} + 5^{7^n} - 1 \equiv -4^{7^n} - 2^{7^n} - 1 \equiv -(4^{7^n} + 2^{7^n} + 1) \equiv -\dfrac{8^n-1}{2^n-1} \pmod{7^{n+1}}$.
Now, by LTE, we have $\nu_7(8^{7^n} - 1) = \nu_7(8-1) + \nu_7(7^n) = n+1$, and $2^{7^n} \equiv 2^{7^n \pmod{6}} \equiv 2^{1^n} \equiv 2 \pmod{7}$, so $7 \nmid 2^{7^n} - 1$. Thus, we have
$$\frac{8^{7^n}-1}{2^{7^n} - 1} \equiv 0 \pmod{7^{n+1}}$$
so we're done.
A: It is known that 
$$(a+b)^7=a^7+b^7+7(a^6b+ab^6)+21(a^5b^2+a^2b^5)+35(a^4b^3+a^3b^4)$$ and $(A+B)^7= {A^7+B^7}$ in fields of characteristic $7$. We apply induction.
►$3^{7^1}+5^{7^1}=80312=1639\times7^2+1\iff3^{7^1}+5^{7^1}\equiv1\pmod{7^2}$
►$3^{7^n}+5^{7^n}\equiv1\pmod{7^{n+1}}\iff3^{7^n}+5^{7^n}=7^{n+1}m+1$ assumed to be true.
►$(7^{n+1}m+1)^7=7^{7(n+1)}m^7+7(7^{6(n+1)}m^6+7^{n+1}m)+21(7^{5(n+1)}m^5+7^{2(n+1)}m^2)+35(7^{4(n+1)}m^4+7^{3(n+1)}m^3)+1=1+7^{n+2}\color{red}{[}7^{6n+5}b^7+(7^{5n+6}m^6+\color{red} m)+21(7^{4n+3}m^5+7^nm^2)+35(7^{3n+2}m^4+7^{2n+1}m^3)\color{red}]$
Then $(3^{7^n}+5^{7^n})^7=(7^{n+1}m+1)^7\equiv1\pmod{7^{n+2}}$
But $(3^{7^n}+5^{7^n})^7\equiv{3^{7^{n+1}}+5^{7^{n+1}}}\equiv1\pmod{7^{n+2}}$
We are done.
