Proving the Existence of a Number without Constructing

Question

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?

Answer 1

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

Answer 2

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.