Show that $3^{7^n}+5^{7^n}\equiv 1 \pmod{7^{n+1}}$

Question

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

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

Answer 2

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

Answer 3

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

Answer 4

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.

Answer 5

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.