2

I got the book How to Prove it A Structured Approach and I'm ashamed to admit I failed to even do the first problem in the introduction chapter:

a) Factor $2^{15} - 1 = 32767$ into a product of two smaller positive integers.

b) Find an integer $x$ such that $1 < x < 2^{32767} - 1$ and $2^{32767}$ is divisible by $x$.

I think I'm supposed to use the same or similar method to solve both of these parts, however I feel like I hit bedrock.

darkradeon
  • 297

2 Answers2

4

Hint a: $15=3\times 5$ and $a^3-1=(a-1)\times (a^2+a+1)$

Woria
  • 1,783
  • 9
  • 15
2

Yes, you are supposed to use the same method. You want to consider the formula $x^n-1 =(x-1)(x^{n-1} + x^{n-2}... x + 1)$ for x > 1. It will help you out in both cases.

After the comments I see that the factorization I suggested is not going to help you in that exact form. 15 is divisible by 3 and 32767 is divisible by 7. So you can use my formula where $2^{15} =(2^5)^3$ and $2^{32767} = (2^7)^{4681}$.

I regret my original and 2nd misleading posts. Someday I'll figure out that 25 is not divisible by 3.

In the future, could you provide with your question some of your thinking or attempts. People prefer to help those who are trying to help themselves.

Betty Mock
  • 3,532
  • Well, not quite that formula. OP wants a generalization of it (factoring into $(x-1)$ and something else doesn't help when $x - 1 = 1$) – Dennis Meng Jan 15 '14 at 22:25
  • Sorry for not posting an attempt, but I pretty much failed at square 1.Basically my first attempt was to do something like what woso's answer and yours suggests, but then I couldn't figure out where to go.I mean I have $2^3 - 1 = (2 - 1)(2^2 + 2 + 1)$ and $2^5 - 1 = (2 - 1)(2^4 + 2^3 + 2^2 + 2 + 1)$.I don't have any idea what to do after this.Multiplying them together doesn't give back the original number. – darkradeon Jan 15 '14 at 22:36
  • @darkradeon $2^3 -1$ = 7 which is exactly $2^2 + 2 + 1$ and $2^5$ checks out similarly at 31. So I don't get why you couldn't get them to match up. 2-1 = 1 of course. I understand about failing at square 1; I hope you are at least at square 2 now. – Betty Mock Jan 16 '14 at 03:33
  • @DennisMeng gee I did say x > 1. Did you miss it? Since OP had a base of 2, we were in good shape. – Betty Mock Jan 16 '14 at 03:34
  • @BettyMock no no, that's not what I meant, what I meant was that I can't relate the results I get from the $(a - 1)(a^2+...+1)$ formula to what is required of me.In the answers it says that one possible solution is $32767 = 31 . 1057$.The 31 I got, however nothing I do with these expressions gets me near $1057$. – darkradeon Jan 16 '14 at 03:43
  • @darkradeon sorry I misunderstood your question. see revised answer – Betty Mock Jan 16 '14 at 03:50
  • @DennisMeng plz ignore previous comment, I misread what you were saying. You are entirely right. – Betty Mock Jan 16 '14 at 03:50