A function divisible by $p$

Question

I want to ask about what is the intuition for making functions like these

• $4^n+2$ is divisible by $3$

• $ 2^{4n+2}+3^{n+2}$ is divisible by $13$

And if so, how can I make my own ones? Thank you all for your time.

Answer 1

There is a simple explanation using the binomial theorem: $$ 4^n+2 = (3+1)^n+2 = 3a + 1 + 2 $$ and $$\small 2^{4n+2}+3^{n+2} =4 \cdot 16^n + 9 \cdot 3^n =4 \cdot (13+3)^n + 9 \cdot 3^n =13a + 4 \cdot 3^n + 9 \cdot 3^n =13a + 13 \cdot 3^n $$

Answer 2

These are easy to see with modular arithmetic.

$4^n+2\equiv1^n+2\equiv1+2=3\equiv0\pmod3$ and

$2^{4n+2}+3^{n+2}=4^{2n+1}+3^23^n=4\times4^{2n}+9\times3^n\equiv4\times3^n+9\times3^n=13\times3^n\equiv0\bmod 13.$

Answer 3

"How to make my own ones":

a) Choose your favourite natural number (works best for primes), like $17$.

b) Play with basic congruences in $\mathbb Z/17$, like $33=-1$, $9=1/2$, $5\cdot 7=1$.

c) Write down an obvious formula like $(-1) + 4\cdot 1/2 -1=0$. Make it look more complicated, like $(-1)^{2n+1} + 4\cdot 1/2 -1^n=0$

Insert c in b: $33^{2n+1}+4\cdot3^2 -5^n\cdot 7^n = 3^2(11^{2n+1}\cdot 3^{2n-1}+4)-5^n\cdot7^n$ is divisible by $17$.