introduction

Just a fancy way of saying that the gcd is of the form au + bv

intuition

Show for m ≥ n ≥ 1. $\frac{gcd(m,n)}{m}\begin{pmatrix} m \\ n \end{pmatrix}$, e.g. m = p is prime, 1 ≤ n ≤ p − 1, then $p|

$ (this would mean interesting things like (a + p)n ≡ ap + bp mod p - By Bezouts_lemma, $\frac{gcd(m,n)}{m}\begin{pmatrix} m \\ n \end{pmatrix} = \frac{um+vn}{m} \frac{m!}{n!(m-n)!}$ - = $u mCn + v \frac{m-1}{(n-1)!(m-n)!}$ - = umCn + v(m − 1)C(n − 1) ∈ ℤ

rigour

Let a, b be integers (both not zero). Then there exists integers u,v such that gcd(a, b) = au + bv

[[modulo]]

TODO update tags tags :math:introduction_to_number_theory:introduction_to_abstract_algebra:

backlinks