Notes of Bezout's Identity

Content

Theorem 1

Let , where , then , must be a multiple of . Especially, , where .

Theorem 2

The equation has integer solution iff .

Proof

Proof to Theorem 1

Let

Apparently, and .

, where

, where

Especially when , .

Proof of Theorem 2

has integer solution

It is not difficult to note that Theorem 2 is a special case of Theorem 1, where .

Proof,

Assume are not co-prime, where .

According to Theorem 1 and the equation, we can deduce that , where and . Since both and are integer, therefore , which forms a contradiction with the proposition we made above.

has integer solution

Omitted, since quite obvious proof by applying Theorem 1.

The application of Bezout’s Identity

1. Extended Euclidean algorithm