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

[19kvh97]

Cho $n$ là số nguyên dương lẻ và lớn hơn $1$. Chứng minh rằng với mọi số $a=2^k+1$ với $k$ là số nguyên dương thì 

$a^n-1$ không chia hết cho $n$

[shinichigl]

Cho $n$ là số nguyên dương lẻ và lớn hơn $1$. Chứng minh rằng với mọi số $a=2^k+1$ với $k$ là số nguyên dương thì 

$a^n-1$ không chia hết cho $n$

ch: chia hết cho; kch: không chia hết cho.

Giả sử $n$ là số nguyên dương lẻ nhỏ nhất thõa mãn $a^{n}-1$ ch $n$.

Nếu $\left ( a;n \right )=f>1$ thì $a^{n}-1$ kch $f$. Suy ra $a^{n}-1$ kch $n$.

Vậy $\left ( a;n \right )=1$. Theo tiêu chuẩn Euler ta có $a^{\varphi \left ( n \right )}-1$ ch $n$.

Mặt khác $\left (a^{n}-1;a^{\varphi \left ( n \right )}-1  \right )=a^{d}-1$, với $\left ( n;\varphi \left ( n \right ) \right )=d$.

Từ đó $a^{d}-1$ ch $n$. Nếu $d=1$ thì $a-1=2^{k}$ kch $n$ (do $n$ là số lẻ).

Vậy $d>1$. Suy ra $a^{d}-1$ ch $d$ (do $\left ( n;\varphi \left ( n \right ) \right )=d$).

Do $\left ( n;\varphi \left ( n \right ) \right )=d$ nên $1<d\leq \varphi \left ( n \right )<n$

Điều này vô lý với định nghĩa $n$ ban đầu.

Vậy $a^{n}-1$ kch $n$

Chú ý $\left ( a^{m}-1;a^{n}-1 \right )=a^{d}-1$, với $d=\left ( m;n \right )$

Thật vậy,

Giả sử $m>n$ và $m=qn+r$.

Ta có $\left ( a^{m}-1;a^{n}-1 \right )=\left ( a^{qn}-1+a^{qn}\left ( a^{r}-1 \right );a^{n}-1 \right )=\left ( a^{r}-1;a^{n}-1 \right )$

(do $a^{m}-1$ và $a^{n}-1$ kch $a$).

Từ đó ta có $\left ( m;n \right )=\left ( n;r \right )\Leftrightarrow \left ( a^{m}-1;a^{n}-1 \right )=\left ( a^{n}-1;a^{r}-1 \right )$.

Vậy theo thuật chia Euclide thì ta có điều phải chứng minh.

Bài viết đã được chỉnh sửa nội dung bởi shinichigl: 24-02-2015 - 14:43

[cachuoi]

Bài này không cần quá phức tạp gọi p là ước nguyên tố bé nhất của n
Suy ra p/a^n-1 đặt h =ord_a(p)
Nếu (a;p) khác 1 thì suy ra p/a suy ra ngay vô lý nên (a;p)=1
Suy ra h/(p-1)
h/n
Vậy h=1 suy ra p/ a-1 suy ra p=2 vô lý suy ra đpcm