Đến nội dung

Hình ảnh

Chứng minh rằng $2^{\phi (n)}-1$ có các ước số nguyên tố không thuộc tập ${p_1,p_2,...,p_k}$

- - - - -

  • Please log in to reply
Chủ đề này có 4 trả lời

#1
thanhdotk14

thanhdotk14

    Thượng sĩ

  • Thành viên
  • 268 Bài viết

Bài toán: Cho $n$ là một số nguyên dương lẻ, $n\ge 5$ và có các ước số nguyên tố là $p_1,p_2,...,p_k$. Chứng minh rằng $2^{\phi (n)}-1$ có các ước số nguyên tố không thuộc tập ${p_1,p_2,...,p_k}$

 


Bài viết đã được chỉnh sửa nội dung bởi thanhdotk14: 28-04-2013 - 22:42

-----------------------------------------------------

 

:ukliam2: Untitled1_zps6cf4d69d.jpg :ukliam2:


#2
WhjteShadow

WhjteShadow

    Thượng úy

  • Phó Quản lý Toán Ứng dụ
  • 1323 Bài viết


Bài toán: Cho $n$ là một số nguyên dương lẻ, $n\ge 5$ và có các ước số nguyên tố là $p_1,p_2,...,p_k$. Chứng minh rằng $2^{\phi (n)}-1$ có các ước số nguyên tố không thuộc tập ${p_1,p_2,...,p_k}$

Ta phát biểu lại định lý Zsigmondy :

Ch0 $a,b,n\in N$ sa0 cho(a,b)=1 và $n\geq 2$ thì tồn tại số $p$ sao cho $p$ là ước của $a^{n}+b^{n}$ mà không là ước của $a^{k}+b^{k}$ với mọi $k< n$ trừ khi $a=2,b=1,k=3$.

-----------------------------------------------------------------------------------------------

Áp dụng vào bài toán, xét 2 trường hợp :

$\star$ Nếu $n$ là 1 số nguyên tố, $\phi(n)=n-1$, giả sử ngược lại là $2^{n-1}-1$ không có ước nguyên dương ngoài $n$ lúc đó $2^{n-1}-1=n^{x}$ với $x\in \mathbb{N}^{*}$. 

  • Nếu $x$ là số chẵn, ta suy ra $(2^{\frac{n-1}{2}}-n^{\frac{x}{2}})(2^{\frac{n-1}{2}}+n^{\frac{x}{2}})=1$. Hay $(2^{\frac{n-1}{2}}-n^{\frac{x}{2}})=(2^{\frac{n-1}{2}}+n^{\frac{x}{2}})=1\Rightarrow n^{\frac{x}{2}}=0$ (Một điều vô lý!)
  • Nếu $x$ là số chẵn thì $2^{n-1}=n^{x}+1=(n+1)\left[n^{x-1}-n^{x-2}+.....+1\right]$ suy ra $n+1$ có dạng $2^{r}$ với $r\in \mathbb{N}^{*}$ và $r<n-1$ $\Rightarrow \left\{\begin{matrix} 2^{n-1}-1=n^{x}\\ 2^{r}-1=n\end{matrix}\right.$, the0 định lý Zsigmondy dễ dàng suy ra vô lý.

Vậy nếu $n$ là snt thì $2^{n-1}-1$ có ước nguyên dương ngoài $n$.

$\star$ Nếu $n$ là hợp số, ta có thể thấy $\phi(n)>p_1-1,p_2-1,...,p_k-1$, lại the0 định lý Zsigmondy thì $2^{\phi(n)}-1$ có ước nguyên tố mà $2^{p_1-1}-1$ không có, nhưng the0 Fermat nhỏ thì $2^{p_1-1}-1\vdots p_1$ (Do $p_1$ lẻ) vậy nên $2^{\phi(n)}-1$

có ước nguyên dương khác $p_1$. Cứ tương tự như vậy ta rút ra $2^{\phi(n)}-1$

có ước nguyên dương khác $p_1,p_2,...,p_k$ và đây chính là đpcm.

Kết thúc chứng minh $\blacksquare$

-----------

Lại dùng đao to giết gà r` =,=''


Bài viết đã được chỉnh sửa nội dung bởi WhjteShadow: 29-04-2013 - 14:03

“There is no way home, home is the way.” - Thich Nhat Hanh

#3
Secrets In Inequalities VP

Secrets In Inequalities VP

    Sĩ quan

  • Thành viên
  • 309 Bài viết

Bài toán: Cho $n$ là một số nguyên dương lẻ, $n\ge 5$ và có các ước số nguyên tố là $p_1,p_2,...,p_k$. Chứng minh rằng $2^{\phi (n)}-1$ có các ước số nguyên tố không thuộc tập ${p_1,p_2,...,p_k}$

Giả sử $n={p_1}^{s_1}.{p_2}^{s_2}...{p_k}^{s_k}$ suy ra $\phi (n)= \prod_{i=1}^{k}{p_i}^{s_i-1}({p_1}-1)$ suy ra $\phi (n)$ chẵn

$\Rightarrow \phi (n)= 2a\Rightarrow \prod_{i=1}^{k}{p_i}^{s_i-1}({p_1}-1)= 2a$

$\Rightarrow a\vdots ({p_i}-1)\forall i=1,2,...,k\Rightarrow 2^{a}-1\vdots 2^{P_i-1}-1\vdots {P_i}\forall i=1,2,...,k$

Lại có $2^{\phi (n)}-1= 2^{2a}-1= (2^{a}-1)(2^{a}+1)$.

Dễ thấy $gcd(2^{a}-1,2^{a}+1)= 1\Rightarrow gcd(2^a+1,{p_i})= 1\forall i=1,2...,k$ suy ra $2^a-1$ có  ước số nguyên tố không thuộc tập ${p_1,p_2,...,p_k}$

Suy ra $2^{\phi (n)}-1$ có  ước số nguyên tố không thuộc tập ${p_1,p_2,...,p_k}$.

-----------------

@ Đ : Hình như c chưa xét đến TH $n$ là số nguyên tố @@~

@ T.A : Bài t có liên quan gì đến $n$ là snt đâu @@~

@ T.A : mà đề nó cho $n$ có một đống ước nt r mà

@ Đ : Cái đoạn $\Rightarrow a\vdots ({p_i}-1)\forall i=1,2,...,k$ cần là hợp số. V~ cả 1 đống =))


Bài viết đã được chỉnh sửa nội dung bởi WhjteShadow: 29-04-2013 - 14:10


#4
buivantuanpro123

buivantuanpro123

    Hạ sĩ

  • Thành viên
  • 96 Bài viết

Ta phát biểu lại định lý Zsigmondy :

Ch0 $a,b,n\in N$ sa0 cho(a,b)=1 và $n\geq 2$ thì tồn tại số $p$ sao cho $p$ là ước của $a^{n}+b^{n}$ mà không là ước của $a^{k}+b^{k}$ với mọi $k< n$ trừ khi $a=2,b=1,k=3$.

-----------------------------------------------------------------------------------------------

Áp dụng vào bài toán, xét 2 trường hợp :

$\star$ Nếu $n$ là 1 số nguyên tố, $\phi(n)=n-1$, giả sử ngược lại là $2^{n-1}-1$ không có ước nguyên dương ngoài $n$ lúc đó $2^{n-1}-1=n^{x}$ với $x\in \mathbb{N}^{*}$. 

  • Nếu $x$ là số chẵn, ta suy ra $(2^{\frac{n-1}{2}}-n^{\frac{x}{2}})(2^{\frac{n-1}{2}}+n^{\frac{x}{2}})=1$. Hay $(2^{\frac{n-1}{2}}-n^{\frac{x}{2}})=(2^{\frac{n-1}{2}}+n^{\frac{x}{2}})=1\Rightarrow n^{\frac{x}{2}}=0$ (Một điều vô lý!)
  • Nếu $x$ là số chẵn thì $2^{n-1}=n^{x}+1=(n+1)\left[n^{x-1}-n^{x-2}+.....+1\right]$ suy ra $n+1$ có dạng $2^{r}$ với $r\in \mathbb{N}^{*}$ và $r<n-1$ $\Rightarrow \left\{\begin{matrix} 2^{n-1}-1=n^{x}\\ 2^{r}-1=n\end{matrix}\right.$, the0 định lý Zsigmondy dễ dàng suy ra vô lý.

Vậy nếu $n$ là snt thì $2^{n-1}-1$ có ước nguyên dương ngoài $n$.

$\star$ Nếu $n$ là hợp số, ta có thể thấy $\phi(n)>p_1-1,p_2-1,...,p_k-1$, lại the0 định lý Zsigmondy thì $2^{\phi(n)}-1$ có ước nguyên tố mà $2^{p_1-1}-1$ không có, nhưng the0 Fermat nhỏ thì $2^{p_1-1}-1\vdots p_1$ (Do $p_1$ lẻ) vậy nên $2^{\phi(n)}-1$

có ước nguyên dương khác $p_1$. Cứ tương tự như vậy ta rút ra $2^{\phi(n)}-1$

có ước nguyên dương khác $p_1,p_2,...,p_k$ và đây chính là đpcm.

Kết thúc chứng minh $\blacksquare$

-----------

Lại dùng đao to giết gà r` =,=''

bạn chứng minh định lí đó được không



#5
WhjteShadow

WhjteShadow

    Thượng úy

  • Phó Quản lý Toán Ứng dụ
  • 1323 Bài viết

bạn chứng minh định lí đó được không

Bạn có thể search trên mạng cũng có nhiều mà, 

http://users.ugent.b...sigmondy_en.pdf

và 

http://math.stackexc...gmondys-theorem

hầu như nó sử dụng cái cyclotomic polynomials.


“There is no way home, home is the way.” - Thich Nhat Hanh




1 người đang xem chủ đề

0 thành viên, 1 khách, 0 thành viên ẩn danh