Chúng tỏ rằng với a, b ∈ ℕ thì ƯCLN (a, b) = ƯCLN (5a + 2b, 7a + 3b

Đề bài: Chúng tỏ rằng với a, b ∈ ℕ thì ƯCLN (a, b) = ƯCLN (5a + 2b, 7a + 3b)

Trả lời

Hướng dẫn giải:

Gọi d = ƯCLN (a; b)

Đặt:

a = d.m  ; b = d.n ⇒ (m; n) = 1

5a + 2b = d(5m + 2n)

7a + 3b = d(7m + 3n)

Gọi d’ = ƯCLN (5m + 2n; 7m + 3n)

$\left\{\begin{array}{l}5m+2n⋮d\text{'}\\ 7m+3n⋮d\text{'}\end{array}\right.\Rightarrow \left\{\begin{array}{l}5m+2n⋮d\text{'}\\ 2m+n⋮d\text{'}\end{array}\right.\Rightarrow \left\{\begin{array}{l}5m+2n⋮d\text{'}\\ 4m+2n⋮d\text{'}\end{array}\right.\Rightarrow m⋮d\text{'}$

Từ đó suy ra: 2n ⋮ d’ và 3n ⋮ d’ do đó, n⋮ d’

Do đó, d’ thuộc tập ƯC (m;n)

Mà ƯCLN (m; n) = 1 nên d’ = 1

Do đó, ƯCLN (5m + 2n; 7m + 3n) = 1 ⇒ ƯCLN (5a + 2b; 7a + 3b) = d = ƯCLN (a; b)