Đến nội dung


Chú ý

Nếu các bạn đăng kí thành viên mà không nhận được email kích hoạt thì hãy kiểm tra thùng thư rác (spam). Nếu không biết cách truy cập vào thùng thư rác thì các bạn chịu khó Google hoặc đăng câu hỏi vào mục Hướng dẫn - Trợ giúp để thành viên khác có thể hỗ trợ.


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ó 5 trả lời

#1 thanhdotk14

thanhdotk14

    Thượng sĩ

  • Thành viên
  • 268 Bài viết
  • Giới tính:Nam
  • Đến từ:Trường THPT chuyên Lê Quý Đôn-Bình Định

Đã gửi 28-04-2013 - 22:42

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 trị
  • 1319 Bài viết
  • Giới tính:Nam

Đã gửi 29-04-2013 - 13:52



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 Zz Isaac Newton Zz: 30-10-2019 - 14:00

$$n! \sim \sqrt{2\pi n} \left(\dfrac{n}{e}\right)^n$$

 

“We can only see a short distance ahead, but we can see plenty there that needs to be done.” - Alan Turing


#3 Secrets In Inequalities VP

Secrets In Inequalities VP

    Sĩ quan

  • Thành viên
  • 309 Bài viết
  • Giới tính:Nam
  • Đến từ:Chuyên Vĩnh Phúc
  • Sở thích:Xem phim.

Đã gửi 29-04-2013 - 13:53

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
  • Giới tính:Nam
  • Đến từ:nơi không tồn tại
  • Sở thích:học toán

Đã gửi 26-05-2016 - 21:57

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 trị
  • 1319 Bài viết
  • Giới tính:Nam

Đã gửi 27-05-2016 - 10:26

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.


$$n! \sim \sqrt{2\pi n} \left(\dfrac{n}{e}\right)^n$$

 

“We can only see a short distance ahead, but we can see plenty there that needs to be done.” - Alan Turing


#6 cuongmkmtpgoldfinch

cuongmkmtpgoldfinch

    Lính mới

  • Thành viên mới
  • 1 Bài viết

Đã gửi 05-05-2020 - 19:19

anh chị có chứng minh định lý zsigmondy sơ cấp ko ạ, 






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

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