Chủ đề này có 1 trả lời

[eLcouQTai]

Với m, n là các số nguyên dương, và a là số nguyên dương khác 1 thì $gcd(a^{m}-1,a^{n}-1)=a^{gcd(m,n)}-1$

[nuhoangbanggia]

Giả sử d=(m,n) và d'=(a^{m}-1,a^{n}-1). Đặt m=d.m_{1},n=dn_{1}  ta có:

           a^{m}-1=(a^{d})^{m_{1}}-1 chia hết cho a^{d}-1.

           a^{n}-1=(a^{d})^{n_{1}}-1 chia hết cho a^{d}-1.

 

nên d' chia hết cho a^{d}-1.   (1)

 

Mặt khác vì d=(m,n) nên tồn tại hai số nguyên dương x,y sao cho:  mx-ny=d

 

Vì a^{m}-1 chia hết cho d' và  a^{n}-1 chia hết cho d' nên nên a^{mx}-1 chia hết cho d' và a^{ny}-1 chia hết cho d'.

 

Suy ra a^{mx}-a^{ny}=a^{ny}(a^{d}-1) chia hết cho d' suy ra a^{d}-1chia hêt cho d'    (2)

 

Từ (1) và (2) suy ra đpcm

Bài viết đã được chỉnh sửa nội dung bởi nuhoangbanggia: 24-07-2018 - 17:36