Prime factorization of integers

Question

Find the prime factorization of the following integers:

$e) 2^{30} -1$

Click here for the solutions

I used the formulas:

$a^2-1^2=(a-1)(a+1)$

$a^3+b^3=(a+b)(a^2-ab+b^2)$

$a^3-b^3=(a-b)(a^2+ab+b^2)$

And I became:

$2^{30} -1$

$=(2^{15}-1)(2^{15}+1)$

$=(2^5-1)(2^{10}+2^5+1)(2^5+1)(2^{10}-2^5+1)$

$=31*1057*32*993$

$=2^5*3*7*31*151*331$

What did I do wrong?

Answer 1

For example: $$10^6-1=(10^3-1)(10^3+1)=(10-1)(10^2+10+1)(10+1)(10^2-10+1)=$$ $$=9\cdot111\cdot11\cdot91=3^3\cdot7\cdot11\cdot13\cdot37;$$ $$10^8-1=(10^4-1)(10^4+1)=(10^2-1)(10^2+1)\cdot10001=$$ $$=(10-1)(10+1)\cdot101\cdot73\cdot137=3^2\cdot11\cdot73\cdot101\cdot137;$$ $$2^{15}-1=(2^5-1)(2^{10}+2^5+1)=31(2^{10}+2^5+1).$$ Now, let $2=x$.

Thus, $$2^{10}+2^5+1=x^{10}+x^5+1=x^{10}+x^6+x^2-x^6-x^4-x^2+x^5+x^4+x^3-x^3+1=$$ $$=x^2(x^8+x^4+1)-x^2(x^4+x^2+1)+x^3(x^2+x+1)-(x-1)(x^2+x+1)=$$ $$=x^2(x^8+2x^4+1-x^4)-x^2(x^4+x^2+1)+(x^2+x+1)(x^3-x+1)=$$ $$=(x^4+x^2+1)(x^6-x^4+x^2-x^2)+7\cdot7=$$ $$=(x^4+2x^2+1-x^2)\cdot48+7\cdot7=(x^2+x+1)(x^2-x+1)\cdot48-7\cdot7=$$ $$=7\cdot3\cdot48+7\cdot7=7(144+7)=7\cdot151.$$

Id est, $$2^{15}-1=7\cdot31\cdot151.$$

Answer 2

the trick in c) to transform $2^{15}$ in $(2^5)^3$ and use $a^3-b^3$ formula

Answer 3

a^n - b^n = (a - b)(a^(n-1) + a^(n-2)b + a^(n-3)b^2 + ... + ab^(n-2) + b^(n-1)) - just prove it. So, a^n - 1 = (a - 1)(a^(n-1) + a^(n-2) + ... + a + 1). May be it can help you

Answer 4

One good method to obtain some factors of numbers of the form $a^n-1$ is to look at the factorization of $x^{n}-1$ into cyclotomic polynomials: $$ x^n - 1 = \prod_{d\mid n}\Phi_d(x) $$

$ x^6-1 = \Phi_{1} \Phi_{2} \Phi_{3} \Phi_{6} =(x - 1) (x + 1) (x^2 + x + 1) (x^2 - x + 1) $.

Therefore, $10^6-1=9 \cdot 11 \cdot 111 \cdot 91$. It remains to factor $111$ and $91$.

$ x^8-1 = \Phi_{1} \Phi_{2} \Phi_{4} \Phi_{8} =(x - 1) (x + 1) (x^2 + 1) (x^4 + 1) $.

Therefore, $10^8-1=9 \cdot 11 \cdot 101 \cdot 10001$. It remains to factor $10001$.

You get the idea...

Of course, finding the factorization of $x^{n}-1$ into cyclotomic polynomials is mostly an application of the identity $x^n-1 = (x-1)(x^{n-1}+ \cdots +x + 1)$ to various factors of $n$.