Exercise · ZW-BEZOUT-S-IDENTITY-006 · ★★☆ Intermediate
If \( \gcd(a,b)=d \), which of these equations has an integer solution \( x,y \) for every such \( a \) and \( b \)?
Choose one option.
Show answer
- C. \( ax+by=d \)
Explanation
The values reachable by \( ax+by \) are exactly the multiples of \( d \), so \( ax+by=d \) always has an integer solution. The value \( d/2 \) is never a multiple of \( d \), and \( d+1 \) and \( 1 \) fail whenever \( d>1 \).
Review the concept: Bézout's identity
Bézout's identity states that, for integers \( a \) and \( b \) not both zero, there exist integers \( x \) and \( y \) such that \( ax+by=\gcd(a,b) \).
\[ax+by=\gcd(a,b) \text{ for some } x,y\in\mathbb{Z}\]
More practice problems: bézout's identity
- ZW-BEZOUT-S-IDENTITY-001 State Bézout's identity for two integers a and b .
- ZW-BEZOUT-S-IDENTITY-002 What is the smallest positive integer that can be written as 12x+18y with x,y∈ℤ ?
- ZW-BEZOUT-S-IDENTITY-003 Give the greatest common divisor of 35 and 14 to use in Bézout's identity.
- ZW-BEZOUT-S-IDENTITY-004 Does Bézout's identity say that ax+by can equal any integer when a and b are coprime?
- ZW-BEZOUT-S-IDENTITY-005 Which statement about the set \ax+by : x,y∈ℤ\ is correct?
- ZW-BEZOUT-S-IDENTITY-007 For a=30 and b=12 , which pair (x,y) satisfies 30x+12y=6 ?
- ZW-BEZOUT-S-IDENTITY-008 Can 8x+12y equal 2 for some integers x,y ?
- ZW-BEZOUT-S-IDENTITY-009 For a=252 and b=198 , with gcd=18 , which pair (x,y) satisfies 252x+198y=18 ?