A simple method of factorization $ 2^{30}+1 $

Question

How can you factor $ 2^{30} + 1 $? This task was supposed to be at one interview, there is an assumption that there should be a simple solution.

Answer 1

Hint: $a^k+1$ is divisible by $a+1$ if $k$ is odd.

Answer 2

I would note it is a sum of cubes and fifth powers, so $2^{10}+1=1025$ and $2^6+1=65$ are both factors. In terms of primes that gives us $5^2\cdot 13 \cdot 41$ as factors. At this point in an interview (depending on the position) I would declare success and move on. Getting the remaining $80581$ would take a bunch of hand calculation and finding $61\cdot 1321$ doesn't seem reasonable either.

Answer 3

Firstly, in an interview there is often a difference between showing that there is a simple solution (existence) and outlining the approach, versus actually finding the solution.

That is, it might suffice to outline a standard prime factorising algorithm and show that it could be computed in trivial time.

One of the simplest classic approaches is that to factor $x$, you only need to test the primes that are less than $\sqrt{x}$. If $x=2^{30}+1$, then $\sqrt{x+1} \simeq 32768$. There are less than 3000 primes that satisfy this constraint, so it is very feasible on any computing platform.

Once each prime factor was found, one would divide that factor out, and then only need to search for primes up to an even smaller upper bound. Thus after the finding that 5 is a prime, one need only search for other prime factors less than 14654.

Thus, you have an algorithm that would find all the factors of $2^{30}+1$ in ascending order.

That is, $2^{30}+1 = 5 \times 5 \times 13 \times 41 \times 61 \times 1321$.

The key to nearly any sensible prime factorization approach is to efficiently find the first factor. Thus, in some ways it could be said that factoring $2^{30}+1$ is easy because it has lots of prime factors, and most of them are very small. (Contrast this to encryption are based on numbers that are very hard to factor, because they typically one have 2 factors and each of them are very very large.)

Anyway, as @Robert indicated, the key to solving this directly is to realise that if $k$ is odd, then $x^k+1$ can be elegantly factorised, as $(x+1)$ is a factor.

For example, $$x^7+1 = (x+1)(x^6-x^5+x^4-x^3+x^2-x+1)$$ Note that $z^{30}+1 = (z^2)^{15}+1$ and so $z^2+1 $ is a factor.

Letting $z=1$ shows that 5 is a factor of $2^{30}+1$.

Similarly, you could use the well-known sum of cubes factorisation. $x^3+1 = (x+1)(x^2-x+1)$, to show that $$2^{30}+1 = (2^{10}+1)(2^{20}-2^{10}+1) = 1025 \times 1047553$$ and continue from there.

Answer 4

Observe that $$x^k+1=\frac{x^{2k}-1}{x^k-1}=\frac{\prod_{d\mid 2k}\Phi_{d}(x)}{\prod_{d\mid k}\Phi_{d}(x)}=\prod_{d\mid 2k,\ d\nmid k}\Phi_{d}(x)$$ With $\Phi_n(x)$ being the $n^\text{th}$ cyclotomic polynomial. It follows that $$2^{30}+1=\Phi_4(2)\Phi_{12}(2)\Phi_{20}(2)\Phi_{60}(2)$$ With the individual factors computed as $$\Phi_4(2)=2^2+1=5$$ $$\Phi_{12}(2)=2^4-2^2+1=13$$ $$\Phi_{20}(2)=2^8-2^6+2^2-2^2+1=5\times 41$$ $$\Phi_{60}(2)=2^{16}+2^{14}-2^{10}-2^8-2^6+2^2+1=61\times 1321$$ Giving an overall factorization of $\boxed{2^{30}+1=5^2\times 13\times 41\times 61\times 1321}$

Answer 5

Yet another easy observation: since $4X^4+1=(2X^2+2X+1)(2X^2-2X+1)$, we get $4\cdot2^{28}+1=(2\cdot2^{14}+2\cdot2^7+1)(2\cdot2^{14}-2\cdot2^7+1)$.