Question

[Bên nhau trọn đời]

Cho A=1*2*3*...*29,B=30*31*32*..*58.CMR:A+B chia hết cho 59

Answer 1

[Phát Lê Ngọc]

  Lê Ngọc Phát @ldtv.cskh.phatln Livechat Agent 14:40

Ta có thể viết lại A và B dưới dạng:

 

A = 29!

 

B = (58!/29!) / 30

 

Ta sẽ chứng minh rằng A + B chia hết cho 59 bằng cách chứng minh rằng A ≡ -B (mod 59).

 

Đầu tiên, ta áp dụng định lý Wilson: (p-1)! ≡ -1 (mod p) nếu p là số nguyên tố. Áp dụng định lý này với p = 59, ta có:

 

58! ≡ -1 (mod 59)

 

Ta nhân cả hai vế của phương trình trên với 29!, ta được:

 

29!(58!) ≡ -29! (mod 59)

 

Nhưng ta biết rằng 29! ≡ A (mod 59) và (58!/29!) ≡ B (mod 59), do đó ta có:

 

A * B ≡ -A (mod 59)

 

Thêm A vào cả hai vế của phương trình, ta được:

 

A + A * B ≡ 0 (mod 59)

 

Nhưng ta biết rằng A + B = 29! + (58!/29!) / 30, do đó:

 

A + B ≡ A + A * B (mod 59)

 

Vậy ta kết luận được rằng A + B chia hết cho 59.