Divisibility, gcd, and Euclidean algorithm - Discrete Math

1. 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?
   Answer: $d$ divides $a - c$ and $\gcd(d, abc) = 1$ 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$.
2. 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?
   Answer: 2 pairs: $(60,105)$ and $(105,60)$ 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.
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$?
   Answer: $(x_0, y_0) = (-1, 1)$ with $x_0^2 + y_0^2 = 2$ 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.
4. 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$?
   Answer: $|T| = 6$ and largest element is $12$ 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.
5. 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?
   Answer: 3 extractions from first number, 4 from second, $\gcd(147, 63) = 21$ 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.
6. 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$?
   Answer: No such $k$ exists since $\gcd(17, 23) = 1$ 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.
7. 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$?
   Answer: 19 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.
8. 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?
   Answer: $p \equiv 1 \pmod{4}$ or $p = 2$ 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.
9. 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:
   Answer: 10 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.

Start this quiz