Bài toán số học N mũ N chia hết cho A bất kỳ
Bài 1 : Cho số tự nhiên A. Tìm số tự nhiên N nhỏ nhất sao cho N N chia hết cho A. Hãy viết chương trình tìm số N đó và xuất ra màn hình. Trong đó A có giá trị từ 1 đến 10 9 . Ví dụ: Nhập A=8, xuất ra N=4. Nhập A=13, xuất ra N=13. Hướng giải quyết: Vì N N chia hết cho A nên N N chia hết cho tất cả các ước nguyên tố của A. Suy ra N chia hết cho tất cả các ước nguyên tố của A. Nếu phân tích A ra thừa số nguyên tố A = p[1] e[1] .p[2] e[2] .p[3] e[3] .p[4] e[4] ...........p[k] e[k] thì N có dạng N = p[1] t[1] .p[2] t[2] .p[3] t[3] .p[4] t[4] ...........p[k] t[k] . Suy ra: N N = p[1] t[1].N .p[2] t[2].N .p[3] t[3].N .p[4] t[4].N ...........p[k] t[k].N chia hết cho A khi và chỉ khi với với ∀ i ∈(1,k) , t[i].N ≥ e[i].