Factoring and Divisibility Problems with 2^n - 1: Beginner Proof Method

  • Thread starter Thread starter Hivoyer
  • Start date Start date
  • Tags Tags
    Beginner Proof
AI Thread Summary
The discussion revolves around solving two problems related to the expression 2^n - 1. The first part requires factoring 2^15 - 1, which equals 32,767, into two smaller positive integers, while the second part seeks an integer x that is a divisor of 2^32767. Participants note that for the second part, x must be a power of 2, as 2^32767 is only divisible by powers of 2. There is confusion about how to connect the methods used in both parts of the problem. Overall, the conversation highlights the need for clarity in applying mathematical principles to factorization and divisibility.
Hivoyer
Messages
26
Reaction score
0

Homework Statement



I'm given this problem and I think I'm supposed to use the same or similar method to solve both of its parts:

a) Factor 2^{15} - 1 = 32,767 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.

Homework Equations



It is shown above the problem that:
x = 1 * 2 * 3 * 4 * ... * (n + 1) + 2 = 2 * (1 * 3 * 4 * ... *(n + 1) + 1
While I get that it's true, I don't quite see how I can apply the same to solving the problem.Can anyone give a hint?

The Attempt at a Solution



I tried "guessing", however with no success.
 
Last edited:
Physics news on Phys.org
I don't see any connection between the two.
Can you factorise x3-1?
 
For b, you realize that 2^{32767} can be divided evenly only by another power of 2, right? So x must be a power of 2.
 

Similar threads

Proof That an Integer is Divisible by 2
Replies
3
Views
2K
Proof: Divisibility of Integers by 4
Replies
5
Views
2K
Proof: Integer Divisibility by 3 via Polynomials
Replies
2
Views
2K
Prove: If the integer ## a ## is not divisible by ## 2 ## or ## 3 ##....
Replies
9
Views
2K
For n>3, show that the integers n, n+2, n+4 cannot all be prime
Replies
27
Views
3K
Proof: Palindromes Divisible by 11
Replies
1
Views
1K
Express ##x^3+y^3## in terms of ##m## and ##n##
Replies
17
Views
3K
Show that the sum of twin primes ## p ## and ## p+2 ## is divisible?
Replies
17
Views
3K
Prove that ## a^{({2}^{n})}\equiv 1\pmod {2^{n+2}} ## for any ##n##?
Replies
6
Views
2K
Factoring difference of squares not working?
Replies
3
Views
2K

Hot Threads

Recent Insights

Back
Top