I'll try to format my question in a manner such that you can skip (irrelevant) parts.


Find all natural $n$ such that $3^{2n+1}-4^{n+1}+6^n$ is prime.


I'm trying to prepare talented elementary school children for mathematics competition and the question from the title popped up somewhere as suggested for the purpose (explicitly stating this should be number theory exercise for elementary school). Now, this immediately rang some alarms, as powers are learned in grade 8 (final grade before high school), when they certainly don't know any modular arithmetic or induction, let alone more advanced number theory. I tried to solve it anyway to see if this could actually be used, but to my surprise, I couldn't. Obviously, when $n=1$ we get $17$, which is prime, but for $n>1$ it seems that it will never be prime again, although I fail to show it (computer says that the expression is never prime in range $n\in[2, 100000000]$). There is, of course, possibility of a typo in question, but computer check up makes me believe that this is "legit" question.

My work:

First of all, for $n=1$ we have $3^{2n+1}-4^{n+1}+6^n = 17$ which is prime.

Secondly, it is easy enough to check that for $n = 2k,\ k\in\mathbb N$ we have $5\mid 3^{2n+1}-4^{n+1}+6^n$.

This looked promising, but for $n = 5$, we get $3^{2n+1}-4^{n+1}+6^n = 211\cdot 857$ as prime decomposition which is definitely worrisome.

I tried to find some appropriate $d\in\mathbb N$ such that $n = qd + r$ to build some casework with respect to $r$, but had no luck.

What I did notice is that if you pick $n$ in some non-trivial ideal $(d)$, there is at least one prime $p_d$ such that $p_d\mid 3^{2n+1}-4^{n+1}+6^n$, for all $n\in (d)$.

(though, I proved this only for $d=2$, for $d>2$ this is but a computer inspired conjecture)

Here is a table:

\begin{array}{c | c} d & p_d \\ \hline 2 & 5 \\ 3 & 19 \\ 4 & 5, 13 \\ 5 & 211 \\ 6 & 5, 7, 19 \\ 7 & 29, 71 \\ 8 & 5, 13, 97 \\ 9 & 19, 1009 \\ 10 & 5, 11, 211\\ \end{array}

Another attempt was obviously to try to factor $3^{2n+1}-4^{n+1}+6^n$ directly. Some obvious attempts led me to believe this approach might fail too. Indeed, polynomials $$x^{2n+1} - y^{2n+2} + x^ny^n,$$ $$x^{2n+1} - (x-1)^{2n+2} + x^n(x-1)^n$$ and $$x^{2n+1} - (x+1)^{n+1} + x^n(x-1)^n$$ are irreducible over $\mathbb Q$.

This leaves me without ideas. Any help would be much appreciated.

  • $\begingroup$ assume it can be factored using your symbols. See what you get. This is the flip side of the mod p coin. $\endgroup$ – Will Jagy Feb 8 '16 at 22:00

$x = 3^n, y = 2^n$ $$ 3 x^2 + x y - 4 y^2 = (3x + 4y)(x - y)$$

  • 2
    $\begingroup$ Thank you. This substitution never occurred to me, although it should have. $\endgroup$ – Ennar Feb 8 '16 at 22:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.