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

We will need the following useful result: If $$x\equiv1\pmod{7^k}$$ then $$x^7\equiv1\pmod{7^{k+1}}$$. To see why this is true, write $$x$$ as $$x=1+7^km$$ and apply the binomial theorem.

Now suppose that $$3^{7^k}+5^{7^k}\equiv1\pmod{7^{k+1}}$$. By the useful result, $$\left(3^{7^k}+5^{7^k}\right)^7\equiv1\pmod{7^{k+2}}.$$ Then \begin{align*} 3^{7^{k+1}}&+7\cdot3^{6\cdot7^k}5^{7^k}+21\cdot3^{5\cdot7^k}5^{2\cdot7^k}+35\cdot3^{4\cdot7^k}5^{3\cdot7^k}\\&+35\cdot3^{3\cdot7^k}5^{4\cdot7^k}+21\cdot3^{2\cdot7^k}5^{5\cdot7^k}+7\cdot3^{7^k}5^{6\cdot7^k}+5^{7^{k+1}}\equiv1\pmod{7^{k+2}}. \end{align*} We want to show that $$3^{7^{k+1}}+5^{7^{k+1}}\equiv1\pmod{7^{k+2}}$$. Then it suffices to show that \begin{align*} 7\cdot3^{6\cdot7^k}5^{7^k}&+21\cdot3^{5\cdot7^k}5^{2\cdot7^k}+35\cdot3^{4\cdot7^k}5^{3\cdot7^k}\\&+35\cdot3^{3\cdot7^k}5^{4\cdot7^k}+21\cdot3^{2\cdot7^k}5^{5\cdot7^k}+7\cdot3^{7^k}5^{6\cdot7^k}\equiv0\pmod{7^{k+2}}. \end{align*} By dividing through by $$7$$, it suffices to show that $$3^{6\cdot7^k}5^{7^k}+3\cdot3^{5\cdot7^k}5^{2\cdot7^k}+5\cdot3^{4\cdot7^k}5^{3\cdot7^k}+5\cdot3^{3\cdot7^k}5^{4\cdot7^k}+3\cdot3^{2\cdot7^k}5^{5\cdot7^k}+3^{7^k}5^{6\cdot7^k}\equiv0\pmod{7^{k+1}}.$$ Now $$3\cdot5\equiv1\pmod7$$ so inductively applying the useful result shows that $$3^{7^k}5^{7^k}\equiv1\pmod{7^{k+1}}$$. Then it suffices to show that $$3^{5\cdot7^k}+3\cdot3^{3\cdot7^k}+5\cdot3^{7^k}+5\cdot5^{7^k}+3\cdot5^{3\cdot7^k}+5^{5\cdot7^k}\equiv0\pmod{7^{k+1}}.$$ Finally, $$3^{7^k}+5^{7^k}\equiv1\pmod{7^{k+1}}$$ so it suffices to show that $$3^{5\cdot7^k}+3\cdot3^{3\cdot7^k}+3\cdot5^{3\cdot7^k}+5^{5\cdot7^k}\equiv-5\pmod{7^{k+1}}.\qquad\qquad(1)$$

Taking fifth powers of the congruence $$3^{7^k}+5^{7^k}\equiv1\pmod{7^{k+1}}$$ shows that $$3^{5\cdot7^k}+5\cdot3^{4\cdot7^k}5^{7^k}+10\cdot3^{3\cdot7^k}5^{2\cdot7^k}+10\cdot3^{2\cdot7^k}5^{3\cdot7^k}+5\cdot3^{7^k}5^{4\cdot7^k}+5^{5\cdot7^k}\equiv1\pmod{7^{k+1}}.$$ Again, $$3^{7^k}5^{7^k}\equiv1\pmod{7^{k+1}}$$ so $$3^{5\cdot7^k}+5\cdot3^{3\cdot7^k}+10\cdot3^{7^k}+10\cdot5^{7^k}+5\cdot5^{3\cdot7^k}+5^{5\cdot7^k}\equiv1\pmod{7^{k+1}}.$$ Again, $$3^{7^k}+5^{7^k}\equiv1\pmod{7^{k+1}}$$ so $$3^{5\cdot7^k}+5\cdot3^{3\cdot7^k}+5\cdot5^{3\cdot7^k}+5^{5\cdot7^k}\equiv-9\pmod{7^{k+1}}.\qquad\qquad(2)$$

Taking third powers of the congruence $$3^{7^k}+5^{7^k}\equiv1\pmod{7^{k+1}}$$ shows that $$3^{3\cdot7^k}+3\cdot3^{2\cdot7^k}5^{7^k}+3\cdot3^{7^k}5^{2\cdot7^k}+5^{3\cdot7^k}\equiv1\pmod{7^{k+1}}.$$ Again, $$3^{7^k}5^{7^k}\equiv1\pmod{7^{k+1}}$$ so $$3^{3\cdot7^k}+3\cdot3^{7^k}+3\cdot5^{7^k}+5^{3\cdot7^k}\equiv1\pmod{7^{k+1}}.$$ Again, $$3^{7^k}+5^{7^k}\equiv1\pmod{7^{k+1}}$$ so $$3^{3\cdot7^k}+5^{3\cdot7^k}\equiv-2\pmod{7^{k+1}}.$$ Multiplying through by $$-2$$ shows that $$-2\cdot3^{3\cdot7^k}-2\cdot5^{3\cdot7^k}\equiv4\pmod{7^{k+1}}.\qquad\qquad(3)$$

Adding Equations (2) and (3) gives Equation (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$$.

• the first statement is correct Jul 2, 2019 at 19:24
• I have added a proof of the lemma. Jul 3, 2019 at 2:43

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

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.

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.

• In the last step, how do you know that $\left(3^{7^n} + 5^{7^n}\right)^7 \equiv 3^{7^{n+1}} + 5^{7^{n+1}} \pmod {7^{n+2}}$? Working modulo $7^{n+2}$, we are not in a field of characteristic $7$ anymore so Frobenius does not apply in general. Something specific must be used about $3$ and $5$ that makes it work. Jul 4, 2019 at 23:59