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$.

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$.
