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

  • Thread starter Thread starter Hivoyer
  • Start date Start date
  • Tags Tags
    Beginner Proof
Click For Summary
SUMMARY

The discussion focuses on factoring the expression 215 - 1 and finding an integer x such that 1 < x < 232767 - 1, where 232767 is divisible by x. The factorization of 215 - 1 results in the product of 31 and 1023. For the second part, it is established that x must be a power of 2, as only powers of 2 can evenly divide another power of 2. The relationship between these two problems lies in the properties of divisibility and factorization of powers of 2.

PREREQUISITES
  • Understanding of factorization techniques, specifically for expressions of the form 2n - 1.
  • Knowledge of divisibility rules, particularly regarding powers of integers.
  • Familiarity with the concept of integer sequences and their properties.
  • Basic algebraic manipulation skills to handle polynomial expressions.
NEXT STEPS
  • Study the factorization of expressions of the form 2n - 1, including specific cases like 23 - 1 and 25 - 1.
  • Learn about the properties of powers of 2 and their divisibility.
  • Explore integer sequences and their applications in number theory.
  • Investigate polynomial factorization techniques, particularly for cubic and higher-degree polynomials.
USEFUL FOR

This discussion is beneficial for students studying number theory, mathematicians interested in divisibility and factorization, and educators looking for examples of problems involving powers of integers.

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 [tex]2^{15} - 1 = 32,767[/tex] into a product of two smaller positive integers.
b) Find an integer [tex]x[/tex] such that [tex]1 < x < 2^{32767} - 1[/tex] and [tex]2^{32767}[/tex] is divisible by [tex]x[/tex].

Homework Equations



It is shown above the problem that:
[tex]x = 1 * 2 * 3 * 4 * ... * (n + 1) + 2 = 2 * (1 * 3 * 4 * ... *(n + 1) + 1[/tex]
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 [itex]2^{32767}[/itex] 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 ·
Replies
3
Views
3K
Proof: Divisibility of Integers by 4
  • · Replies 5 ·
Replies
5
Views
2K
Proof: Integer Divisibility by 3 via Polynomials
  • · Replies 2 ·
Replies
2
Views
2K
Prove: If the integer ## a ## is not divisible by ## 2 ## or ## 3 ##....
  • · Replies 9 ·
Replies
9
Views
3K
For n>3, show that the integers n, n+2, n+4 cannot all be prime
  • · Replies 27 ·
Replies
27
Views
4K
Proof: Palindromes Divisible by 11
  • · Replies 1 ·
Replies
1
Views
2K
Express ##x^3+y^3## in terms of ##m## and ##n##
  • · Replies 17 ·
Replies
17
Views
3K
Show that the sum of twin primes ## p ## and ## p+2 ## is divisible?
  • · Replies 17 ·
Replies
17
Views
3K
Prove that ## a^{({2}^{n})}\equiv 1\pmod {2^{n+2}} ## for any ##n##?
  • · Replies 6 ·
Replies
6
Views
3K
Factoring difference of squares not working?
  • · Replies 3 ·
Replies
3
Views
3K