[Bài toán] Ứng dụng định lí phần dư Trung Hoa

By

Bài toán : Cho hai số nguyên dương p,q nguyên tố cùng nhau. Chứng minh rằng tồn tại số nguyên k sao cho (pq-1)^n.k+1 là hợp số với mọi số nguyên dương n.

Lời giải :

Xét hệ đồng dư \left\{\begin{matrix} k\equiv 1\;(mod\;p)\\ k\equiv -1\;(mod\;q) \end{matrix}\right., do gcd(p,q)=1 nên theo định lí phần dư Trung Hoa thì hệ này chắc chắn có nghiệm.

Nếu n chẵn thì (pq-1)^n.k+1\equiv k+1\equiv -1+1=0\;\;(mod\;q), suy ra (pq-1)^n.k+1 là hợp số

Nếu n lẻ thì (pq-1)^n.k+1\equiv -k+1\equiv -1+1=0\;\;(mod\;p), suy ra (pq-1)^n.k+1 là hợp số.

Kết luận : Luôn tồn tại số k sao cho (pq-1)^n.k+1 là hợp số với mọi số nguyên dương n.

One thought on “[Bài toán] Ứng dụng định lí phần dư Trung Hoa”

  1. Pingback: Danh sách tổng hợp các bài toán số học | Juliel's Blog

Leave a comment