Suppose $n$ is a natural number such that $4^n + 2^n + 1$ is a prime. Prove that $n = 3^k$ for some nonnegative integer $k$.
Problem
Source: Indian Postal Coaching 2007 set 3 p3
Tags: power of 3, number theory, prime
somebodyyouusedtoknow
28.06.2021 20:09
Notice for $k = 0$, $4^1 + 2^1 + 1^1 = 7$ which is prime. Now, suppose $n$ is not a multiple of 3, then $4^{3p + 2} + 2^{3p + 2} + 1$ will be composite since $4^{3p + 2} + 2^{3p + 2} + 1 \equiv 2 + 4 + 1 \textrm{(mod 7)}$, and $4^{3p + 1} + 2^{3p + 1} + 1$ will be composite since $4^{3p + 1} + 2^{3p + 1} + 1 \equiv 4 + 2 + 1 \textrm{(mod 7)}$. Hence $n$ is a multiple of 3.
Generally, we use the following trick:
Lemma. If $3 \not \vert n$ then $a^2 + a + 1 \vert a^{2n} + a^n + 1$.
Proof. We'll split into 2 cases, i.e. $n = 3q + 1$ and $n = 3q + 2$.
Case 1. $n = 3q + 1$ then $a^2 + a + 1 \vert a^{2n} - a^2 + a^n - a$ by the Division Algorithm. Notice that:
a) $a^{6q + 2} - a^2 = a^2(a^{6q} - 1) = a^2(a^{3q} - 1)(a^{3q + 1}) = a^2(a^3 - 1)(a^{3(q-1)} + a^{3(q - 2)} + \cdots + a^3 + 1)(a^{3q} + 1)$ which is obviously true since $a^2 + a + 1 \vert a^3 - 1$.
b) $a^{3q + 1} - a = a(a^{3q} - 1) = a(a^3 - 1)(a^{3(q - 1)} + \cdots + a^3 + 1)$ which is again, true, by the same reason as above.
Case 2. $n = 3q + 2$ then $a^2 + a + 1 \vert a^{2n} - a + a^n - a^2$ by the Division Algorithm. Notice that:
a) $a^{6q + 4} - a = a(a^{6q+3} - 1) = a(a^{3(2q + 1)} - 1) = a(a^3 - 1)(a^{3(2q)} + a^{3(2q - 1)} + \cdots + a^3 + 1)$
b) $a^{3q + 2} - a^2 = a^2(a^{3q} - 1) = a^2(a^{3(q-1)} + a^{3(q-2)} + \cdots + a^3 + 1)$ which are obviously true for the same reason.
Thus if $n$ is not a power of three, we can take $n = 3^t \cdot q$ where $q$ is relatively prime to 3, and then substitute $a = 3^t$ on our lemma to get that it can't be prime, as desired.
peace09
29.06.2021 19:16
Original Claim: If $n$ is a natural number such that $4^n + 2^n + 1$ is prime, then $n = 3^k$ for some nonnegative integer $k.$ Follow - Up Claim: If $n$ is a natural $n^4 + n^2 + 1$ is prime, then $n=1.$ Can you prove it?
jasperE3
29.06.2021 20:10
$n^4+n^2+1=(n^2-n+1)(n^2+n+1)$
peace09
29.06.2021 20:12
jasperE3 wrote: $n^4+n^2+1=(n^2-n+1)(n^2+n+1)$ Yup; then $n^2-n+1$ or $n^2+n+1$ is equal to 1, which yields $n=1$ as the only solution.