5
$\begingroup$

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.

$\endgroup$
11
$\begingroup$

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}$

$\endgroup$
7
  • 1
    $\begingroup$ This is very elegant. $\endgroup$
    – Lubin
    Aug 6 '18 at 1:58
  • 1
    $\begingroup$ Thanks! It's also not too hard to compute the relevant polynomials by hand (the section "Easy cases for computation" in the linked wiki article lists some strategies) :) $\endgroup$ Aug 6 '18 at 2:01
  • $\begingroup$ Again, computing $\Phi_{60}(2) = 61 \times 1321$ is not really something to do in an interview. $\endgroup$ Aug 6 '18 at 7:26
  • $\begingroup$ Perhaps they wanted to see the way to a solution, not the solution itself. $\endgroup$ Aug 6 '18 at 11:43
  • 1
    $\begingroup$ @RobertIsrael: probably the interviewer wanted to hear something along the lines "in order to find the prime divisors of $\Phi_{60}(2)$, it is enough to check the primes $\equiv 1\pmod{60}$. Since the order of $2$ in $\mathbb{Z}/(61\mathbb{Z})^*$ is what it is, $61$ is a prime divisor of $\Phi_{60}(2)$ and the problem boils down to checking that $1321$ is a prime". $\endgroup$ Aug 6 '18 at 16:45
8
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ $61\equiv 5 \bmod 8$ so $(2|61)\equiv 2^{30}\equiv -1\bmod 61$. $\endgroup$ Aug 6 '18 at 1:44
3
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Just so we can check any number-theoretic derivation... Mathematica gives: $5^2 \times 13 \times 41 \times 61 \times 1321 $. (Doesn't seem so simple that it could be done in an interview session...) $\endgroup$ Aug 6 '18 at 0:37
1
$\begingroup$

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)$.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Your early complete factorization is missing $61$ $\endgroup$ Aug 6 '18 at 1:59

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.