prime factorization?
Thanks!
gmat prep prime factors
This topic has expert replies
-
- Senior | Next Rank: 100 Posts
- Posts: 30
- Joined: Sun Apr 27, 2008 4:22 pm
4^17 - 2^28
= (2^2)^17 - 2^28
=2^34-2^28
=2^28(2^6-1)
=(2^28)(63)
Greatest prime factor is 7.
= (2^2)^17 - 2^28
=2^34-2^28
=2^28(2^6-1)
=(2^28)(63)
Greatest prime factor is 7.
GMAT/MBA Expert
- Ian Stewart
- GMAT Instructor
- Posts: 2621
- Joined: Mon Jun 02, 2008 3:17 am
- Location: Montreal
- Thanked: 1090 times
- Followed by:355 members
- GMAT Score:780
Definitely prime factorization! First, it's easiest to see how you can factor if you write both exponential expressions with the same base:
4^17 - 2^28 = (2^2)^17 - 2^28 = 2^34 - 2^28
Both 2^34 and 2^28 are divisible by 2^28, so we can factor that out:
2^34 - 2^28 = 2^28 * ( 2^6 - 1)
Now, the expression in brackets is small enough to calculate:
2^28 * ( 2^6 - 1) = 2^28 * (64 - 1) = 2^28 * 63 = 2^28 * 3^2 * 7
Once you get this far, any question about divisibility is easy to answer. For example, what's the largest prime divisor? It's 7.
4^17 - 2^28 = (2^2)^17 - 2^28 = 2^34 - 2^28
Both 2^34 and 2^28 are divisible by 2^28, so we can factor that out:
2^34 - 2^28 = 2^28 * ( 2^6 - 1)
Now, the expression in brackets is small enough to calculate:
2^28 * ( 2^6 - 1) = 2^28 * (64 - 1) = 2^28 * 63 = 2^28 * 3^2 * 7
Once you get this far, any question about divisibility is easy to answer. For example, what's the largest prime divisor? It's 7.
GMAT/MBA Expert
- Ian Stewart
- GMAT Instructor
- Posts: 2621
- Joined: Mon Jun 02, 2008 3:17 am
- Location: Montreal
- Thanked: 1090 times
- Followed by:355 members
- GMAT Score:780
Yes, that's essentially the idea- really, it's dividing up the number until you get *only* primes. If you need to prime factorize, just start dividing any way you like, and keep going until all you have are primes. For example, start with 90:vinviper1 wrote:I need to work on my prime factorization skills. Is that simply breaking down the number until you get some primes?
90 = 9*10 = 3*3*2*5
You don't need to start with 9*10; you'll get the same answer no matter how you begin. So you could have instead done;
90 = 2*45 = 2*9*5 = 2*3*3*5
which is the same as the above, just in a different order.
Number theorists normally write prime factorizations by using exponents, and normally write the primes in increasing order, so the above prime factorization would normally be written 2*3^2*5.
One of the most important facts in all of mathematics is that prime factorizations are 'unique'. If you want to multiply primes together to get 90, for example, you must multiply one 2, one 5, and two 3s. There's no other way to do it. It is because of this that prime factorizations are so useful; if you know 90 = 2*3^2*5, you can see all of the divisors of 90. As a simple example, you can see immediately that the only primes which are divisors of 90 are 2, 3, and 5.
Prime factorization is an amazingly useful technique, especially on harder GMAT questions that mention 'divisibility' or 'divisors'. Experience helps a lot here, though. Not only do you need to know how to find a prime factorization, but often you need to know what to do after you've found it. That part is often different from question to question, and it's very useful to see many different examples. The question you've posted is a great start, and a good example of a fairly difficult GMAT question on prime factorization.
Ian Stewart wrote:Definitely prime factorization! First, it's easiest to see how you can factor if you write both exponential expressions with the same base:
4^17 - 2^28 = (2^2)^17 - 2^28 = 2^34 - 2^28
Both 2^34 and 2^28 are divisible by 2^28, so we can factor that out:
2^34 - 2^28 = 2^28 * ( 2^6 - 1)
Now, the expression in brackets is small enough to calculate:
2^28 * ( 2^6 - 1) = 2^28 * (64 - 1) = 2^28 * 63 = 2^28 * 3^2 * 7
Once you get this far, any question about divisibility is easy to answer. For example, what's the largest prime divisor? It's 7.
Hi Ian,
I know this post is already quite old, but I've been trying to understand prime factorization and I'm stuck here with your explanation.
I'm lost when you go from this 2^34 - 2^28 to this 2^28 * ( 2^6 - 1)
Can you explain plz?
Thx a lot!
-
- Master | Next Rank: 500 Posts
- Posts: 166
- Joined: Sat Apr 18, 2009 10:41 pm
- Thanked: 9 times
- GMAT Score:770
Hi.nifoui7 wrote:Ian Stewart wrote:Definitely prime factorization! First, it's easiest to see how you can factor if you write both exponential expressions with the same base:
4^17 - 2^28 = (2^2)^17 - 2^28 = 2^34 - 2^28
Both 2^34 and 2^28 are divisible by 2^28, so we can factor that out:
2^34 - 2^28 = 2^28 * ( 2^6 - 1)
Now, the expression in brackets is small enough to calculate:
2^28 * ( 2^6 - 1) = 2^28 * (64 - 1) = 2^28 * 63 = 2^28 * 3^2 * 7
Once you get this far, any question about divisibility is easy to answer. For example, what's the largest prime divisor? It's 7.
Hi Ian,
I know this post is already quite old, but I've been trying to understand prime factorization and I'm stuck here with your explanation.
I'm lost when you go from this 2^34 - 2^28 to this 2^28 * ( 2^6 - 1)
Can you explain plz?
Thx a lot!
It is similar to simplifying 12 - 6
Dont subtract it directly. Instead you can put it as (6*2) - 6
Now take 6 common in both the terms. You get 6(2 - 1) = 6
This is wht Ian has done.
For this problem it is
2^34 - 2^28
2^34 can be written as (2^28)*(2^6). As per rules of indices.
So we have (2^28)*(2^6) - (2^28)
Take 2^28 common in both terms to get 2^28(2^6 - 1)
GMAT/MBA Expert
- Ian Stewart
- GMAT Instructor
- Posts: 2621
- Joined: Mon Jun 02, 2008 3:17 am
- Location: Montreal
- Thanked: 1090 times
- Followed by:355 members
- GMAT Score:780
Just to add to the explanation above: the factorization we're doing here is one you probably will have done many times in algebra questions. When you see something like x^5 - x^3, we'd almost always want to factor out the term with the smaller power: x^5 - x^3 = x^3(x^2 - 1). We're using the same type of factorization in the question above - it's just that we have a base of 2 instead of x.nifoui7 wrote: Hi Ian,
I know this post is already quite old, but I've been trying to understand prime factorization and I'm stuck here with your explanation.
I'm lost when you go from this 2^34 - 2^28 to this 2^28 * ( 2^6 - 1)
Can you explain plz?
Thx a lot!
For online GMAT math tutoring, or to buy my higher-level Quant books and problem sets, contact me at ianstewartgmat at gmail.com
ianstewartgmat.com
ianstewartgmat.com