GmatPrep Test 2 - 2 Difficult Number Property Problems

This topic has expert replies
Newbie | Next Rank: 10 Posts
Posts: 8
Joined: Fri Jan 05, 2007 6:28 pm
Followed by:1 members
Two different problems:

1) If y=8x+12, where y and x are integers, what is the greatest common factor of x and y? The test claims that, to answer this, it is suficient to know that y=12z, where z is an integer. Can someone please show how to calculate the actual GCF with this info?

2) What is the gratest prime factor of ( 4^17 ) - ( 2^28 )?


Can someone good with number properties please work out both problems for the rest of us mortals? =)

Many thanks in advance!
Source: — Problem Solving |

User avatar
Legendary Member
Posts: 2469
Joined: Thu Apr 20, 2006 12:09 pm
Location: BtG Underground
Thanked: 85 times
Followed by:14 members
hmmm really good problems 8)

medenica wrote:Two different problems:

1) If y=8x+12, where y and x are integers, what is the greatest common factor of x and y? The test claims that, to answer this, it is suficient to know that y=12z, where z is an integer. Can someone please show how to calculate the actual GCF with this info?
it would have been better if you presented a full problem with other options...
still i can provide the explanation.

Here i go:
If you have give y=12z as information: that means y is divisible by 12

this also means that it is divisible by 3 & 4

that means x has to be divisible of 3 so as to meet our given condition.


2) What is the greatest prime factor of ( 4^17 ) - ( 2^28 )?


Can someone good with number properties please work out both problems for the rest of us mortals? =)

Many thanks in advance!
note that
4^17= (2^2)^17= 2^34

now 2^34- 2^28 = (2^28 ) X (2^(34-28 )-1 )

note that the answer is divisible by 2^28
lets check the other factor : (2^6)-1= 64-1 = 63

we know that 63 = 3*3*7

that means 7 is the greatest prime number.


reply it if you find this explanation inadequate :)

Newbie | Next Rank: 10 Posts
Posts: 8
Joined: Fri Jan 05, 2007 6:28 pm
Followed by:1 members

by medenica » Mon Jan 15, 2007 9:17 pm
Yes, 7 is what I got for 2) as well.

However for 1), you never calculate what their greatest common factor is. I see the part on why y is divisible by 12 but, how do you determine that x is divisible by 12 as well? Furthermore, how do you determine that there is no greater factor, say 24?

Btw, yes I omitted the other part of the DS question but this is according to the test all you need. Since it's all one needs, I wanted to see how the calculation goes and see what the actual gcf is...

Senior | Next Rank: 100 Posts
Posts: 76
Joined: Tue Dec 26, 2006 11:26 am
Followed by:3 members

by maxim730 » Tue Jan 16, 2007 11:20 am
I'm confused about 1.


y=12z

if z = 4, then y = 28,

y=8x+12,

say x = 2

y = 8(2) + 12 = 28

x (which is 2) is not divisible by 3? I'm lost!!\


2. how did you simplify: now 2^34- 2^28 = (2^28 ) X (2^(34-28 )-1 ) ?

TY

User avatar
Legendary Member
Posts: 2469
Joined: Thu Apr 20, 2006 12:09 pm
Location: BtG Underground
Thanked: 85 times
Followed by:14 members

by aim-wsc » Tue Jan 16, 2007 10:06 pm
maxim730 wrote:I'm confused

2. how did you simplify: now 2^34- 2^28 = (2^28 ) X (2^(34-28 )-1 ) ?

TY
let
2^34=x
&
2^28=y

now if you want me to explain this analytically:
here i go:

thus: (2^34) - (2^28 )= x-y= (x) X ((y/x)- 1)

= 2^28 X ((2^34 / 2^28 ) -1 )

note that (2^34 / 2^28 ) = 2^(34-28 )

Senior | Next Rank: 100 Posts
Posts: 76
Joined: Tue Dec 26, 2006 11:26 am
Followed by:3 members

by maxim730 » Wed Jan 17, 2007 6:26 am
You mean let 2^28 = x right?

I had no idea about the formula:

x-y= (x) X ((y/x)- 1)

!!!! I'm surprised I haven't encountered it so far on any of my review :(
aim-wsc wrote:
maxim730 wrote:I'm confused

2. how did you simplify: now 2^34- 2^28 = (2^28 ) X (2^(34-28 )-1 ) ?

TY
let
2^34=x
&
2^28=y

now if you want me to explain this analytically:
here i go:

thus: (2^34) - (2^28 )= x-y= (x) X ((y/x)- 1)

= 2^28 X ((2^34 / 2^28 ) -1 )

note that (2^34 / 2^28 ) = 2^(34-28 )

GMAT/MBA Expert

User avatar
GMAT Instructor
Posts: 2228
Joined: Wed Dec 27, 2006 3:28 pm
Location: Montreal, Canada
Thanked: 639 times
Followed by:694 members
GMAT Score:780

by Stacey Koprince » Wed Jan 17, 2007 6:56 pm
Hi, medenica

Are you sure you transcribed the question completely accurately? I think you may have transposed x and y in your original formula. So, you typed "y=8x+12" but this problem is in OG and it is printed as "x = 8y+12" which makes all the difference. As you transcribed it, the statement is insufficient. As the OG prints it, the statement is sufficient.

Also, in future, please do post the whole question, as it is usually better for comprehension to be able to see the entire problem.

So, I'll explain the OG question:
If x and y are positive integers such that x = 8y+12, what is the greatest common divisor of x and y?
(1) x = 12u, where u is an integer
(2) y = 12z, where z is an integer

A number properties rule we all need to know:
If two integers are added (or subtracted), any factors shared by those two integers will also be factors of the sum (or difference). For example, 2 + 4 = 6. 2 and 4 both have 2 as a factor. 2 is also a factor of 6.

(1) is insufficient. This basically tells us that 12 is a divisor of x. So if we plug into our original equation, we have (multiple of 12) = 8y + (multiple of 12). This tells us that the expression 8y must also be a multiple of 12. The prime factorization of 12 is 2*2*3. The 8 in the expression 8y can cover the two 2's that we need, but not the 3. So the 3 must be a part of y. At the least, then, y is a multiple of 3. x is also a multiple of 3 (since it is a multiple of 12), but this may not be the GREATEST common divisor of the two. Insufficient.

(2) is sufficient. So if we plug into our original equation, we have x = (multiple of 12) + (multiple of 12). Which means that x must also be a multiple of 12. Now, I know that both x and y are multiples of 12, but I still need to address the GREATEST common factor issue.

Number properties rule #2 we need to know:
If one number is n units away from another number, and n is a factor of both of those numbers, then the greatest common factor of the two numbers is n.

This is REALLY complicated. I'll explain this concept below, but you may just want to memorize the above rule. If so, skip to the paragraph that starts "back to our problem." By definition, the greatest common factor divides both numbers evenly without remainder - so the GCF cannot be bigger than the difference between the two numbers.

For example, 24 + 36 = 60. 12 is a factor of all 3 numbers, and the two smaller numbers are 12 units apart. We can re-write this as (12*2) + (12*3) = 60. So 12*3 is 12 units (or 12*1) away from 12*2. The higher number (36, or 12 * 3) is exactly one multiple higher than the lower number (24, or 12 * 2). We can't get any simpler than one multiple higher, so we can't go any higher than 12 for the GCF.

Back to our problem. So statement 2 tells us that 12 is a factor of both x and 8y, AND it tells us that x is 12 units away from 8y. By definition, then 12 is the GCF of x and 8y. But wait - the problem asks us about x and y, not x and 8y. Well, 8y is eight times bigger than y. So if 12 is the GCF of x and 8y, AND 12 is also a factor of y by itself, then 12 must be the GCF of x and y too. The GCF of x and y can't be bigger than the GCF of x and the larger multiple 8y.

This is a great one to skip on the test. Just make some kind of educated guess and MOVE ON!!!
:)
Please note: I do not use the Private Messaging system! I will not see any PMs that you send to me!!

Stacey Koprince
GMAT Instructor
Director of Online Community
Manhattan GMAT

Contributor to Beat The GMAT!

Learn more about me

User avatar
Legendary Member
Posts: 2469
Joined: Thu Apr 20, 2006 12:09 pm
Location: BtG Underground
Thanked: 85 times
Followed by:14 members

by aim-wsc » Thu Jan 18, 2007 1:16 pm
sorry ... was away for some days..
for first question: Stacey has talked enough.
maxim730 wrote:You mean let 2^28 = x right?

I had no idea about the formula:

x-y= (x) X ((y/x)- 1)
NO
i said its "2^28=y" & not "x"

sorry that was typo...for the formula

refer this one...
x-y= (y) X ((x/y)- 1)

User avatar
GMAT Instructor
Posts: 613
Joined: Thu Mar 22, 2007 6:17 am
Location: madrid
Thanked: 171 times
Followed by:64 members
GMAT Score:790

by kevincanspain » Thu Mar 22, 2007 6:40 am
Stacey Koprince wrote:If x and y are positive integers such that x = 8y+12, what is the greatest common divisor of x and y?
(1) x = 12u, where u is an integer
(2) y = 12z, where z is an integer
(1) x is a multiple of 12: Since 8y=x-12, 8y is multiple of 12 and thus y is a multiple of 3. We know that a common divisor of x and y is 3, but 3 need not be the greatest common divisor. For example, if x=60, y=6 and the greatest common divisor is 6. However, if x=36, y=3 and the greatest common divisor is 3. NOT SUFFICIENT

(2) y=12z. Thus x=8(12z)+12=12(8z+1)

Thus the greatest common divisor of x and y is 12* GCD(z,8z+1)

But GCD(z,8z+1)=1

Proof:

Suppose that z is divisible by d, an integer greater than 1. 8z is also divisible by d, so 8z+1 divided by d is an integer plus 1/d, which is not an integer. Thus 8z+1 is not divisible by d

Thus the greatest common divisor of x and y is 12

SUFFICIENT
Kevin Armstrong
GMAT Instructor
Gmatclasses
Madrid

Senior | Next Rank: 100 Posts
Posts: 80
Joined: Fri Apr 13, 2007 7:02 am
Location: Long Island

by maolivie » Wed Apr 25, 2007 7:07 am
what formula is this?

Senior | Next Rank: 100 Posts
Posts: 44
Joined: Wed Sep 03, 2008 11:27 am
Thanked: 2 times
GMAT Score:740

by java_ka_jalwa » Thu Oct 23, 2008 1:31 pm
This formula is a property of gcd:

gcd(a,am+b) = gcd(a,b)

So in this problem
gcd(z,8z+1) = gcd(z,1) gcd of 1 and any number is 1
gcd(z,8z+1) = 1

This is a pretty useful property. Probability of this being tested is low, but its an easy formula to remember