Greatest Common Divisor (GCD) and Least Common Multiple (LCM) Practice Questions — GMAT

Question 1Question →

A rectangular tabletop measuring $126\text{ centimeters}$ by $180\text{ centimeters}$ is to be completely covered by non-overlapping, identical square tiles of the maximum possible side length, such that no tiles need to be cut. How many such square tiles are required to cover the entire tabletop?

Show answer & explanation

Answer: 70

Answer

70 tiles are required to cover the tabletop.

To cover a

126\text{ cm} \times 180\text{ cm}

surface with identical square tiles of maximum side length without cutting, the side length of each square tile must be the greatest common divisor of

126

and

180

, which is

18\text{ cm}

. Dividing the surface dimensions by

18\text{ cm}

gives

7

tiles along one side and

10

tiles along the other, yielding a total of

70

tiles.

Step-by-Step Solution

1

Determine the prime factorizations of the tabletop dimensions 126 and 180.

126 = 2^1 \times 3^2 \times 7^1

and

180 = 2^2 \times 3^2 \times 5^1

Prime factorization allows systematic extraction of the greatest common divisor.

2

Calculate the Greatest Common Divisor (GCD) of 126 and 180.

\text{GCD}(126, 180) = 2^{\min(1,2)} \times 3^{\min(2,2)} = 2^1 \times 3^2 = 18

The maximum side length of a square tile that fits evenly without cutting is the GCD of the two dimensions.

3

Find the total number of tiles required.

\text{Total tiles} = \left(\frac{126}{18}\right) \times \left(\frac{180}{18}\right) = 7 \times 10 = 70

The total area divided by the area of one tile gives the number of tiles needed.

Key Concept

Greatest Common Divisor (GCD) application in geometric spatial partitioning

Question 2Question →

What is the greatest common divisor (GCD) of $2^3 \times 3^2 \times 5$ and $2^2 \times 3^3$ ?

36

72

180

1080

18

Show answer & explanation

Answer: $36$

Answer

The greatest common divisor (GCD) of

2^3 \times 3^2 \times 5

and

2^2 \times 3^3

is

36

.

The greatest common divisor (GCD) is calculated by taking the lowest power of each prime factor common to both expressions. For

2^3 \times 3^2 \times 5

and

2^2 \times 3^3

, the common prime factors are

2

and

3

. Taking the smallest exponents gives

2^2 \times 3^2 = 4 \times 9 = 36

.

Step-by-Step Solution

1

Identify the common prime factors in both numbers.

The prime factors present in both numbers are

2

and

3

. The factor

5

is only present in the first number.

GCD requires prime factors that are shared by all target numbers.

2

Select the minimum exponent for each common prime factor.

For

2

:

\min(3, 2) = 2

. For

3

:

\min(2, 3) = 2

. For

5

:

\min(1, 0) = 0

.

The GCD contains only the prime powers that divide both numbers completely.

3

Multiply the resulting prime power factors to evaluate the GCD.

\text{GCD} = 2^2 \times 3^2 = 4 \times 9 = 36

.

Evaluating the prime factor powers gives the final integer value.

Key Concept

To find the Greatest Common Divisor (GCD) of numbers written in prime factorized form, take the product of each common prime factor raised to its smallest exponent across all the factorizations.

Estimated Time:1m 0s

Question 3Question →

What is the least common multiple (LCM) of $12$ and $18$ ?

Show answer & explanation

Answer: 36

Answer

The least common multiple of

12

and

18

is

36

.

To find the least common multiple of

12

and

18

, determine the prime factorization of each number (

12 = 2^2 \times 3^1

and

18 = 2^1 \times 3^2

). The LCM is calculated by taking the maximum power of each prime factor present:

2^2 \times 3^2 = 4 \times 9 = 36

.

Step-by-Step Solution

1

Express both numbers in terms of their prime factorizations.

12 = 2^2 \times 3^1

and

18 = 2^1 \times 3^2

Prime factorization separates each number into basic prime components.

2

Select the highest power of each prime factor that appears in either factorization.

The highest power of

2

is

2^2

, and the highest power of

3

is

3^2

.

The least common multiple must contain enough factors to be divisible by both original numbers.

3

Calculate the product of these highest prime powers.

\text{LCM}(12, 18) = 2^2 \times 3^2 = 4 \times 9 = 36

Multiplying the chosen powers yields the minimum integer divisible by both

12

and

18

.

Key Concept

Finding the Least Common Multiple (LCM) via Prime Factorization

Estimated Time:45s

Question 4Question →

For two positive integers $a$ and $b$ , the greatest common divisor is $15$ and the least common multiple is $180$ . If $a = 45$ , what is the value of $b$ ?

12

15

60

135

180

Show answer & explanation

Answer: 60

Answer

60

For any two positive integers

a

and

b

, the product of their greatest common divisor and their least common multiple equals the product of the two numbers, expressed as

\text{GCD}(a, b) \times \text{LCM}(a, b) = a \times b

. Plugging in the given values yields

15 \times 180 = 45 \times b

. Dividing

2700

by

45

results in

60

.

Step-by-Step Solution

1

Recall the fundamental relation between GCD and LCM for two positive integers.

\text{GCD}(a, b) \times \text{LCM}(a, b) = a \times b

The product of the greatest common divisor and the least common multiple of two positive integers is equal to the product of the integers themselves.

2

Substitute the given values into the formula.

15 \times 180 = 45 \times b

We are given

\text{GCD}(a,b) = 15

,

\text{LCM}(a,b) = 180

, and

a = 45

.

3

Solve for

b

.

b = \frac{15 \times 180}{45} = \frac{180}{3} = 60

Dividing both sides by

45

simplifies to

180 \div 3 = 60

.

Key Concept

Relationship between GCD, LCM, and the product of two positive integers.

Estimated Time:1m 30s

Question 5Question →

For two positive integers $m$ and $n$ , their prime factorizations are given by $m = 2^3 \times 3^a \times 5^b$ and $n = 2^c \times 3^3 \times 5^1$ , where $a$ , $b$ , and $c$ are positive integer exponents. If the greatest common divisor of $m$ and $n$ is $\text{GCD}(m, n) = 360$ and their least common multiple is $\text{LCM}(m, n) = 108,000$ , what is the value of $a + b + c$ ?

7

8

9

10

11

Show answer & explanation

Answer: $10$

Answer

The correct value of

a + b + c

is

10

.

First, find the prime factorizations of

360

and

108,000

:
-

360 = 2^3 \times 3^2 \times 5^1

-

108,000 = 2^5 \times 3^3 \times 5^3

Using the properties of GCD and LCM:
- For base

2

:

\text{GCD}

power is

3

and

\text{LCM}

power is

5

. Since

m

has

2^3

,

n

must have

2^c

where

c = 5

.
- For base

3

:

\text{GCD}

power is

2

and

\text{LCM}

power is

3

. Since

n

has

3^3

,

m

must have

3^a

where

a = 2

.
- For base

5

:

\text{GCD}

power is

1

and

\text{LCM}

power is

3

. Since

n

has

5^1

,

m

must have

5^b

where

b = 3

.

Summing these values gives

a + b + c = 2 + 3 + 5 = 10

.

Step-by-Step Solution

1

Express GCD and LCM in prime factorized form.

\text{GCD}(m, n) = 360 = 2^3 \times 3^2 \times 5^1

and

\text{LCM}(m, n) = 108,000 = 2^5 \times 3^3 \times 5^3

.

Converting given numbers into prime powers allows direct comparison with the exponents of

m

and

n

.

2

Apply prime exponent min/max rules to determine

a

,

b

, and

c

.

For prime

2

:

\max(3, c) = 5 \implies c = 5

. For prime

3

:

\min(a, 3) = 2 \implies a = 2

. For prime

5

:

\max(b, 1) = 3 \implies b = 3

.

\text{GCD}

uses the minimum exponent for each prime factor, while

\text{LCM}

uses the maximum exponent.

3

Sum the derived exponents

a

,

b

, and

c

.

a + b + c = 2 + 3 + 5 = 10

.

The question asks for the sum

a + b + c

.

Key Concept

Prime Factor Exponent Rule for GCD and LCM

Alternative Method

Use the product formula

\text{GCD}(m, n) \times \text{LCM}(m, n) = m \times n

. Multiplying gives

360 \times 108,000 = 38,880,000 = 2^8 \times 3^5 \times 5^4

. Multiplying

m \times n = (2^3 \times 3^a \times 5^b) \times (2^c \times 3^3 \times 5^1) = 2^{3+c} \times 3^{a+3} \times 5^{b+1}

. Equating powers:

3+c=8 \implies c=5

,

a+3=5 \implies a=2

,

b+1=4 \implies b=3

. Thus

a+b+c = 2+3+5 = 10

.

Estimated Time:2m 0s

Question 6Question →

What is the number of distinct prime factors of the greatest common divisor (GCD) of $60$ and $90$ ?

2

3

4

5

30

Show answer & explanation

Answer: 3

Answer

3

The prime factorization of 60 is

2^2 \times 3 \times 5

and the prime factorization of 90 is

2 \times 3^2 \times 5

. The GCD is obtained by taking the lowest exponent for each common prime base:

\text{GCD}(60, 90) = 2^1 \times 3^1 \times 5^1 = 30

. The distinct prime factors of 30 are 2, 3, and 5, yielding a count of 3.

Step-by-Step Solution

1

Find the prime factorizations of 60 and 90.

60 = 2^2 \times 3^1 \times 5^1

and

90 = 2^1 \times 3^2 \times 5^1

Expressing numbers as products of prime factors is the standard method for finding their GCD.

2

Determine the GCD by taking the lowest power of each common prime factor.

\text{GCD}(60, 90) = 2^{\min(2,1)} \times 3^{\min(1,2)} \times 5^{\min(1,1)} = 2^1 \times 3^1 \times 5^1 = 30

The GCD takes the common prime bases raised to their minimum respective exponents.

3

Identify and count the distinct prime factors of 30.

The distinct prime factors of 30 are 2, 3, and 5, giving a total of 3 prime factors.

By prime definition, 1 is excluded from the list of prime factors.

Key Concept

Greatest Common Divisor (GCD) and Prime Factorization

Estimated Time:1m 0s

Question 7Question →

For two positive integers $x$ and $y$ , their greatest common divisor is $\gcd(x, y) = 12$ and their least common multiple is $\text{lcm}(x, y) = 10,800$ . If $x > y$ , $x$ is not divisible by $9$ , and $y$ is not divisible by $25$ , what is the value of $x + y$ ?

732

972

1,308

1,356

1,500

Show answer & explanation

Answer: 1,308

Answer

The sum of the two integers

x + y

is

1,308

.

By prime factorizing the given GCD (

2^2 \cdot 3^1

) and LCM (

2^4 \cdot 3^3 \cdot 5^2

), the minimum and maximum exponents for each prime factor are determined. The constraint that

x

is not divisible by

9

forces the exponent of

3

in

x

to be

1

, so the exponent of

3

in

y

must be

3

. The constraint that

y

is not divisible by

25

forces the exponent of

5

in

y

to be

0

, so the exponent of

5

in

x

must be

2

. Finally, the condition

x > y

requires the exponent of

2

in

x

to be

4

and in

y

to be

2

. Thus,

x = 1,200

and

y = 108

, giving

x + y = 1,308

.

Step-by-Step Solution

1

Express the GCD and LCM in their prime factorizations.

\gcd(x, y) = 12 = 2^2 \cdot 3^1 \cdot 5^0

and

\text{lcm}(x, y) = 10,800 = 2^4 \cdot 3^3 \cdot 5^2

.

Decomposing into prime factors allows direct determination of the minimum and maximum powers of each prime factor present in

x

and

y

.

2

Determine the prime exponents for

x

and

y

using the given divisibility constraints.

For prime factor

3

:

\min(b_1, b_2) = 1

and

\max(b_1, b_2) = 3

. Since

x

is not divisible by

9 = 3^2

,

b_1 = 1

, which forces

b_2 = 3

. For prime factor

5

:

\min(c_1, c_2) = 0

and

\max(c_1, c_2) = 2

. Since

y

is not divisible by

25 = 5^2

,

c_2 < 2

, which forces

c_1 = 2

and

c_2 = 0

.

The GCD gives the minimum exponent of each prime factor across both numbers, while the LCM gives the maximum exponent.

3

Apply the condition

x > y

to assign the powers of

2

.

The exponents for

2

must be

\{2, 4\}

. If

x

takes exponent

4

and

y

takes exponent

2

,

x = 2^4 \cdot 3^1 \cdot 5^2 = 1,200

and

y = 2^2 \cdot 3^3 \cdot 5^0 = 108

. Since

1,200 > 108

, this satisfies

x > y

.

If

x

took exponent

2

and

y

took exponent

4

, then

x = 300

and

y = 432

, violating

x > y

.

4

Calculate

x + y

.

x + y = 1,200 + 108 = 1,308

.

Adding the uniquely determined values of

x

and

y

gives the final requested sum.

Key Concept

Prime factor exponent min/max rules for GCD and LCM:

\gcd(x,y)

takes the minimum exponent of each prime factor, while

\text{lcm}(x,y)

takes the maximum exponent.

Estimated Time:2m 30s

Question 8Question →

For distinct prime numbers $p$ and $q$ , two positive integers are defined as $a = p^3 q^2$ and $b = p^2 q^4$ . What is the ratio of the least common multiple of $a$ and $b$ to the greatest common divisor of $a$ and $b$ ?

p q^2

p^3 q^4

p^2 q^2

p^5 q^6

p q

Show answer & explanation

Answer: $p q^2$

Answer

p q^2

The greatest common divisor of

a = p^3 q^2

and

b = p^2 q^4

is

p^2 q^2

by taking the minimum exponent for each prime factor. The least common multiple is

p^3 q^4

by taking the maximum exponent for each prime factor. Dividing the LCM by the GCD yields

\frac{p^3 q^4}{p^2 q^2} = p q^2

.

Step-by-Step Solution

1

Find the prime factorization representation of the greatest common divisor (GCD) of

a

and

b

.

\text{GCD}(a, b) = p^{\min(3, 2)} q^{\min(2, 4)} = p^2 q^2

The GCD taking prime factorizations uses the minimum power of each common prime factor.

2

Find the prime factorization representation of the least common multiple (LCM) of

a

and

b

.

\text{LCM}(a, b) = p^{\max(3, 2)} q^{\max(2, 4)} = p^3 q^4

The LCM taking prime factorizations uses the maximum power of each prime factor.

3

Compute the ratio of the LCM to the GCD.

\frac{\text{LCM}(a, b)}{\text{GCD}(a, b)} = \frac{p^3 q^4}{p^2 q^2} = p^{3-2} q^{4-2} = p q^2

Dividing exponential terms with the same base requires subtracting their exponents.

Key Concept

Calculating GCD and LCM using prime factor exponent rules and evaluating their ratio

Question 9Question →

For three positive integers $x$ , $y$ , and $z$ , all of whose prime factors belong exclusively to the set $\{2, 3, 5\}$ , their pairwise greatest common divisors are given by $\gcd(x, y) = 60$ , $\gcd(y, z) = 90$ , and $\gcd(x, z) = 150$ . What is the minimum possible value of the sum $x + y + z$ ?

300

465

930

1,350

2,700

Show answer & explanation

Answer: $930$

Answer

The minimum possible value of the sum

x + y + z

is

930

.

Analyzing the prime factorization exponents for each prime factor

p \in \{2, 3, 5\}

establishes minimum lower bounds on exponents. For prime

2

,

\min(x_2, y_2) = 2

forces

x_2 \ge 2

and

y_2 \ge 2

, which in turn forces

z_2 = 1

to satisfy

\min(y_2, z_2) = 1

. Similarly, for prime

3

,

y_3 \ge 2

and

z_3 \ge 2

forces

x_3 = 1

. For prime

5

,

x_5 \ge 2

and

z_5 \ge 2

forces

y_5 = 1

. Evaluating

x = 2^2 \cdot 3^1 \cdot 5^2 = 300

,

y = 2^2 \cdot 3^2 \cdot 5^1 = 180

, and

z = 2^1 \cdot 3^2 \cdot 5^2 = 450

gives

x + y + z = 930

.

Step-by-Step Solution

1

Express the given pairwise GCDs in their prime factorized forms.

\gcd(x,y) = 60 = 2^2 \times 3^1 \times 5^1

\gcd(y,z) = 90 = 2^1 \times 3^2 \times 5^1

\gcd(x,z) = 150 = 2^1 \times 3^1 \times 5^2

The exponent of any prime

p

in

\gcd(a,b)

is

\min(a_p, b_p)

.

2

Determine the minimum required prime exponents for prime

2

.

\min(x_2, y_2) = 2

,

\min(y_2, z_2) = 1

,

\min(x_2, z_2) = 1 \implies x_2 = 2, y_2 = 2, z_2 = 1

Since

\min(x_2, y_2) = 2

, both

x_2 \ge 2

and

y_2 \ge 2

. To satisfy

\min(y_2, z_2) = 1

, we must have

z_2 = 1

. The minimal exponents are

x_2=2, y_2=2, z_2=1

.

3

Determine the minimum required prime exponents for prime

3

.

\min(x_3, y_3) = 1

,

\min(y_3, z_3) = 2

,

\min(x_3, z_3) = 1 \implies x_3 = 1, y_3 = 2, z_3 = 2

Since

\min(y_3, z_3) = 2

, both

y_3 \ge 2

and

z_3 \ge 2

. To satisfy

\min(x_3, y_3) = 1

, we must have

x_3 = 1

. The minimal exponents are

x_3=1, y_3=2, z_3=2

.

4

Determine the minimum required prime exponents for prime

5

.

\min(x_5, y_5) = 1

,

\min(y_5, z_5) = 1

,

\min(x_5, z_5) = 2 \implies x_5 = 2, y_5 = 1, z_5 = 2

Since

\min(x_5, z_5) = 2

, both

x_5 \ge 2

and

z_5 \ge 2

. To satisfy

\min(x_5, y_5) = 1

, we must have

y_5 = 1

. The minimal exponents are

x_5=2, y_5=1, z_5=2

.

5

Calculate the values of

x

,

y

, and

z

and find their sum.

x = 2^2 \times 3^1 \times 5^2 = 300

y = 2^2 \times 3^2 \times 5^1 = 180

z = 2^1 \times 3^2 \times 5^2 = 450

x + y + z = 300 + 180 + 450 = 930

Summing the minimal values yields the required minimum total.

Key Concept

Finding integers from pairwise GCD conditions using prime factor exponent minimums:

\text{v}_p(\gcd(a,b)) = \min(\text{v}_p(a), \text{v}_p(b))

.

Estimated Time:2m 30s

Question 10Question →

Three automated security beacons flash at regular intervals of $18$ seconds, $24$ seconds, and $42$ seconds, respectively. If all three beacons flash simultaneously at 8:00:00 AM, how many times will all three beacons flash simultaneously between 8:01:00 AM and 9:00:00 AM, inclusive?

Show answer & explanation

Answer: 7

Answer

7

The least common multiple of 18, 24, and 42 is 504 seconds. The timeframe between 8:01:00 AM and 9:00:00 AM inclusive represents elapsed times from 60 seconds to 3600 seconds after 8:00:00 AM. Dividing 3600 by 504 gives 7 full periods (3528 seconds), all of which are greater than 60 seconds. Therefore, the beacons flash simultaneously 7 times within the specified period.

Step-by-Step Solution

1

Find the Least Common Multiple (LCM) of the three flash intervals.

LCM(18, 24, 42) = 504 seconds

The beacons flash simultaneously at time intervals that are integer multiples of the LCM of their individual cycle times.

2

Convert the target time interval (8:01:00 AM to 9:00:00 AM) into seconds after the initial flash at 8:00:00 AM (t = 0).

Range is from t = 60 seconds to t = 3600 seconds

8:01:00 AM is 60 seconds after 8:00:00 AM, and 1 hour (9:00:00 AM) equals 3600 seconds after 8:00:00 AM.

3

Determine the number of positive multiples of 504 within the interval [60, 3600].

7 multiples (504, 1008, 1512, 2016, 2520, 3024, 3528)

Dividing 3600 by 504 gives 7 with a remainder of 72. Since the first positive multiple (504) is greater than 60, all 7 multiples fall strictly within the specified window.

Key Concept

Application of Least Common Multiple (LCM) to periodic events

Question 11Question →

Two positive integers $m$ and $n$ satisfy $m < n$ . Their greatest common divisor is $18$ and their least common multiple is $1,080$ . If $m$ is not divisible by $27$ and $n$ is not divisible by $5$ , what is the value of $n - m$ ?

Show answer & explanation

Answer: 126

Answer

The value of

n - m

is

126

.

By writing

m = 18a

and

n = 18b

with

\text{GCD}(a,b) = 1

, we find

a \cdot b = 60

. Evaluating all coprime factor pairs

(a, b)

shows that only

(5, 12)

satisfies all constraints (

m = 90

is not a multiple of

27

, and

n = 216

is not a multiple of

5

). The difference is

216 - 90 = 126

.

Step-by-Step Solution

1

Relate GCD, LCM, and coprime factors.

Let

m = 18a

and

n = 18b

, where

\text{GCD}(a, b) = 1

and

a < b

. Then

a \cdot b = \frac{1080}{18} = 60

.

The product of two positive integers equals the product of their GCD and LCM.

2

Determine all coprime factor pairs of

60

.

The coprime pairs

(a, b)

with

a < b

such that

a \cdot b = 60

are

(1, 60)

,

(3, 20)

,

(4, 15)

, and

(5, 12)

.

Since

\text{GCD}(a, b) = 1

, prime factors of

60 = 2^2 \cdot 3 \cdot 5

cannot be shared between

a

and

b

.

3

Apply the given constraints to eliminate invalid pairs.

The pair

(5, 12)

is the only pair satisfying both conditions:

m = 90

is not divisible by

27

, and

n = 216

is not divisible by

5

.

Pairs

(1,60)

and

(4,15)

yield

n

divisible by

5

; pair

(3,20)

yields

m=54

which is divisible by

27

.

4

Compute the final difference

n - m

.

n - m = 216 - 90 = 126

.

Subtract

m

from

n

using the valid values found.

Key Concept

Properties of GCD and LCM, prime factorization, and coprime factor pairs

Estimated Time:2m 0s

Question 12Question →

For positive integers $a$ , $b$ , and $c$ , let $x = 2^a \times 3^3 \times 5^b$ and $y = 2^3 \times 3^c \times 5^1$ . If $\text{GCD}(x, y) = 360$ and $\text{LCM}(x, y) = 270,000$ , what is the value of $a + b + c$ ?

8

9

10

11

12

Show answer & explanation

Answer: 10

Answer

10

First, express the given GCD and LCM in prime factor form:

360 = 2^3 \times 3^2 \times 5^1

and

270,000 = 2^4 \times 3^3 \times 5^4

. For any two numbers, the exponent of each prime factor in their GCD is the minimum of their individual exponents, while the exponent in their LCM is the maximum. Comparing prime 2:

\max(a, 3) = 4

, so

a = 4

. Comparing prime 3:

\min(3, c) = 2

, so

c = 2

. Comparing prime 5:

\max(b, 1) = 4

, so

b = 4

. Therefore,

a + b + c = 4 + 4 + 2 = 10

.

Step-by-Step Solution

1

Find the prime factorizations of GCD(x, y) and LCM(x, y)

360 = 2^3 × 3^2 × 5^1 and 270,000 = 2^4 × 3^3 × 5^4

Expressing GCD and LCM in prime factor form allows direct comparison of prime exponents.

2

Apply prime exponent rules for GCD (minimum) and LCM (maximum)

For prime 2: min(a, 3) = 3 and max(a, 3) = 4, so a = 4.
For prime 3: min(3, c) = 2 and max(3, c) = 3, so c = 2.
For prime 5: min(b, 1) = 1 and max(b, 1) = 4, so b = 4.

The GCD takes the minimum exponent for each prime factor, while the LCM takes the maximum exponent.

3

Calculate the sum a + b + c

4 + 4 + 2 = 10

Substitute the evaluated exponent values to find the requested total.

Key Concept

GCD and LCM via Prime Factorization Exponents

Estimated Time:1m 30s

Question 13Question →

For three positive integers $a$ , $b$ , and $c$ , the greatest common divisor of any pair among them is $12$ , and the least common multiple of all three integers is $5,040$ . If $a = 60$ , what is the minimum possible value of $b + c$ ?

168

228

300

372

1,020

Show answer & explanation

Answer: $228$

Answer

The minimum possible value of

b + c

is

228

.

The value

228

is correct because prime factor analysis shows

b

and

c

must take exponents

\{4, 2\}

for prime 2,

\{2, 1\}

for prime 3,

\{0, 0\}

for prime 5, and

\{1, 0\}

for prime 7. Combining

2^4 \times 3^2 = 144

and

2^2 \times 3^1 \times 7^1 = 84

satisfies all pairwise GCD and LCM conditions while minimizing the sum to

144 + 84 = 228

.

Step-by-Step Solution

1

Express the given numbers and conditions in prime factorized form.

The pairwise GCD is

12 = 2^2 \times 3^1

. The LCM of

a, b, c

is

5,040 = 2^4 \times 3^2 \times 5^1 \times 7^1

. Given

a = 60 = 2^2 \times 3^1 \times 5^1

.

Prime factorization allows exact determination of the minimum and maximum required exponent for each prime factor across

a, b,

and

c

.

2

Determine the prime factor exponent constraints for

b

and

c

.

For prime factor 2: min exponent is 2, max is 4. Since

a

has

2^2

, exponents for

(b,c)

for factor 2 must be

\{4, 2\}

to minimize sum.
For prime factor 3: min exponent is 1, max is 2. Since

a

has

3^1

, exponents for

(b,c)

for factor 3 must be

\{2, 1\}

.
For prime factor 5: since

\gcd(a,b) = 12

and

\gcd(a,c) = 12

, 5 cannot divide

b

or

c

. Thus exponents for factor 5 are both 0.
For prime factor 7: max exponent is 1 in LCM, but

a

has

7^0

and pairwise GCD has

7^0

, so exactly one of

b

or

c

has

7^1

and the other has

7^0

.

The pairwise GCD dictates the minimum exponent present in all pairs, while the overall LCM dictates the maximum exponent present across the three numbers.

3

Test allocations of exponents to minimize

b + c

.

We must distribute exponents

\{4, 2\}

for 2,

\{2, 1\}

for 3, and

\{1, 0\}

for 7 between

b

and

c

.
Allocation 1:

b = 2^4 \times 3^2 = 144

and

c = 2^2 \times 3^1 \times 7^1 = 84 \implies b + c = 228

.
Allocation 2:

b = 2^4 \times 3^1 = 48

and

c = 2^2 \times 3^2 \times 7^1 = 252 \implies b + c = 300

.
Allocation 3:

b = 2^4 \times 3^1 \times 7^1 = 336

and

c = 2^2 \times 3^2 = 36 \implies b + c = 372

.
Allocation 4:

b = 2^4 \times 3^2 \times 7^1 = 1008

and

c = 2^2 \times 3^1 = 12 \implies b + c = 1020

.

Comparing all valid exponent combinations reveals the minimum sum.

4

Identify the minimum sum.

The minimum sum is

228

.

The smallest sum among all valid combinations is

144 + 84 = 228

.

Key Concept

Prime factor exponent extraction for pairwise GCD and joint LCM of three numbers

Estimated Time:2m 0s

Question 14Question →

Two positive integers $a$ and $b$ are in the ratio $3 : 8$ . If the least common multiple (LCM) of $a$ and $b$ is $360$ , what is the greatest common divisor (GCD) of $a$ and $b$ ?

Show answer & explanation

Answer: 15

Answer

The greatest common divisor of

a

and

b

is 15.

Any two positive integers in the ratio

3 : 8

can be written as

3g

and

8g

, where

g

is their greatest common divisor. Because

3

and

8

are coprime (their GCD is

1

), the least common multiple of

3g

and

8g

is

3 \times 8 \times g = 24g

. Setting

24g = 360

and dividing by

24

yields

g = 15

.

Step-by-Step Solution

1

Represent the two integers using their ratio and their greatest common divisor.

Let

g = \gcd(a, b)

. Then

a = 3g

and

b = 8g

, where

3

and

8

share no common factors other than

1

.

When two numbers are in reduced ratio

p : q

, dividing both by their GCD leaves coprime factors

p

and

q

.

2

Express the LCM of

a

and

b

in terms of

g

.

\text{LCM}(a, b) = 3 \times 8 \times g = 24g.

The LCM of two numbers

p \cdot g

and

q \cdot g

with

\gcd(p, q) = 1

is

p \cdot q \cdot g

.

3

Solve for

g

using the given LCM value of

360

.

24g = 360 \implies g = 15.

Dividing the given LCM by the product of the coprime ratio components yields the GCD.

Key Concept

Relationship between GCD, LCM, and coprime factor ratios of two positive integers

Estimated Time:1m 15s

Question 15Question →

Two positive integers $x$ and $y$ have a greatest common divisor (GCD) of $14$ and a least common multiple (LCM) of $840$ . If $14 < x < y < 200$ and $x$ is not a multiple of $4$ , what is the value of $y - x$ ?

42

98

112

126

238

Show answer & explanation

Answer: $98$

Answer

The value of

y - x

is

98

.

The prime factorizations of

\text{GCD}(x,y)=14=2^1 \times 7^1

and

\text{LCM}(x,y)=840=2^3 \times 3^1 \times 5^1 \times 7^1

require

x

and

y

to split the exponents of

2, 3, 5, 7

. Since

x

is not a multiple of

4

,

x

contains

2^1

and

y

contains

2^3

. Both contain

7^1

. To satisfy

14 < x < y < 200

,

x

must take factor

5

(

x = 70

) and

y

must take factor

3

(

y = 168

). The difference is

168 - 70 = 98

.

Step-by-Step Solution

1

Express the GCD and LCM in prime factorized form.

\text{GCD}(x, y) = 14 = 2^1 \times 3^0 \times 5^0 \times 7^1

and

\text{LCM}(x, y) = 840 = 2^3 \times 3^1 \times 5^1 \times 7^1

.

Prime factorization allows us to analyze the min and max prime exponents shared between

x

and

y

.

2

Determine the distribution of prime factor exponents between

x

and

y

.

For factor

7

: both

x

and

y

must have exponent

1

.
For factor

2

:

\min(a_x, a_y) = 1

and

\max(a_x, a_y) = 3

. Since

x

is not divisible by

4

(

2^2

),

a_x = 1

, which forces

a_y = 3

.
For factors

3

and

5

: one integer receives

3^1

and the other receives

5^1

.

The GCD takes the minimum exponent and the LCM takes the maximum exponent for each prime factor.

3

Test possible assignments of factors

3

and

5

under the given inequalities.

Case 1:

x

gets

3

and

y

gets

5

.

x = 2 \times 7 \times 3 = 42

,

y = 8 \times 7 \times 5 = 280

. This fails

y < 200

.
Case 2:

x

gets

5

and

y

gets

3

.

x = 2 \times 7 \times 5 = 70

,

y = 8 \times 7 \times 3 = 168

. This satisfies

14 < 70 < 168 < 200

.

Only Case 2 satisfies all structural and boundary constraints (

14 < x < y < 200

and

x

not a multiple of

4

).

4

Compute

y - x

.

y - x = 168 - 70 = 98

.

Direct subtraction of the valid integer values.

Key Concept

Prime Factorization Rules for GCD and LCM

Question 16Question →

For a positive integer $N$ , the greatest common divisor of $N$ and $360$ is $120$ , and the least common multiple of $N$ and $450$ is $9000$ . What is the value of $N$ ?

Show answer & explanation

Answer: 3000

Answer

The value of

N

is

3000

.

Prime factorizing

360

,

120

,

450

, and

9000

converts the GCD and LCM requirements into a system of min/max equations for the exponents of

2

,

3

, and

5

. The condition

\gcd(N, 360) = 120

dictates that the exponent of

3

in

N

must be exactly

1

, while the exponent of

2

is at least

3

. The condition

\text{lcm}(N, 450) = 9000

dictates that the exponent of

2

must be exactly

3

and the exponent of

5

must be exactly

3

. Combining these constraints gives

N = 2^3 \times 3^1 \times 5^3 = 3000

.

Step-by-Step Solution

1

Find the prime factorizations of all known numbers

360 = 2^3 \times 3^2 \times 5^1

,

120 = 2^3 \times 3^1 \times 5^1

,

450 = 2^1 \times 3^2 \times 5^2

, and

9000 = 2^3 \times 3^2 \times 5^3

.

Prime factorization allows us to analyze GCD and LCM conditions using exponent minimums and maximums.

2

Apply the GCD exponent rule

\min(\text{exp}_N(p), \text{exp}_A(p)) = \text{exp}_{GCD}(p)

For factor

2

:

\min(a, 3) = 3 \implies a \ge 3

; For factor

3

:

\min(b, 2) = 1 \implies b = 1

; For factor

5

:

\min(c, 1) = 1 \implies c \ge 1

.

The GCD of two numbers takes the minimum exponent for each prime factor.

3

Apply the LCM exponent rule

\max(\text{exp}_N(p), \text{exp}_B(p)) = \text{exp}_{LCM}(p)

For factor

2

:

\max(a, 1) = 3 \implies a = 3

; For factor

5

:

\max(c, 2) = 3 \implies c = 3

. No prime factors greater than

5

exist in

N

.

The LCM of two numbers takes the maximum exponent for each prime factor.

4

Synthesize the exponents and compute

N

N = 2^3 \times 3^1 \times 5^3 = 8 \times 3 \times 125 = 3000

.

Multiplying out the uniquely determined prime factors gives the value of

N

.

Key Concept

Simultaneous prime exponent analysis using GCD (minimum exponents) and LCM (maximum exponents) rules.

Question 17Question →

For two positive integers $x$ and $y$ with $x < y$ , the greatest common divisor is $\text{GCD}(x, y) = 15$ and the least common multiple is $\text{LCM}(x, y) = 9000$ . If $x$ is a multiple of $8$ but not a multiple of $9$ , what is the value of $y - x$ ?

Show answer & explanation

Answer: 1005

Answer

1005

By writing

x = 15a

and

y = 15b

with

\text{GCD}(a, b) = 1

, we derive

a \cdot b = \frac{9000}{15} = 600

. Prime factorizing

600 = 8 \times 3 \times 25

yields four coprime pairs

(a, b)

with

a < b

:

(1, 600)

,

(3, 200)

,

(8, 75)

, and

(24, 25)

. These yield candidate values for

x

of

15

,

45

,

120

, and

360

, respectively. Checking the divisibility conditions,

15

and

45

are not multiples of

8

, while

360

is a multiple of

9

. The only value of

x

that is a multiple of

8

and not a multiple of

9

is

120

(corresponding to

a = 8, b = 75

). Hence

y = 15 \times 75 = 1125

, and

y - x = 1125 - 120 = 1005

.

Step-by-Step Solution

1

Set up the algebraic representation using the GCD

x = 15a

and

y = 15b

, where

\text{GCD}(a, b) = 1

and

a < b

Any two integers can be written as the product of their GCD and coprime factor multipliers.

2

Relate LCM and GCD to find the product of multipliers

a \times b

a \times b = \frac{\text{LCM}(x, y)}{\text{GCD}(x, y)} = \frac{9000}{15} = 600

The product of GCD and LCM equals the product of the numbers:

\text{GCD}(x,y) \times \text{LCM}(x,y) = x \times y = 15a \times 15b = 225ab

.

3

Decompose 600 into coprime component blocks

600 = 2^3 \times 3^1 \times 5^2 = 8 \times 3 \times 25

Since

\text{GCD}(a, b) = 1

, prime powers cannot be split between

a

and

b

.

4

Form all valid candidate pairs

(a, b)

with

a < b

(1, 600)

,

(3, 200)

,

(8, 75)

, and

(24, 25)

There are

2^{3-1} = 4

ways to partition the 3 prime factor blocks into two coprime factors where

a < b

.

5

Apply divisibility constraints to isolate

x

and

y

x = 120

and

y = 1125

Only

x = 15 \times 8 = 120

satisfies being a multiple of 8 without being a multiple of 9.

6

Calculate the target difference

y - x

1125 - 120 = 1005

Subtracting

x

from

y

yields the required value.

Key Concept

Partitioning prime factor powers of LCM/GCD to identify coprime factor multipliers

Question 18Question →

Three automated signal beacons emit flashes at regular time intervals of $x$ , $y$ , and $z$ seconds, respectively, where $x$ , $y$ , and $z$ are positive integers. If $\text{gcd}(x, y) = 18$ , $\text{gcd}(y, z) = 24$ , and $\text{gcd}(x, z) = 30$ , what is the minimum possible value of $\text{lcm}(x, y, z)$ ?

180

360

720

1{}080

12{}960

Show answer & explanation

Answer: $360$

Answer

360

By breaking each given greatest common divisor into its prime factorization, we establish minimum requirements for the exponents of prime factors

2

,

3

, and

5

across

x

,

y

, and

z

. Specifically,

\text{gcd}(y, z) = 24 = 2^3 \times 3

dictates that both

y

and

z

must contain

2^3

, making the maximum exponent of

2

equal to

3

. Similarly,

\text{gcd}(x, y) = 18 = 2 \times 3^2

forces the maximum exponent of

3

to be

2

, and

\text{gcd}(x, z) = 30 = 2 \times 3 \times 5

forces the maximum exponent of

5

to be

1

. Multiplying these prime powers together gives

2^3 \times 3^2 \times 5 = 360

.

Step-by-Step Solution

1

Express the given pairwise greatest common divisors in prime factorized form.

\text{gcd}(x, y) = 18 = 2^1 \times 3^2

,

\text{gcd}(y, z) = 24 = 2^3 \times 3^1

,

\text{gcd}(x, z) = 30 = 2^1 \times 3^1 \times 5^1

.

GCD conditions determine the minimum prime factor exponents across pairs of variables.

2

Analyze the exponents for prime factor

2

.

\min(v_2(x), v_2(y)) = 1

,

\min(v_2(y), v_2(z)) = 3

, and

\min(v_2(x), v_2(z)) = 1

. This implies

v_2(y) \ge 3

and

v_2(z) \ge 3

, while

v_2(x) = 1

. To minimize the LCM, set

v_2(x) = 1

,

v_2(y) = 3

,

v_2(z) = 3

. Thus,

\max(v_2(x), v_2(y), v_2(z)) = 3

.

The exponent of

2

in

\text{lcm}(x, y, z)

is the maximum of the individual exponents of

2

.

3

Analyze the exponents for prime factor

3

.

\min(v_3(x), v_3(y)) = 2

,

\min(v_3(y), v_3(z)) = 1

, and

\min(v_3(x), v_3(z)) = 1

. This implies

v_3(x) \ge 2

and

v_3(y) \ge 2

, while

v_3(z) = 1

. To minimize the LCM, set

v_3(x) = 2

,

v_3(y) = 2

,

v_3(z) = 1

. Thus,

\max(v_3(x), v_3(y), v_3(z)) = 2

.

The exponent of

3

in

\text{lcm}(x, y, z)

is the maximum of the individual exponents of

3

.

4

Analyze the exponents for prime factor

5

.

\min(v_5(x), v_5(y)) = 0

,

\min(v_5(y), v_5(z)) = 0

, and

\min(v_5(x), v_5(z)) = 1

. This requires

v_5(x) \ge 1

and

v_5(z) \ge 1

, while

v_5(y) = 0

. To minimize the LCM, set

v_5(x) = 1

,

v_5(y) = 0

,

v_5(z) = 1

. Thus,

\max(v_5(x), v_5(y), v_5(z)) = 1

.

The exponent of

5

in

\text{lcm}(x, y, z)

is the maximum of the individual exponents of

5

.

5

Calculate the minimum value of

\text{lcm}(x, y, z)

.

\text{lcm}(x, y, z) = 2^3 \times 3^2 \times 5^1 = 8 \times 9 \times 5 = 360

.

No additional prime factors are required to satisfy the conditions, yielding the minimum possible LCM.

Key Concept

Prime Exponent Constraints on Pairwise GCD and LCM

Estimated Time:2m 0s

Question 19Question →

If $m$ and $n$ are positive two-digit integers such that $m < n$ , $\text{GCD}(m, n) = 12$ , and $\text{LCM}(m, n) = 420$ , what is the value of $n - m$ ?

24

36

72

144

408

Show answer & explanation

Answer: $24$

Answer

The value of

n - m

is

24

.

Writing

m = 12x

and

n = 12y

for coprime integers

x < y

gives

\text{LCM}(m, n) = 12xy = 420

, which simplifies to

xy = 35

. The coprime factor pairs of

35

are

(1, 35)

and

(5, 7)

. The pair

(1, 35)

yields

m = 12

and

n = 420

, but

420

is not a two-digit integer. The pair

(5, 7)

gives two-digit integers

m = 60

and

n = 84

. The difference is

84 - 60 = 24

.

Step-by-Step Solution

1

Express

m

and

n

in terms of their GCD.

Let

m = 12x

and

n = 12y

, where

x

and

y

are coprime positive integers with

x < y

.

Factoring out the greatest common divisor

\text{GCD}(m, n) = 12

leaves coprime factors

x

and

y

.

2

Relate GCD and LCM to determine

x \cdot y

.

\text{LCM}(m, n) = 12 \cdot x \cdot y = 420 \implies x \cdot y = 35

.

For integers written as

12x

and

12y

with

\text{GCD}(x,y)=1

, the least common multiple is

12xy

.

3

Determine the valid pair

(x, y)

that satisfies the two-digit constraint.

The coprime factor pairs of

35

with

x < y

are

(1, 35)

and

(5, 7)

. For

(1, 35)

,

m = 12

and

n = 420

(a three-digit number). For

(5, 7)

,

m = 60

and

n = 84

(both are two-digit numbers). Thus,

(x, y) = (5, 7)

.

The problem specifies that both

m

and

n

are two-digit positive integers.

4

Compute

n - m

.

n - m = 84 - 60 = 24

.

Subtracting

m = 60

from

n = 84

gives

24

.

Key Concept

Properties of Greatest Common Divisor (GCD) and Least Common Multiple (LCM)

Question 20Question →

Two positive integers $m$ and $n$ satisfy $\text{GCD}(m, n) = 60$ and $\text{LCM}(m, n) = 75{}600$ . Given that $m$ is divisible by $63$ but not by $189$ , and $n$ is divisible by $400$ , what is the value of $m$ ?

Show answer & explanation

Answer: 1260

Answer

1260

By finding the prime factorizations of the GCD (

2^2 \cdot 3^1 \cdot 5^1

) and LCM (

2^4 \cdot 3^3 \cdot 5^2 \cdot 7^1

), we determine the prime powers for

m

and

n

using

\min

and

\max

rules. The constraint that

n

is divisible by

400 = 2^4 \cdot 5^2

fixes

e_2(n)=4

and

e_5(n)=2

, which forces

e_2(m)=2

and

e_5(m)=1

. The constraint that

m

is divisible by

63 = 3^2 \cdot 7^1

but not

189 = 3^3 \cdot 7^1

fixes

e_3(m)=2

and

e_7(m)=1

. Evaluating

m = 2^2 \cdot 3^2 \cdot 5^1 \cdot 7^1

gives

1{}260

.

Step-by-Step Solution

1

Prime factorize the GCD and LCM

GCD = 2^2 * 3^1 * 5^1 * 7^0 and LCM = 2^4 * 3^3 * 5^2 * 7^1

GCD represents the minimum exponent of each prime shared by m and n, whereas LCM represents the maximum exponent.

2

Determine the prime exponents for m using divisibility conditions

e_2(m) = 2, e_3(m) = 2, e_5(m) = 1, e_7(m) = 1

Divisibility of n by 400 forces e_2(n)=4 and e_5(n)=2, leaving e_2(m)=2 and e_5(m)=1. Divisibility of m by 63 but not 189 fixes e_3(m)=2 and e_7(m)=1.

3

Compute the product of prime powers for m

m = 4 * 9 * 5 * 7 = 1260

Multiplying the determined prime factors yields the exact value of integer m.

Key Concept

Greatest Common Divisor (GCD) and Least Common Multiple (LCM) Prime Exponent Rules

Estimated Time:2m 0s

Greatest Common Divisor (GCD) and Least Common Multiple (LCM)

Answer

Step-by-Step Solution

Key Concept

Common Mistakes

Answer

Step-by-Step Solution

Key Concept

Common Mistakes

Answer

Step-by-Step Solution

Key Concept

Common Mistakes

Answer

Step-by-Step Solution

Key Concept

Common Mistakes

Answer

Step-by-Step Solution

Key Concept

Common Mistakes

Alternative Method

Answer

Step-by-Step Solution

Key Concept

Common Mistakes

Answer

Step-by-Step Solution

Key Concept

Common Mistakes

Answer

Step-by-Step Solution

Key Concept

Common Mistakes

Answer

Step-by-Step Solution

Key Concept

Common Mistakes

Answer

Step-by-Step Solution

Key Concept

Common Mistakes

Answer

Step-by-Step Solution

Key Concept

Common Mistakes

Answer

Step-by-Step Solution

Key Concept

Common Mistakes

Answer

Step-by-Step Solution

Key Concept

Common Mistakes

Answer

Step-by-Step Solution

Key Concept

Common Mistakes

Answer

Step-by-Step Solution

Key Concept

Common Mistakes

Answer

Step-by-Step Solution

Key Concept

Common Mistakes

Answer

Step-by-Step Solution

Key Concept

Common Mistakes

Answer

Step-by-Step Solution

Key Concept

Common Mistakes

Answer

Step-by-Step Solution

Key Concept

Common Mistakes

Answer

Step-by-Step Solution