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

[supermember]

Bài Toán :

Cho trước số nguyên dương $n$

Chứng minh rằng với mọi số nguyên dương $k$ ; ta có :

$ \sum_{i=1}^{n} k^{ \gcd(i \ ; \ n)} \equiv 0 \ \ ( \mod n )$

Nguyễn Kim Anh

[phong than]

Bài Toán :

Cho trước số nguyên dương $n$

Chứng minh rằng với mọi số nguyên dương $k$ ; ta có :

$ \sum_{i=1}^{n} k^{ \gcd(i \ ; \ n)} \equiv 0 \ \ ( \mod n )$

Nguyễn Kim Anh

$ \sum_{i=1}^{n} k^{ \gcd(i \ ; \ n)}=\sum_{d|n}{\phi(\dfrac{n}{d}).k^d}$.
Chứng minh bằng quy nạp số ước nguyên tố của $n$.
Khi $n$ có 1 ước nguyên tố dễ dàng kiểm tra.
Giả sử giả thiết đúng với mọi $n$ có $l$ ước nguyên tố.
Xét $n=p_1^{\alpha_1}p_2^{\alpha_2}...p_{l+1}^{\alpha_{l+1}}$.
$\sum_{d|n}{\phi(\dfrac{n}{d}).k^d}=\sum_{i}^{\alpha_j}{\phi(p_j^i)\sum_{d|\dfrac{n}{p_j^{\alpha_j}}}{\phi(\dfrac{n}{dp_j^{\alpha_j}}).(k^{p_j^{\alpha_j-i}})^{d}$.
Áp dụng giả thiết quy nạp suy ra $ \sum_{i=1}^{n} k^{ \gcd(i \ ; \ n)}\vdots \dfrac{n}{p_j^{\alpha_j}}$ với mọi $j$.
$\Rightarrow \sum_{i=1}^{n} k^{ \gcd(i \ ; \ n)}\vdots n$. Ta có điều phải chứng minh.

Bài viết đã được chỉnh sửa nội dung bởi phong than: 31-03-2011 - 20:41