1
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ Don't post images of text. Write down the questions - that way they can be found using a search function. $\endgroup$ – 5xum Nov 15 '17 at 14:23
  • $\begingroup$ Ok, thnx! I changed it! $\endgroup$ – WinstonCherf Nov 15 '17 at 14:29
  • $\begingroup$ Ok, I changed it! $\endgroup$ – WinstonCherf Nov 15 '17 at 15:49
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Thnx! I found the solution. Can you please solve e) for me? What did I do wrong? $\endgroup$ – WinstonCherf Nov 15 '17 at 15:50
  • $\begingroup$ @Lene Coenen Just $993=3\cdot331$. $\endgroup$ – Michael Rozenberg Nov 15 '17 at 15:54
  • $\begingroup$ Sorry, that's my mistace. But I have 2^5∗3∗7∗31∗151∗331 and it has to be 3^2∗7∗11∗31∗151∗331. $\endgroup$ – WinstonCherf Nov 15 '17 at 15:58
  • $\begingroup$ @Lene Coenen $2^5+1\neq2^5$. $\endgroup$ – Michael Rozenberg Nov 15 '17 at 16:01
  • $\begingroup$ Yes, I know. I changed the 32 for the 2^5. So 31∗1057∗32∗993 = 2^5∗3∗7∗31∗151∗331. But that's a wrong answer. $\endgroup$ – WinstonCherf Nov 15 '17 at 16:05
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$

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.