Bezout Identity states that
If a and b are integers (not both zero) then there exists integers u and v such that
Gcd(a,b) = au + bv
(Note: u and v are not unique
For example
au + bv = a(u-b) + b(v+a))
this can be used by backtracking the euclid’s equation to find Gcd(a,b) in terms of a b. this can be found in a number of books and is the standard process.
However this can be proved using pigeon hole principle also as below
We know that au is divisible by Gcd(a,b) so au mod b is divisible by Gcd(a,b)
Let gcd(a,b ) = k and
b / gcd(a,b) = t
Now taking an mod b( n from 1 to b/gcd(a,b)-1 that is t -1 ) there are
t-1 remainders
they are kn1, kn2, kn3, so on
there are t-1 remainders and all are divisible by k
no remainder can be zero
because na (n from 1 to t-1) cannot be a product of b.
no 2 remainder can be same if they are then difference is a multiple of b
so there has to a n such that one of the remainder is k
as all t- 1 remainders has to be different and values from 1 to n-1 so one remainder has to be 1
an = k mod b or an + bm = k
(u = n, v= m satisfy the condition)
1 comment:
Thank you very much for your proof. It's much better than the usual "use the Eucldean algorithm" cop-out that's frequently published.
I struggled with the t-1 remainders being unique, even though I realised it must be true. I became completely sure after I realising that it follows from the cancellation law. So sorting that out was very useful to my general understanding of the wonderful world of modulo arithmetic.
Post a Comment