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

[perfectstrong]

Cho $p$ nguyên tố. $y,k \in \mathbb{N}$ và $y,k$ cố định.
Chứng minh rằng: $\forall n \in \mathbb{N}, \exists x \in \mathbb{N}:x^k+y \vdots p^n$ với $gcd(y,p)=1$

[Karl Heinrich Marx]

$k=2,y=1,p=3$ làm sao tồn tại $x$ đây.

[perfectstrong]

Dạ, anh nghĩ xem nên thêm đk gì vào bài toán để nó chặt hơn

[nguyenta98]

Vấn đề bài này là anh Hân phải thêm câu: biết rằng nó đúng với một vài trường hợp đầu của $n$ sau đó cm đúng với mọi $n$ chứ nếu không thì ta thử ngay trường hợp đầu đã sai thì quy nạp sao được


P/S em đã có một cách làm nhưng chỉ chứng minh được với $gcd(k,p)=1$ hoặc $k$ là số nguyên tố bất kì thôi

Bài viết đã được chỉnh sửa nội dung bởi nguyenta98: 18-06-2012 - 17:28

[Karl Heinrich Marx]

Theo anh thì bài này nên cho thêm điều kiện $gcd(k,p-1)=1$, khi đấy thì $1^k,2^k,..,(p-1)^k$ mới lập thành hệ thặng dư đầy đủ mod $p$. Bước sau có thể qui nạp được thì phải, anh mới chỉ nghĩ ra cách quy nạp nhưng chưa viết ra nên không biết đúng không nữa.

[nguyenta98]

Theo anh thì bài này nên cho thêm điều kiện $gcd(k,p-1)=1$, khi đấy thì $1^k,2^k,..,(p-1)^k$ mới lập thành hệ thặng dư đầy đủ mod $p$. Bước sau có thể qui nạp được thì phải, anh mới chỉ nghĩ ra cách quy nạp nhưng chưa viết ra nên không biết đúng không nữa.

Không cần đâu anh ạ, em có thể chứng minh bài toán cũng đúng ngay cả khi $gcd(k,p-1)\neq 1$ (nhưng tất nhiên vẫn phải có $gcd(k,p)=1$ hoặc $k$ nguyên tố thì em mới làm được

[Karl Heinrich Marx]

Thế em cm dùm anh cái trường hợp $k=2,y=1,p=3$ anh nêu ở trên đi.

[nguyenta98]

Thế em cm dùm anh cái trường hợp $k=2,y=1,p=3$ anh nêu ở trên đi.

Em biết là khi đó nó sai nhưng nếu ta thử cho một ví dụ khác xem sao?
Thí dụ $k=4$ và $y=3$ và $p=7$ xem sao?

Bài viết đã được chỉnh sửa nội dung bởi nguyenta98: 18-06-2012 - 23:02

[Karl Heinrich Marx]

Rõ ràng là chỉ cần $y=1,k=2t$ là sai rồi, vì thế nếu giới hạn của em là $(k,p)=1$ thì em phải giới hạn thâm điều kiện cho $y$. Chỉ cần 1 bài toán sai trong 1 trường hợp thì nó đã sai rồi em ạ. Em thử xem lại lời giải của em và giới hạn thêm điều kiện của $y$ để phù hợp hơn với lời giải của em xem sao.

Bài viết đã được chỉnh sửa nội dung bởi Karl Heinrich Marx: 18-06-2012 - 23:09

[nguyenta98]

Cho $p$ nguyên tố. $y,k \in \mathbb{N}$ và $y,k$ cố định.
Chứng minh rằng: $\forall n \in \mathbb{N}, \exists x \in \mathbb{N}:x^k+y \vdots p^n$ với $gcd(y,p)=1$

Rõ ràng là chỉ cần $y=1,k=2t$ là sai rồi, vì thế nếu giới hạn của em là $(k,p)=1$ thì em phải giới hạn thâm điều kiện cho $y$. Chỉ cần 1 bài toán sai trong 1 trường hợp thì nó đã sai rồi em ạ. Em thử xem lại lời giải của em và giới hạn thêm điều kiện của $y$ để phù hợp hơn với lời giải của em xem sao.

Em sẽ chứng minh bài này đúng với $gcd(k,p)=1$ và $gcd(k,p-1)=1$ (theo ý anh karl)
Giải như sau:
Ta sẽ chứng minh bằng quy nạp
$n=1$ dễ thấy một HĐĐ nên đúng
Giả sử $n$ đúng hay tồn tại $x^k+y \vdots p^n$
Ta sẽ chứng minh $n+1$ cũng đúng hay tồn tại $x_0^k+y \vdots p^{n+1}$
Thật vậy, từ giả thiết quy nạp suy ra $x^k+y=p^n.q$
TH1: $q \vdots p \rightarrow Q.E.D$
TH2: $gcd(q,p)=1$ $(1)$
Khi đó ta chọn $x_0=v.p^n+x$
Do đó $x_0^k+y=(v.p^n+x)^k+y=v^k.p^{nk}+\binom{1}{k}.v^{k-1}.p^{n(k-1)}.x+...+\binom{k-1}{k}.v.p^n.x^{k-1}+(x^k+y)$
Dễ dàng cm $p^{n+1} \mid v^k.p^{nk}+\binom{1}{k}.v^{k-1}.p^{n(k-1)}.x+...\binom{k-2}{k}.v^2.p^{2n}.x^{k-2}$
Do vậy ta xét $\binom{k-1}{k}.v.p^n.x^{k-1}+(x^k+y)=k.v.p^n.x^{k-1}+p^n.q=p^n(k.v.x^{k-1}+q)$
Nhận thấy giả sử $k.x^{k-1} \equiv t \pmod{p}$ mà $gcd(k,p)=1$ và $x^k+y \vdots p \rightarrow gcd(x,p)=1$ (do $gcd(y,p)=1$) suy ra $gcd(t,p)=1$
Do đó $(k.v.x^{k-1}+q) \equiv tv+q \pmod{p}$ mà từ (1) ta đã có $gcd(q,p)=1$
Cho nên luôn tồn tại $v$ thỏa mãn $tv+q \vdots p$
Cho nên bài toán được khẳng đinh với $n+1$

Bài viết đã được chỉnh sửa nội dung bởi nguyenta98: 18-06-2012 - 23:29

[perfectstrong]

Nếu thêm đk như anh Karl nói thì ở $n=1$, sẽ luôn có nghiệm $x$. Do đó, nó sẽ dẫn tới kết quả cần tìm.
Còn nếu không, thì việc có nghiệm $n=1$ hay không, phụ thuộc theo $y$ và $k$.

[Karl Heinrich Marx]

Em sẽ chứng minh bài này đúng với $gcd(k,p)=1$ và $gcd(k,p-1)=1$ (theo ý anh karl)
Giải như sau:
Ta sẽ chứng minh bằng quy nạp
$n=1$ dễ thấy một HĐĐ nên đúng
Giả sử $n$ đúng hay tồn tại $x^k+y \vdots p^n$
Ta sẽ chứng minh $n+1$ cũng đúng hay tồn tại $x_0^k+y \vdots p^{n+1}$
Thật vậy, từ giả thiết quy nạp suy ra $x^k+y=p^n.q$
TH1: $q \vdots p \rightarrow Q.E.D$
TH2: $gcd(q,p)=1$ $(1)$
Khi đó ta chọn $x_0=v.p^n+x$
Do đó $x_0^k+y=(v.p^n+x)^k+y=v^k.p^{nk}+\binom{1}{k}.v^{k-1}.p^{n(k-1)}.x+...+\binom{k-1}{k}.v.p^n.x^{k-1}+(x^k+y)$
Dễ dàng cm $p^{n+1} \mid v^k.p^{nk}+\binom{1}{k}.v^{k-1}.p^{n(k-1)}.x+...\binom{k-2}{k}.v^2.p^{2n}.x^{k-2}$
Do vậy ta xét $\binom{k-1}{k}.v.p^n.x^{k-1}+(x^k+y)=k.v.p^n.x^{k-1}+p^n.q=p^n(k.v.x^{k-1}+q)$
Nhận thấy giả sử $k.x^{k-1} \equiv t \pmod{p}$ mà $gcd(k,p)=1$ và $x^k+y \vdots p \rightarrow gcd(x,p)=1$ (do $gcd(y,p)=1$) suy ra $gcd(t,p)=1$
Do đó $(k.v.x^{k-1}+q) \equiv tv+q \pmod{p}$ mà từ (1) ta đã có $gcd(q,p)=1$
Cho nên luôn tồn tại $v$ thỏa mãn $tv+q \vdots p$
Cho nên bài toán được khẳng đinh với $n+1$

Em làm đúng rồi, cả cách quy nạp giống anh, phần quy nạp nghĩ nghĩ trong đầu nên quên mất đk $(k,p)=1$ thật , bổ sung đk anh với em là chuẩn ^^. Để đúng với $n=1$ chứng minh dùng căn nguyên thủy.

[nguyenta98]

Như vậy chúng ta có một bài toán tổng quát sau

Cho $p$ nguyên tố. $y,k \in \mathbb{N}$ và $y,k$ cố định, với $gcd(k,p)=gcd(k,p-1)=1$
Chứng minh rằng: $\forall n \in \mathbb{N}, \exists x \in \mathbb{N}:x^k+y \vdots p^n$ với $gcd(y,p)=1$

Tuy nhiên với $gcd(k,p)\neq 1$ thì còn nhiều câu hỏi mở xung quanh

Bài viết đã được chỉnh sửa nội dung bởi nguyenta98: 18-06-2012 - 23:50

[The Gunner]

Như vậy chúng ta có một bài toán tổng quát sau

Cho $p$ nguyên tố. $y,k \in \mathbb{N}$ và $y,k$ cố định, với $gcd(k,p)=gcd(k,p-1)=1$
Chứng minh rằng: $\forall n \in \mathbb{N}, \exists x \in \mathbb{N}:x^k+y \vdots p^n$ với $gcd(y,p)=1$

Tuy nhiên với $gcd(k,p)\neq 1$ thì còn nhiều câu hỏi mở xung quanh

Bài toán này thử cho $k=x$ tức là $y$ cố định, $p$ nguyên tố $(y,p)=1$
thì với mọi $n$ tồn tại $x \in \mathbb{N} $ để $x^x+y \vdots p^n$ thì có đúng ko nhỉ

Bài viết đã được chỉnh sửa nội dung bởi The Gunner: 19-06-2012 - 00:15

[Karl Heinrich Marx]

Bài toán này thử cho $k=x$ tức là $y$ cố định, $p$ nguyên tố $(y,p)=1$
thì với mọi $n$ tồn tại $x \in \mathbb{N} $ để $x^x+y \vdots p^n$ thì có đúng ko nhỉ

Lời giải này mình mới nghĩ ra cũng không chắc lắm là đúng.
Ta coi bài ở đầu toppic là một bổ đề. Khi đó với $n=1$ chỉ cần chọn $x$ thỏa hệ đồng dư $x \equiv k (mod p-1), x \equiv x_0 (mod p)$ với $x_0,k$ thỏa mãn $x_0^k+y \vdots p$.
Giả sử đúng đến $n-1$ tức là tồn tại $x$ mà $x^x+y \vdots p^{n-1}$. Từ cách xác định quy nạp ở bài trên thì ta chọn được $x_n=a.p^n+x$ thỏa $x_n^x+y \vdots p^n$ khi đó dễ nhận thấy $x_n \equiv x (mod p^{n-1})$. Và như thế thì hệ thặng dư $X \equiv x (mod p^{n-1}(p-1)),X \equiv x_n (mod p^n)$ có nghiệm. Rõ ràng $X^X+y \vdots p^n$.

[perfectstrong]

Lời giải này mình mới nghĩ ra cũng không chắc lắm là đúng.
Ta coi bài ở đầu toppic là một bổ đề. Khi đó với $n=1$ chỉ cần chọn $x$ thỏa hệ đồng dư $x \equiv k (mod p-1), x \equiv x_0 (mod p)$ với $x_0,k$ thỏa mãn $x_0^k+y \vdots p$.
Giả sử đúng đến $n-1$ tức là tồn tại $x$ mà $x^x+y \vdots p^{n-1}$. Từ cách xác định quy nạp ở bài trên thì ta chọn được $x_n=a.p^n+x$ thỏa $x_n^x+y \vdots p^n$ khi đó dễ nhận thấy $x_n \equiv x (mod p^{n-1})$. Và như thế thì hệ thặng dư $X \equiv x (mod p^{n-1}(p-1)),X \equiv x_n (mod p^n)$ có nghiệm. Rõ ràng $X^X+y \vdots p^n$.

Anh giải thích rõ chỗ cách chọn được không? Tại sao như thế ạ? Định lý thặng dư Trung Hoa em chưa rành lắm

[Karl Heinrich Marx]

Anh giải thích rõ chỗ cách chọn được không? Tại sao như thế ạ? Định lý thặng dư Trung Hoa em chưa rành lắm

Em không rõ cách chọn ở đoạn nào. Định lí thặng dư trung hoa anh nói sơ cho 2 số e tự suy ra với n số tức là với 2 số $m_1,m_2$ và $gcd(m_1,m_2)=a$ thì hệ pt đồng dư $x \equiv a_1 (modm_1),x \equiv a_2 (mod m_2)$ có nghiệm khi và chỉ khi $a_1 \equiv a_2 (mod a)$ và có thể thấy khi $a=1$ thì hệ luôn có nghiệm.

[perfectstrong]

Anh có thể viết rõ lại lời giải hơn không ạ?
Bổ đề:
Cho $p$ nguyên tố. $y,k$ nguyên thỏa $(y;p)=(k;p)=(k-1;p)=1$.
Suy ra, $\forall n \in \mathbb{N}, \exists x \in \mathbb{N}:x^k+y \vdots p^n$

[Karl Heinrich Marx]

thì nếu $x \equiv k (mod p-1),x \equiv x_0 (modp)$ thì đương nhiên ta có: $x^x \equiv x^{k} \equiv x_0^k (mod p)$ vậy thôi chứ có j` đâu. Tương tự cái ở dưới vì $(p-1)p^{n-1}= \phi(p^n)$ nên $X^{X} \equiv X^x (mod p^n)$ mà theo bổ đề thì chọn được $x_n$ để $x_n^x+y \vdots p^n$ và $X \equiv x_n (mod p^n)$ nên $X^X \equiv X^x \equiv x_n^x (mod p)$. Còn điều kiện tồn tại $X$ thì anh đã nêu ra điều kiện có nghiệm của định lí thặng dư ở trên rồi.

Bài viết đã được chỉnh sửa nội dung bởi Karl Heinrich Marx: 19-06-2012 - 21:58

[perfectstrong]

Theo anh thì bài này nên cho thêm điều kiện $gcd(k,p-1)=1$, khi đấy thì $1^k,2^k,..,(p-1)^k$ mới lập thành hệ thặng dư đầy đủ mod $p$. Bước sau có thể qui nạp được thì phải, anh mới chỉ nghĩ ra cách quy nạp nhưng chưa viết ra nên không biết đúng không nữa.

Anh Karl Heinrich Marx chứng minh lại cho em chỗ phần HĐĐ được không ạ?
Bổ đề:
Cho $p$ là số nguyên tố lẻ. $k$ nguyên dương thỏa $(k;p)=(k-1;p)=1$.
Khi đó, $\{ 1^k;2^k;...;(p-1)^k \}$ là HĐĐ mod $p$.