Find prime factorization of $2^{22} + 1$

Question

Find the prime factorization of $2^{22} + 1$.

How can I approach this with a subtle way?

I know that $a^n -b^n = (a-b) (a^{n-1}+a^{n-2}b + \cdots + ab^{n-2}+b^{n-1})$ and $a^{2n+1} + b^{2n+1} = (a+b) (a^{2n}-a^{2n-1}b + \cdots - ab^{2n-1}+b^{2n})$. So far I have tried to apply the latter one on $4^{11} + 1$.

Lucian · Answer 1 · 2014-12-29T14:02:11.030

6

$2^{22}+1=2^2\cdot2^{20}+1=4\cdot\Big(2^5\Big)^4+1^4.\quad$ But $4x^4+1=\big(2x^2-2x+1\big)\big(2x^2+2x+1\big)$.

edited Dec 29 '14 at 14:02

answered Dec 29 '14 at 11:27

Lucian

48,334
2
83
154

It's a problem from a high school competition. – Gary Dec 29 '14 at 12:28
In general, $4x^4+a^4=\big(2x^2-2ax+a^2\big)\big(2x^2+2ax+a^2\big)$. – Lucian Dec 29 '14 at 14:10
Thus the answer is $5 * 397 * 2113 = 2^{22}+1$, thanks! – Gary Dec 29 '14 at 18:45

Find prime factorization of $2^{22} + 1$

1 Answers1