NWD(13m + 8n, 5m + 3n) = NWD(m, n)
1.
Oznaczmy
NWD(13m + 8n, 5m + 3n)=d
Wtedy
13m+8n=dk
5m+3n=dl
k,l - liczby względnie pierwsze, czyli takie, że NWD(k,l)=1.
Ponadto liczby 13 i 8, oraz 5 i 3 też są względnie pierwsze, zatem
NWD(m,n)=d
2.
Oznaczmy NWD(m,n)=d
Wtedy
m=dk₁
n=dl₁
k₁,l₁ - liczby względnie pierwsze, czyli takie, że NWD(k₁,l₁)=1.
13 i 8, oraz 5 i 3 też są względnie pierwsze, zatem
13m+8n=13dk₁+8dl₁=d(13k₁+8l₁)
5m+3n=5dk₁+3dl₁=d(3k₁+3l₁)
Czyli
NWD(13m+8n,5m+3n)=d
Z 1 i 2
NWD(13m + 8n, 5m + 3n) = NWD(m, n)