Factorization with smart way.

Question

$3^{15} + 1 = 14348908$ How to factorize it without using calculator. Please me give. I can only do:

$3^{15} + 1 = 14348908 = (3+1)(3^{14}-...+ 1)$

Answer 1

Other divisors of $3^{15}+1$ are $3^5+1$ and $3^3+1$. And both are divisible by $3+1$.

Answer 2

Starting from ajotatxe's answer, we know that $3^{15}+1$ is divisible by $3+1=4$, $3^3+1=28=4\cdot7$, and $3^5+1=244=4\cdot61$. If you remember how to do long division, it's relatively easy to do the following by hand:

$$\begin{align} 14348908/4&=3587227\\ 3587227/7&=512461\\ 512461/61&=8401 \end{align}$$

So so far we have

$$3^{15}+1=4\cdot7\cdot61\cdot8401$$

It remains to factor the $8401$ or show that it's prime. At this point I think you're out of luck, and just have to do trial division by primes up to something shy of $100$. You can pretty easily see that $3$, $5$, $7$, and $11$ don't divide $8401$, but after that I think there's a lot of scratchwork to do, unless (like me) you peak at the answer online.