Divisibility and factorization · Definition

Bézout's identity

elementary number theorydivisibility and factorization

Before you start you need to know

This identity connects the greatest common divisor with integer linear combinations of two numbers. It is a central tool for solving linear Diophantine equations and proving divisibility properties.

Definition

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}\]

If \( d=\gcd(a,b) \), the identity guarantees that \( d \) is the smallest positive integer of the form \( ax+by \). Moreover, every integer of that form is a multiple of \( d \), which follows directly from \( d \) dividing both \( a \) and \( b \).

For \( a=252 \) and \( b=198 \), the Euclidean algorithm gives \( \gcd=18 \). Working backward through the divisions yields \( 18=252\cdot 4-198\cdot 5 \), so \( x=4 \) and \( y=-5 \) is one solution.

A typical mistake is believing the identity requires \( x \) and \( y \) to be positive. The coefficients may be negative or zero, and this confusion leads to discarding valid combinations or wrongly claiming no solutions exist.

Think about it

Why can x and y be negative in the identity?

Because the identity only requires them to be integers, not positive.

Exercises 10

  1. State Bézout's identity for two integers \( a \) and \( b \).
  2. What is the smallest positive integer that can be written as \( 12x+18y \) with \( x,y\in\mathbb{Z} \)?
  3. Give the greatest common divisor of \( 35 \) and \( 14 \) to use in Bézout's identity.
  4. Does Bézout's identity say that \( ax+by \) can equal any integer when \( a \) and \( b \) are coprime?
  5. Which statement about the set \( \{ax+by : x,y\in\mathbb{Z}\} \) is correct?
  6. If \( \gcd(a,b)=d \), which of these equations has an integer solution \( x,y \) for every such \( a \) and \( b \)?
  7. For \( a=30 \) and \( b=12 \), which pair \( (x,y) \) satisfies \( 30x+12y=6 \)?
  8. Can \( 8x+12y \) equal 2 for some integers \( x,y \)?
  9. For \( a=252 \) and \( b=198 \), with \( \gcd=18 \), which pair \( (x,y) \) satisfies \( 252x+198y=18 \)?
  10. If \( 4 \) divides \( ax+by \) for some integers \( x,y \), does it follow that \( 4 \) divides both \( a \) and \( b \)?

References

  • David M. Burton, Elementary Number Theory, 7th edition, McGraw-Hill, 2011. cap. 2
  • Ivan Niven, Herbert S. Zuckerman, Hugh L. Montgomery, An Introduction to the Theory of Numbers, 5th edition, Wiley, 1991. cap. 1