Prime factorization of integers 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?
 A: the trick in c) to transform $2^{15}$ in $(2^5)^3$ and use $a^3-b^3$ formula
A: 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
A: 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$.
