Bổ đề cơ bản về số học

Bổ đề 1: Cho hai số $b,c \in \mathbb{N}$, đặt $a=(b,c)$. Khi đó tồn tại hai số nguyên $x,y$ sao cho:
$bx+cy=a$.
Chứng minh: gọi M là tập các số nguyên có dạng $bx+cy$, $l=bx_0+cy_0$ là phần tử nguyên dương nhỏ nhất của tập M. Ta sẽ chứng minh $l=a$
 Giả sử $l \nmid b$ ta có $b=lq+r \implies r=b-lq=b(1-x_0q)-cy_0q$ vậy thì $r$ cũng thuộc tập M, nhưng $r<l$ nên mâu thuẫn với cách chọn $l$ , vậy $l \mid b$ tương tự thì $l \mid c$
do đó $l \mid a$ mà dễ thấy được $a \mid l$ do đó $a=l$
Vậy ta có điều phải chứng minh
Bổ đề 2: Cho $u,v$ là hai số tự nhiên thoả $(u,v)=1$
thì $(u^n-v^n,u^m-v^m) = u^{(n,m)}-v^{(n,m)}$ với mọi $n,m \in \mathbb{N}$
Chứng minh :  không mất tính tổng quát giả sử $m>n$
Vì $(u,v)=1 \implies (u^k-v^k,u^{k'} )=1$
do đó $(u^n-v^n,u^m-v^m)=((u^n-v^n)u^{m-n},u^m-v^m) \\  =(u^m-u^{m-n}v^n,u^m-v^m)=((u^{m-n}-v^{m-n})v^n,(u^n-v^n)u^{m-n})=(u^n-v^n,u^{m-n}-v^{m-n})$
để cho gọn ta đặt $A_x=u^x-v^x$ thì $(A_m,A_n)=(A_n,A_{m-n})$
vậy $(A_m,A_n)=(A_r,A_n)$ với $r$ là dư khi chia m cho n
Vậy lập luận tương tự thuật toán Euler ta có $(A_m,A_n)=A_{(m,n)}$, suy ra điều phải chứng minh