If a and b are positive integers such that gcd(a,b)=13, then find the

Question

If a and b are positive integers such that gcd(a,b)=13, then find the sum of all possible distinct values of  gcd(a^3,b) .

gcd = Greatest common divisor

A. 13 
B. 2197
C. 2210
D. 2379
E. Can't be determined

ArunSharma12 · Answer

GCD(a,b)=13
 a = 13^x * k   (a has 13 one factor and some other integer not common to b)
 b = 13^y * m  (b has 13 one factor and some other integer not common to a)
such that minimum value between x and y has to 1.

if x = 1, the  a^3 = 13^3 * k^3  
 GCD(a^3,b) :
b can take the following values 
 b_1 = 13*m ;  GCD_1 = 13 
 b_2 = 13^2*m ;  GCD_2 = 13^2 
 b_3 = 13^3*m ;  GCD_3 = 13^3 
after this if we increase the power of 13 in b, it'll start giving us the GCD as  13^3 .

when x = 2, the  a^3 = 13^6 * k^3  
 GCD(a^3,b) :
b can take the following values 
 b_1 = 13*m ;  GCD_1 = 13

sum of all possible distinct values of gcd(a3,b) =  13 +13^2 + 13^3  = 2379
Ans: D

GaurSaini · Answer

a = 13^m.x
b = 13^n.y

as GCD(a,b) is 13, either m or n will be 1.

GCD(a^3,b) = ?

i.e. GCD((13)^3m.x,13^n.y) = ?

when m=1, n can be 1,2,3

GCD(13^3.x, 13.y) = 13
GCD(13^2.x, 13^2.y) = 13^2 
GCD(13^3.x, 13^3.y) = 13^3

when n=1, whatever power m takes, GCD(13^3m.x,13^n.y) will always be 13.

Hence there are 3 possible values 13, 13^2, 13^3.

13+13^2+13^3 = 2379

funkyakki · Answer

Hi, can you please explain that for case when x = 2, why i can't take the value  b_4.

For example,

b_4 = 13^4*m ;  GCD_4 = 13^4

ArunSharma12 · Answer

Hi funkyakki,
here b can not take any higher powers.
lets take the case,
 b_2=13^2∗m; GCD_2=13^2 
minimum value of x,y is 2.
once we focus on GCD value, we can see that GCD is now 13^2 and it violates the constraint given in the question stem: gcd(a,b)=13.
Hence for any higher powers of x = 2,3,4... there will be only one value for y, y =1.
This will also limit the GCD value of  GCD(a^3,b)  to 13 thereby creating no more distinct GCD values.

Fdambro294 · Answer

Basic Concept: if we raise any given integer to a positive integer Power, the UNIQUE Prime Factors that make up that number will not change ——-> only the amount of those Unique Prime Numbers will change

If the GCF of (A , B) = 13

Then when we raise A to the 3rd Power and keep B the same, the same Unique Prime Factors that divide into A and B will be there. All that will change is the amount.

Case 1:

A = 13x

B = 13y

Since GCF = 13, x and y are co-prime

When we raise A to the 3rd Power, the two values will still only share a Factor of 13

Case 2:
A = 13x
B = (13)^2 y

Where x and y are co-prime such that the GCD(A,B) = 13

Right now all A and B shares is the common factor of one 13

However when we Cube A, there will be 3 more prime factors of 13 that make up A

The GCF will now become (13)^2

Case 3:
A = 13x
B = (13)^3 y

Originally, like the others, the GCF of A and B = 13 ———- the only factor they share is a 13

However if we Cube A ———> (A)^3 will now have THREE 13s and the new Greatest Shared Factor will be (13)^3

Sum of all possible GCFs:

13 + (13)^2 + (13)^3 = 2,379

D

Posted from my mobile device

bumpbot · Answer

Automated notice from GMAT Club BumpBot: 

A member just gave Kudos to this thread, showing it’s still useful. I’ve bumped it to the top so more people can benefit. Feel free to add your own questions or solutions.

 This post was generated automatically.

If a and b are positive integers such that gcd(a,b)=13, then find the

Prep Toolkit

Top 5 GMAT Debrief Videos

615 to 715 in 15 Days (Ria's Strategies)

More than Quant/Verbal Abilities: Speed vs. Accuracy

745 with Only Self-Prep and GMAT Club

From 555 to 765: 210-point Improvement

Perfect 805 Score Debrief by Julia

My Rewards

GMAT Problem Solving (PS) Questions

If a and b are positive integers such that gcd(a,b)=13, then find the

Prep Toolkit

615 to 715 in 15 Days (Ria's Strategies)

More than Quant/Verbal Abilities: Speed vs. Accuracy

745 with Only Self-Prep and GMAT Club

From 555 to 765: 210-point Improvement

Perfect 805 Score Debrief by Julia

My Rewards