# Proving the Existence of a Number without Constructing

Prove that for all $$k \in \mathbb{N}$$ then there exists $$n$$ such that $$7^k \mid 2^n + 5^n + 3$$

My idea is to construct $$n$$ such that the equation above is valid. However, the construction that I got is $$n = 3 \cdot 7^{k - 1} + 1$$ which is very weird and almost impossible to find without the help of a computer.

Is there a way to prove the existence of $$n$$ without constructing one?

• This seems provable using induction did you try that? Commented Jun 2, 2023 at 13:35
• $n-1=\phi(7^k)/2$, where $\phi$ is Euler's totient function Commented Jun 2, 2023 at 14:12
• Are you familiar with lifting the exponent lemma? Commented Jun 2, 2023 at 14:42
• @wjmccann I am curious how to use induction, can you please answer or give a hint (of course with/without construction)? Commented Jun 3, 2023 at 6:24
• you could prove by induction that $7^k\mid 2^{3\cdot7^{k-1}}-1$ and $7^k\mid5^{3\cdot7^{k-1}}+1$, and from those it follows that $7^k\mid2^{3\cdot7^{k-1}+1}-2+5^{3\cdot7^{k-1}+1}+5=2^n+5^n+3$ Commented Jun 4, 2023 at 15:14

The construction $$n=3\cdot7^{k-1}+1$$ is not so weird or impossible to find.

By Euler's theorem, $$a^{\phi(7^k)}\equiv1\bmod7^k$$ if $$7\nmid a$$, where $$\phi$$ is Euler's totient function,

and $$a^{\phi(7^k)/2}\equiv\pm1\bmod7^k$$, and $$\phi(7^k)=6\cdot7^{k-1}$$.

$$2^{\phi(7^1)/2}=8\equiv1\bmod7$$, and $$5^{\phi(7^1)/2}=125\equiv-1\bmod7$$,

so $$2^{\phi(7^k)/2}\equiv1\bmod7^k$$, and $$5^{\phi(7^k)/2}\equiv-1\bmod7^k$$.

Therefore, $$2^n+5^n+3\equiv 2-5+3=0\bmod7^k$$.

Notice that $$2 - 5 + 3 = 0$$.
So the motivation is to find a $$7^k \mid 2^n - 2, 7^k \mid 5^n + 5$$, or that $$7^k \mid 2^{n-1} - 1, 7^k \mid 5^{n-1} + 1$$.

If you're familiar with the Lifting the Exponent lemma, this is pretty standard.

• Show that $$2^3 \equiv 1 \pmod{7}$$ and $$5^3 \equiv -1 \pmod {7}$$.
• LTE thus gives us $$v_7(2^{3m} - 1^{3m}) = v_7(2^3 - 1) + v_7(3m)$$ and $$v_7 (5^{3m} - (-1)^{3m} ) = v_7(5^3 - (-1)) + v_7 (3m)$$.
• In particular, for $$m = 7^{k-1}$$, $$7^k \mid 2^{3m} - 1$$, $$7^k \mid 5^{3m} + 1$$, which is what we need.
• Thus, $$n = 3\times 7^{k-1} + 1$$ works.

Note

• It follows that any $$n = A \times 3\times 7^{k-1} + 1$$ will work.