Bézout's identity

Bézout's identity

Take two integers a and b and let d be the greatest common factor of a and b (GCF(a,b))

Bézout's identity states that there exists integers x and y such that

ax + by = d

Example: a = 3 and b = 11

Using Euclid's Algorithm

  1. 11 = 3 × 3 + 2
    ⇒ 2 = 11 - 3 × 3
  2. 3 = 1 × 2 + 1
    ⇒ 1 = 3 - 1 × 2
  3. 2 = 2 × 1 + 0
    ⇒ GCF(3, 11) = 1

3x + 11y = 1: Find x and y


Reversing Euclid's Algorithm

  1. 1 = 3 - 1 × 2
  2. 1 = 3 - (11 - 3 × 3)
    = 4 × 3 - 1 × 11

x = 4 and y = -1

4 × 3 - 11 = 1

Alternative

(4 × 3 - 11) - (11 × 3 - 3 × 11) = 1

- 7 × 3 + 2 × 11 = 1

x = -7 and y = 2

2 × 11 - 7 × 3 = 1

Example: a = 12 and b = 20

Using Euclid's Algorithm

  1. 20 = 1 × 12 + 8
    ⇒ 8 = 20 - 1 × 12
  2. 12 = 1 × 8 + 4
    ⇒ 4 = 12 - 1 × 8
  3. 8 = 2 × 4 + 0
    ⇒ GCF(12, 20) = 4

12x + 20y = 4: Find x and y


Reversing Euclid's Algorithm

  1. 4 = 12 - 8
  2. 4 = 12 - (20 - 12)
    = 2 × 12 - 20

x = 2 and y = -1

2 × 12 - 20 = 4

Alternative

(2 × 12 - 20) - (5 × 12 - 3 × 20) = 4

-3 × 12 + 2 × 20 = 4

x = -3 and y = 2

-3 × 12 + 2 × 20 = 4

Euclid's Algorithm finds the greatest common factor of a and b where a is greater than b

The Algorithm

  1. Divide a by b and find the remainder r
  2. Set a = b and b = r
  3. Repeat steps 1 and 2 until r is 0
  4. The greatest common factor is a

The modulo function can be used to find the remainder.

If a divided by b gives a remainder r, then a mod b = r.

Example: a = 124 and b = 72

Find the greatest common factor of 72 and 124

a = 124 and b = 72

  • 124 = 1 × 72 + 52: r = 52
    a = 72, b = 52
  • 72 = 1 × 52 + 20: r = 20
    a = 52, b = 20
  • 52 = 2 × 20 + 12: r = 12
    a = 20, b = 12
  • 20 = 1 × 12 + 8: r = 8
    a = 12, b = 84
  • 12 = 1 × 8 + 4: r = 4
    a = 8, b = 4
  • 8 = 2 × 4 + 0: r = 0
    a = 4, b = 0

r = 0 ⇒ the GCF is 4

Bézout's identity ax + by = 1


Enter a value for a

Enter a value for b