Discrete Math Quiz: Divisibility Gcd And Euclidean Algorithm

9 questions · exam conditions

0:00

Divisibility Gcd And Euclidean AlgorithmQuestion 1 of 9

In implementing a fast gcd algorithm, we use the identity $\gcd(2^a \cdot u, 2^b \cdot v) = 2^{\min(a,b)} \cdot \gcd(u,v)$ where $u,v$ are odd. Given $\gcd(1176, 1008)$ , how many factor-of-2 extractions are needed, and what is the gcd of the resulting odd parts?

4 extractions from first number, 3 from second,

\gcd(73, 126) = 1

3 extractions from first number, 4 from second,

\gcd(147, 63) = 3

3 extractions from first number, 4 from second,

\gcd(147, 63) = 21

2 extractions from first number, 3 from second,

\gcd(294, 126) = 42

← Back to quizzes

Discrete Math Quiz

Discrete Math Quiz: Divisibility Gcd And Euclidean Algorithm

Practice Divisibility Gcd And Euclidean Algorithm in Discrete Math with focused quiz questions that help you check what you know, review explanations, and build confidence with test-style prompts.

What this quiz covers

This quiz focuses on Divisibility Gcd And Euclidean Algorithm, giving you a quick way to practice the rules, question types, and explanations that matter most for Discrete Math.

How to use this quiz

Try each quiz question before looking at the correct answer. Use the explanations to review missed ideas, then come back to similar questions until the pattern feels familiar.

All questions

Question 1

4 extractions from first number, 3 from second, $\gcd(73, 126) = 1$
3 extractions from first number, 4 from second, $\gcd(147, 63) = 3$
3 extractions from first number, 4 from second, $\gcd(147, 63) = 21$ (correct answer)
2 extractions from first number, 3 from second, $\gcd(294, 126) = 42$

Explanation: When you encounter a fast gcd algorithm problem, you're working with the binary GCD method that efficiently handles powers of 2. The key identity

\gcd(2^a \cdot u, 2^b \cdot v) = 2^{\min(a,b)} \cdot \gcd(u,v)

tells us we can factor out powers of 2 separately, then find the gcd of the remaining odd parts. Let's extract factors of 2 from each number. For 1176:

1176 = 2^3 \cdot 147

(since

1176 ÷ 2 = 588

588 ÷ 2 = 294

294 ÷ 2 = 147

, and 147 is odd). For 1008:

1008 = 2^4 \cdot 63

(since

1008 ÷ 2 = 504

504 ÷ 2 = 252

252 ÷ 2 = 126

126 ÷ 2 = 63

, and 63 is odd). So we have 3 extractions from the first number and 4 from the second. Now we need

\gcd(147, 63)

. Using the Euclidean algorithm:

147 = 2 \cdot 63 + 21

, then

63 = 3 \cdot 21 + 0

, so

\gcd(147, 63) = 21

. Answer A has the wrong extraction counts (4 and 3 instead of 3 and 4) and wrong odd parts. Answer B correctly identifies the extractions and odd parts but miscalculates their gcd as 3 instead of 21. Answer D has incorrect extraction counts (2 and 3) and doesn't properly extract all factors of 2. Always double-check your division by 2 until you reach odd numbers, and verify your final gcd calculation using the Euclidean algorithm. The binary method's efficiency comes from handling powers of 2 separately.

Question 2

Consider positive integers $a$ and $b$ where $a \equiv 17 \pmod{25}$ and $b \equiv 23 \pmod{25}$ . If $\gcd(a,b) = 25k$ for some positive integer $k$ , what are the possible values of $k$ , and which value occurs when $a = 42$ and $b = 73$ ?

Possible values: $k \in \{1\}$ , and $k = 1$ for the given $a,b$
Possible values: $k \in \{1, 2\}$ , and $k = 2$ for the given $a,b$
Possible values: $k \in \{1, 5\}$ , and $k = 1$ for the given $a,b$
No such $k$ exists since $\gcd(17, 23) = 1$ (correct answer)

Explanation: We have a = 25m + 17 and b = 25n + 23 for integers m, n. Then gcd(a,b) = gcd(25m + 17, 25n + 23). Using the property that gcd(x + ky, y) = gcd(x, y), we get gcd(25m + 17, 25n + 23) = gcd(25m + 17 - (25n + 23), 25n + 23) = gcd(25(m-n) + 17 - 23, 25n + 23) = gcd(25(m-n) - 6, 25n + 23). We can continue reducing, but more directly: gcd(25m + 17, 25n + 23) divides any linear combination, including gcd(25m + 17 - (25n + 23), 25n + 23) = gcd(25(m-n) - 6, 25n + 23). Since gcd divides both terms, it divides gcd(25(m-n) - 6, 25) and gcd(25(m-n) - 6, 23). Now gcd(25(m-n) - 6, 25) = gcd(-6, 25) = gcd(6, 25) = 1 since gcd(6,25) = 1. So gcd(a,b) must divide gcd(something, 23). But more systematically: gcd(25m + 17, 25n + 23) = gcd(25m + 17, 25n + 23 - 25m - 17) = gcd(25m + 17, 25(n-m) + 6). This equals gcd(25m + 17, 6) since we can subtract multiples of 25(n-m). Now gcd(25m + 17, 6) = gcd(17, 6) = gcd(17, 6) = gcd(5, 6) = 1. So gcd(a,b) = 1, not 25k for any k ≥ 1. Let's verify with a = 42, b = 73: 42 = 25(1) + 17 ✓, 73 = 25(2) + 23 ✓. gcd(42, 73) = gcd(42, 73-42) = gcd(42, 31) = gcd(42-31, 31) = gcd(11, 31) = 1 since 11 and 31 are both prime and distinct. So indeed gcd(a,b) = 1 ≠ 25k for k ≥ 1. Choice D is correct.

Question 3

Consider the Diophantine equation $84x + 90y = \gcd(84, 90)$ . Among all integer solutions $(x,y)$ , let $(x_0, y_0)$ be the solution that minimizes $x_0^2 + y_0^2$ . What are the values of $x_0$ and $y_0$ ?

$(x_0, y_0) = (5, -4)$ with $x_0^2 + y_0^2 = 41$
$(x_0, y_0) = (-1, 1)$ with $x_0^2 + y_0^2 = 2$ (correct answer)
$(x_0, y_0) = (14, -13)$ with $x_0^2 + y_0^2 = 365$
$(x_0, y_0) = (-10, 9)$ with $x_0^2 + y_0^2 = 181$

Explanation: First find gcd(84, 90): 90 = 84(1) + 6, 84 = 6(14) + 0. So gcd(84, 90) = 6. The equation becomes 84x + 90y = 6, or equivalently 14x + 15y = 1 (dividing by 6). Using extended Euclidean algorithm on gcd(14, 15): 15 = 14(1) + 1, 14 = 1(14) + 0. So gcd(14, 15) = 1. Working backwards: 1 = 15 - 14(1). So 14(-1) + 15(1) = 1. Therefore x = -1, y = 1 is a particular solution to 14x + 15y = 1. The general solution is x = -1 + 15t, y = 1 - 14t for integer t. We want to minimize x² + y² = (-1 + 15t)² + (1 - 14t)² = 1 - 30t + 225t² + 1 - 28t + 196t² = 2 - 58t + 421t². Taking derivative: d/dt(2 - 58t + 421t²) = -58 + 842t. Setting to 0: t = 58/842 = 29/421 ≈ 0.069. Since t must be integer, try t = 0 and t = 1. For t = 0: (x,y) = (-1, 1), x² + y² = 1 + 1 = 2. For t = 1: (x,y) = (14, -13), x² + y² = 196 + 169 = 365. For t = -1: (x,y) = (-16, 15), x² + y² = 256 + 225 = 481. The minimum occurs at t = 0, giving (x₀, y₀) = (-1, 1) with x₀² + y₀² = 2. Choice B is correct.

Question 4

If $\gcd(a,b) = 15$ and $\text{lcm}(a,b) = 420$ , and both $a$ and $b$ are positive integers less than 200, how many possible ordered pairs $(a,b)$ exist?

2 pairs: $(60,105)$ and $(105,60)$ (correct answer)
4 pairs: $(30,210), (60,105), (105,60), (210,30)$
2 pairs: $(45,140)$ and $(140,45)$
4 pairs: $(15,420), (30,210), (60,105), (84,75)$

Explanation: Using gcd(a,b) · lcm(a,b) = ab, we get 15 · 420 = 6300 = ab. Since gcd(a,b) = 15, we can write a = 15m and b = 15n where gcd(m,n) = 1. Then 225mn = 6300, so mn = 28. The pairs (m,n) with gcd(m,n) = 1 and mn = 28 are (1,28), (4,7), (7,4), (28,1). This gives (a,b) pairs: (15,420), (60,105), (105,60), (420,15). But we need both a,b < 200, so (15,420) and (420,15) are excluded. Only (60,105) and (105,60) remain. Choice A is correct.

Question 5

Consider the equation $84x + 30y = \gcd(84, 30)$ . Using the extended Euclidean algorithm, one particular solution is $x = x_0, y = y_0$ . If the general solution is given by $x = x_0 + kt, y = y_0 - \ell t$ for integer $t$ , what is the value of $k + \ell$ ?

19 (correct answer)
28
42
56

Explanation: First, find

\gcd(84, 30)

using the Euclidean algorithm:

84 = 2 \cdot 30 + 24

30 = 1 \cdot 24 + 6

24 = 4 \cdot 6 + 0

. So

\gcd(84, 30) = 6

. Now we need to solve

84x + 30y = 6

. Working backwards with the extended Euclidean algorithm:

6 = 30 - 1 \cdot 24 = 30 - 1 \cdot (84 - 2 \cdot 30) = 30 - 84 + 2 \cdot 30 = 3 \cdot 30 - 1 \cdot 84

. So

6 = 84 \cdot (-1) + 30 \cdot 3

, giving us

x_0 = -1, y_0 = 3

. For the general solution of

84x + 30y = 6

, we use the fact that if

(x_0, y_0)

is a particular solution, then the general solution is

x = x_0 + \frac{30}{\gcd(84,30)} \cdot t = x_0 + \frac{30}{6} \cdot t = x_0 + 5t

and

y = y_0 - \frac{84}{\gcd(84,30)} \cdot t = y_0 - \frac{84}{6} \cdot t = y_0 - 14t

. Therefore,

k = 5

and

\ell = 14

, so

k + \ell = 5 + 14 = 19

. The other answer choices represent common errors: 28 would result from using

\frac{84}{3}

instead of

\frac{84}{6}

, 42 would come from adding the original coefficients

\frac{84+30}{\gcd(84,30)} = \frac{114}{6} = 19

(actually this gives 19 too, so this distractor represents a different error), and 56 represents

4 \times 14

from a computational mistake.

Question 6

For positive integers $a$ and $b$ , define $S(a, b) = \{ax + by : x, y \in \mathbb{Z}, ax + by > 0\}$ . If $\gcd(15, 35) = d$ , then the smallest element of $S(15, 35)$ is $d$ , and the second smallest element is:

10 (correct answer)
15
20
25

Explanation: First,

\gcd(15, 35) = \gcd(15, 35) = \gcd(15, 5) = 5

since

35 = 2 \cdot 15 + 5

and

15 = 3 \cdot 5 + 0

. So

d = 5

. By Bézout's identity, there exist integers

x, y

such that

15x + 35y = 5

. Working backwards:

5 = 35 - 2 \cdot 15

, so

15 \cdot (-2) + 35 \cdot 1 = 5

. This confirms that 5 can be written as

15x + 35y

. By the theory of linear Diophantine equations, the set of all integers that can be expressed as

15x + 35y

(for integers

x, y

) is exactly the set of all multiples of

\gcd(15, 35) = 5

. Therefore,

S(15, 35)

consists of all positive multiples of 5, i.e.,

S(15, 35) = \{5, 10, 15, 20, 25, 30, \ldots\}

. The smallest element is indeed

d = 5

, and the second smallest is 10. However, let me double-check that 10 can actually be achieved. We need

15x + 35y = 10

for some integers

x, y

. Dividing by 5:

3x + 7y = 2

. We need a particular solution to this equation. Since

\gcd(3, 7) = 1

, this equation has integer solutions. By inspection or the extended Euclidean algorithm:

3 \cdot 3 + 7 \cdot (-1) = 9 - 7 = 2

. So

x = 3, y = -1

works:

15 \cdot 3 + 35 \cdot (-1) = 45 - 35 = 10

✓. Therefore, the second smallest element is 10. The other choices would correspond to different multiples of 5, but 10 comes immediately after 5 in the sequence of positive multiples of 5.

Question 7

Let $S = \{n \in \mathbb{Z}^+ : \gcd(n, 60) = \gcd(n, 84)\}$ . If $T$ is the set of all possible values of $\gcd(n, 60)$ for $n \in S$ , what is $|T|$ and what is the largest element in $T$ ?

$|T| = 8$ and largest element is $12$
$|T| = 6$ and largest element is $12$ (correct answer)
$|T| = 4$ and largest element is $6$
$|T| = 12$ and largest element is $60$

Explanation: We have 60 = 2² · 3 · 5 and 84 = 2² · 3 · 7. For gcd(n,60) = gcd(n,84), let d = gcd(n,60) = gcd(n,84). Since d divides both 60 and 84, we have d | gcd(60,84) = gcd(2² · 3 · 5, 2² · 3 · 7) = 2² · 3 = 12. So d ∈ {1, 2, 3, 4, 6, 12}. Now we need to check which of these values are actually achievable. If gcd(n,60) = d, then n = dk for some k with gcd(k, 60/d) = 1. Similarly, if gcd(n,84) = d, then n = dm for some m with gcd(m, 84/d) = 1. For both to hold simultaneously, we need gcd(k, 60/d) = gcd(m, 84/d) = 1 and dk = dm, so k = m. This means gcd(k, 60/d) = gcd(k, 84/d) = 1, i.e., gcd(k, lcm(60/d, 84/d)) = 1. We have lcm(60/d, 84/d) = lcm(60,84)/d = (60 · 84)/gcd(60,84)/d = 5040/12/d = 420/d. So we need gcd(k, 420/d) = 1. This is possible for each d ∈ {1,2,3,4,6,12}, so all these values are achievable. Therefore |T| = 6 and the largest element is 12. Choice B is correct.

Question 8

Let $a, b, c$ be positive integers such that $\gcd(a, b) = \gcd(b, c) = \gcd(a, c) = 1$ . If $\gcd(a + b, b + c) = d > 1$ , which of the following statements must be true?

$d$ divides $a - c$ and $\gcd(d, abc) = 1$ (correct answer)
$d$ divides $a + c$ and $d$ is even
$d$ divides $2b$ and $\gcd(d, a) = \gcd(d, c) = 1$
$d$ divides $a - c$ and $d$ divides $b$

Explanation: Since

d = \gcd(a + b, b + c)

, we know

d | (a + b)

and

d | (b + c)

. Therefore,

d | ((a + b) - (b + c)) = d | (a - c)

. Now we need to show

\gcd(d, abc) = 1

. Suppose

p

is a prime that divides both

d

and

abc

. Since

\gcd(a,b) = \gcd(b,c) = \gcd(a,c) = 1

, the prime

p

can divide at most one of

a, b, c

. Case 1:

p | a

but

p \nmid b, c

. Since

d | (a + b)

and

p | d

, we have

p | (a + b)

. Since

p | a

, this means

p | b

, contradicting

p \nmid b

. Case 2:

p | b

but

p \nmid a, c

. Since

d | (a + b)

and

d | (b + c)

, we have

p | (a + b)

and

p | (b + c)

. Since

p | b

, this gives

p | a

and

p | c

, contradicting our assumption. Case 3:

p | c

but

p \nmid a, b

. Similar to Case 1, since

d | (b + c)

and

p | c

, we get

p | b

, contradiction. Therefore, no prime can divide both

d

and

abc

, so

\gcd(d, abc) = 1

. Choice B is wrong because

d

need not be even (consider

a = 2, b = 3, c = 4

where

\gcd(2,3) = \gcd(3,4) = \gcd(2,4) = 1

is false, so this example doesn't work, but we can construct others). Choice C is wrong because

d

divides

(a+b) + (b+c) = a + 2b + c

, but this doesn't imply

d | 2b

. Choice D is wrong because

d

need not divide

b

Question 9

Let $p$ be a prime number and $a, b$ be positive integers such that $p | (a^2 + b^2)$ . If $\gcd(a, p) = \gcd(b, p) = 1$ , then which of the following must be true?

$p \equiv 1 \pmod{4}$ or $p = 2$ (correct answer)
$p \equiv 3 \pmod{4}$ and $p$ is odd
$p$ divides $a - b$ or $p$ divides $a + b$
$a^2 \equiv b^2 \pmod{p}$ and $p > 2$

Explanation: This problem involves the theory of sums of two squares and quadratic residues. We're given that

p | (a^2 + b^2)

where

p

is prime and

\gcd(a, p) = \gcd(b, p) = 1

. From

p | (a^2 + b^2)

, we get

a^2 + b^2 \equiv 0 \pmod{p}

, which means

a^2 \equiv -b^2 \pmod{p}

. Since

\gcd(b, p) = 1

, we can multiply both sides by

(b^{-1})^2

(ab^{-1})^2 \equiv -1 \pmod{p}

. This means

-1

is a quadratic residue modulo

p

. By quadratic reciprocity theory,

-1

is a quadratic residue modulo an odd prime

p

if and only if

p \equiv 1 \pmod{4}

. For

p = 2

a^2 + b^2 \equiv 0 \pmod{2}

means

a^2 + b^2

is even. Since

\gcd(a, 2) = \gcd(b, 2) = 1

, both

a

and

b

are odd, so

a^2 \equiv b^2 \equiv 1 \pmod{2}

. Thus

a^2 + b^2 \equiv 1 + 1 \equiv 0 \pmod{2}

, which works. Therefore, the condition can be satisfied when

p = 2

or when

p \equiv 1 \pmod{4}

. Choice B is incorrect because if

p \equiv 3 \pmod{4}

, then

-1

is not a quadratic residue mod

p

, so the condition cannot be satisfied. Choice C is not necessarily true; for example, take

p = 5, a = 1, b = 2

: we have

1^2 + 2^2 = 5 \equiv 0 \pmod{5}

\gcd(1, 5) = \gcd(2, 5) = 1

, but

5 \nmid (1-2) = -1

and

5 \nmid (1+2) = 3

. Choice D states

a^2 \equiv b^2 \pmod{p}

, but we showed

a^2 \equiv -b^2 \pmod{p}

. These are equivalent only if

2b^2 \equiv 0 \pmod{p}

, which would require

p | 2b^2

. Since

p

is prime and

\gcd(b, p) = 1

, this would require

p = 2

. But choice D also requires

p > 2

, making it impossible.