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

[demonhunter000]

Cho $(a,p)=1$,$(b,p)$=1,$p\in P$:
Cmr:$\sum_{i=1}^{p}\left ( \frac{ai^{2}+bi}{p} \right )=-\left ( \frac{a}{p} \right )$
Trong đó(-) là kí hiệu legendre

Bài viết đã được chỉnh sửa nội dung bởi demonhunter000: 30-12-2012 - 16:46

[nguyenta98]

Cho $(a,p)=1$,$(b,p)$=1,$p\in P$:
Cmr:$\sum_{i=1}^{p}\left ( \frac{ai^{2}+bi}{p} \right )=-\left ( \frac{a}{p} \right )$
Trong đó(-) là kí hiệu legendre

Sai đề, cho $a=3,b=4,p=5$ thì bài toán sai, thực ra ngay từ lúc nhìn vào đề bài đã thấy sai vì cho $i=p$ thì $\left(\dfrac{ai^2+bi}{p}\right)=0$ (do theo kí hiệu legendre) do đó còn lại $i=1,2,3,...,p-1$ khi ấy dễ cm $\left(\dfrac{ai^2+bi}{p}\right)=1,-1$ mà có chẵn số hạng từ $1\Rightarrow p-1$ nên không thể nào ra kết quả là $-\left(\dfrac{a}{p}\right)$ được

[nguyenta98]

Cho $(a,p)=1$,$(b,p)$=1,$p\in P$:
Cmr:$\sum_{i=1}^{p}\left ( \frac{ai^{2}+bi}{p} \right )=-\left ( \frac{a}{p} \right )$
Trong đó(-) là kí hiệu legendre

Cách giải này hơi lằng nhằng, hy vọng nó đúng
Giải như sau:
Bổ đề : $1^k+2^k+3^k+...+(p-1)^k \vdots p$ với $k\neq p-1$
Chứng minh:
$k$ lẻ thì bài toán dễ dàng được cm
$k$ chẵn, gọi $g$ là căn nguyên thủy của $p$ khi ấy $ord_g(p)=p-1$ như vậy $g,g^2,...,g^{p-1}$ lập thành một hệ thặng dư đầy đủ $mod(p)$ (không chia hết cho $p$) giả sử $k \equiv r \pmod{p-1}$
Khi ấy $1^k+2^k+...+(p-1)^k \equiv 1^r+2^r+...+(p-1)^r \equiv (g^1)^r+(g^2)^r+...+(g^{p-1})^r \pmod{p}$
Đặt $g^r=x$ khi ấy cần cm $x^1+x^2+...+x^{p-1} \vdots p$ hay $1+x+x^2+...+x^{p-2} \vdots p$ ta thấy theo Fermat nhỏ $x^{p-1}-1 \vdots p$ mà $x-1=g^r-1 \not \vdots p$ do $r<p-1$ (vì $r$ là số dư của $k$ chia cho $p-1$) mà $p-1$ là số nhỏ nhất thỏa $g^h-1 \vdots p$ nên do đó $g^r-1 \not \vdots p$ như vậy $1+x+x^2+...+x^{p-2} \vdots p$ hay có $đpcm$, bổ đề được giải
$$**********$$
Ta có theo kí hiệu legendre, ta cần cm $\sum_{i=1}^p(ai^2+bi)^{\frac{p-1}{2}} \equiv -a^{\frac{p-1}{2}} \pmod{p}$
Đặt $\frac{p-1}{2}=k$
Do đó cần cm $A=\sum_{i=1}^p(ai^2+bi)^{k}+a^{k}$
Nhận thấy $A=\left(\sum_{i=1}^p(ai^2)^k+a^k\right)+\left(\binom{k}{1}\sum_{i=1}^p(ai^2)^{k-1}(bi)\right)+...+\left(\binom{k}{k-1}\sum_{i=1}^p(ai^2).(bi)^{k-1}\right)+\left(\sum_{i=1}^p.(bi)^k\right)$
Dễ cm do $k\neq p-1$ thì $\left(\sum_{i=1}^p.(bi)^k\right) \vdots p$ theo bổ đề
Ta xét $\binom{k}{i}\sum_{i=1}^p.(ai^2)^{k-i}.(bi)^i=\binom{k}{i}.a^{k-i}.b^i\left(1^{k+i}+2^{k+i}+...+(p-1)^{k+i}\right)$ cũng theo bổ đề suy ra nó chia hết cho $p$ (chú ý $i<\frac{p-1}{2}$ nên $k+i<p-1 \Rightarrow k+i\neq p-1$ nên áp dụng bổ đề cho $1^{k+i}+2^{k+i}+...+(p-1)^{k+i} \vdots p$)
Giờ xét $\left(\sum_{i=1}^p(ai^2)^k+a^k\right) \vdots p$
Hay $a^k(1+1^{2k}+2^{2k}+...+(p-1)^{2k})=a^k(1+1^{p-1}+2^{p-1}+...+(p-1)^{p-1}) \vdots p$ đúng theo Fermat nhỏ
Do đó $\sum_{i=1}^p(ai^2+bi)^{\frac{p-1}{2}} \equiv -a^{\frac{p-1}{2}} \pmod{p}$
Hay $\sum_{i=1}^{p}\left ( \frac{ai^{2}+bi}{p} \right )=-\left ( \frac{a}{p} \right )$ đây là $đpcm$

Bài viết đã được chỉnh sửa nội dung bởi nguyenta98: 01-01-2013 - 10:19

[nguyenta98]

Gọi $g$ là căn nguyên thủy của $p$ khi ấy $ord_g(p)=p-1$ như vậy $g,g^2,...,g^{p-1}$ lập thành một hệ thặng dư đầy đủ $mod(p)$ (không chia hết cho $p$)

Sau đây mình xin nói về căn nguyên thủy, chứng minh sự tồn tại của căn nguyên thủy và cm khi $g$ là căn nguyên thủy modulo $p$ thì $g,g^2,...,g^{p-1}$ lập thành một hệ thặng dư đầy đủ $mod(p)$ (không chia hết cho $p$)
Giải như sau:
1) (sự tồn tại của căn nguyên thủy $mod(p)$ với $p$ nguyên tố)
Bổ đề 1: $p=4k+1$ và $p \in P$ khi ấy tồn tại $x$ nguyên dương sao cho $x^2+1 \vdots p$
Bổ đề 2: $a$ là số chính phương $mod(p)$ khi và chỉ khi $a^{\frac{p-1}{2}} \equiv 1 \pmod{p}$
$$**********$$
$p=2$ hiển nhiên đúng
Ta chỉ xét $p>2$ khi ấy $p$ lẻ
TH1: $\frac{p-1}{2}$ là số lẻ khi ấy chọn $g=p-1$ khi ấy $(p-1)^{\frac{p-1}{2}}+1 \vdots p$ (do $\frac{p-1}{2}$ lẻ)
Lúc này ta có theo Fermat nhỏ $(p-1)^{p-1}-1 \vdots p$ mà $(p-1)^{\frac{p-1}{2}}+1 \vdots p$ do đó $(p-1)^{\frac{p-1}{2}}-1 \not \vdots p$ như vậy gọi $h$ là cấp của $g$ mod $(p)$ khi ấy $h=p-1$ vì ngược lại suy ra $\frac{p-1}{2} \vdots h$ khi ấy $(p-1)^{\frac{p-1}{2}}-1 \vdots p$ mâu thuẫn suy ra $g$ là căn nguyên thủy $mod(p)$
TH2: $\frac{p-1}{2}$ là số chẵn, đặt $\frac{p-1}{2}=2^{k-1}.j$ với $j$ lẻ suy ra $p=2^k.j+1$ với $k-1\geq 2$ vì $k-1=1$ thì $p=4k+1$ với $k$ lẻ khi ấy theo bổ đề 1 tồn tại $x^2+1 \vdots p$ khi ấy theo Fermat nhỏ $x^{p-1}-1 \vdots p$ nên $(x^{\frac{p-1}{2}}-1)(x^{\frac{p-1}{2}}+1) \vdots p$ ta lại thấy $p=4k+1$ nên $\frac{p-1}{2}=2l$ với $l$ lẻ khi ấy $x^{\frac{p-1}{2}}+1=x^{2l}+1=(x^2)^l+1 \vdots x^2+1 \vdots p$ do $l$ lẻ, như vậy suy ra $x^{\frac{p-1}{2}}-1 \not \vdots p$ cm tương tự TH1 suy ra $x$ là căn nguyên thủy $mod(p)$
Như vậy ta chỉ xét $k-1\geq 2$
Theo bổ đề 1, tồn tại $r_1$ sao cho $r_1^2+1 \vdots p$, ta sẽ cm $r_1$ cũng là scp $mod(p)$
Thấy $r_1^2 \equiv -1 \pmod{p} \Rightarrow r_1^{\frac{p-1}{2}} \equiv (-1)^{\frac{p-1}{4}}$
Mà $k-1\geq 2$ nên $\frac{p-1}{4} \vdots 2$ do đó $(-1)^{\frac{p-1}{4}}=1$ như vậy $r_1^{\frac{p-1}{2}} \equiv 1 \pmod{p}$
Như vậy theo bổ đề 2 thì $r_1$ là scp $mod(p)$
Do đó tồn tại $r_2^2 \equiv r_1 \pmod{p}$ hay $r_2^{\frac{p-1}{2}} \equiv r_1^{\frac{p-1}{4}} \pmod{p}$ $(1)$
Lại có từ $r_1^{\frac{p-1}{2}} \equiv 1 \pmod{p}$ ta có $r_1^{\frac{p-1}{4}}-1 \vdots p$ hoặc $r_1^{\frac{p-1}{4}}+1 \vdots p$
Mà $\frac{p-1}{4}$ chẵn (do nếu lẻ thì ta dừng ở $r_1$ là đủ khi ấy cm tương tự TH1 $r_1$ là căn nguyên thủy $mod(p)$) kết hợp với $r_1^2+1 \vdots p$ suy ra $r_1^{\frac{p-1}{4}}-1 \vdots p$ như vậy $r_1^{\frac{p-1}{4}} \equiv 1 \pmod{p}$ $(2)$
Từ $(1)(2)$ suy ra $r_2^{\frac{p-1}{2}} \equiv 1 \pmod{p}$ hay $r_2$ lại là số chính phương $mod(p)$
Quá trình lặp lại chi đến khi số mũ $k$ của $p$ giảm dần khi còn $=0$ thì bài toán kết thúc
Do đó ta hoàn tất cm tồn tại $g$ nguyên dương sao cho $g^{2^{k-1}}+1 \vdots p$ suy ra $g^{2^{k-1}.j}+1 \vdots p$ (do $j$ lẻ)
Hay $g^{\frac{p-1}{2}}+1 \vdots p$ lúc này cm tương tự TH1 suy ra $g$ là căn nguyên thủy $mod(p)$
Vậy bài toán được giải quyết, ta có khẳng định với mọi $p$ nguyên tố tồn tại $g$ là căn nguyên thủy $mod(p)$

2) Hệ quả: $g$ là căn nguyên thủy $mod(p)$ khi ấy $g,g^2,...,g^{p-1}$ lập thành hệ thặng dư đầy đủ $mod(p)$ (không chia hết cho $p$) thật vậy giả sử $g^i \equiv g^j \pmod{p} \Rightarrow g^{i-j}-1 \vdots p$ mà $i,j\le p-1$ do đó $i-j<p-1$ vô lí vì $g$ là căn nguyên thủy $mod(p)$ thì $ord_g(p)=p-1$, hệ quả được cm

Bài viết đã được chỉnh sửa nội dung bởi nguyenta98: 01-01-2013 - 11:19

[nguyenta98]

Gọi $g$ là căn nguyên thủy của $p$ khi ấy $ord_g(p)=p-1$ như vậy $g,g^2,...,g^{p-1}$ lập thành một hệ thặng dư đầy đủ $mod(p)$ (không chia hết cho $p$)

Một cách khác nữa chỉ ra sự tồn tại của căn nguyên thủy $mod(p)$ với $p$ nguyên tố
Bổ đề 1: Xét đa thức $f(x)=a_nx^n+a_{n-1}x^{n-1}+...+a_1x+a_0 \equiv 0 \pmod{p}$ có $\le deg(f(x))=n$ nghiệm
Chứng minh: http://diendantoanho...chia-hết-cho-p/
Bổ đề 2: Xét đa thức $f(x)=x^d-1$ với $d|p-1$ thì có đúng $d$ nghiệm khi $f(x) \equiv 0 \pmod{p}$ với $p$ nguyên tố
Chứng minh:
Đặt $p-1=dk$ suy ra xét $x^{p-1}-1 \equiv 0 \pmod{p}$ theo định lý Fermat nhỏ $x^{p-1}-1 \equiv 0 \pmod{p}$ với mọi $x \equiv (1,2,..,p-1)$ do đó có $p-1$ nghiệm
Mặt khác $x^{p-1}-1=x^{dk}-1=(x^d-1).((x^d)^{k-1}+...+(x^d)^2+(x^d)+1)$
Theo bổ đề 1 thì $g(x)=((x^d)^{k-1}+...+(x^d)^2+(x^d)+1)$ có $\le d(k-1)$ nghiệm
Suy ra $x^d-1$ có $\geq p-1-d(k-1)=d$ nghiệm, mặt khác theo bổ đề 1 suy ra $x^d-1$ có không quá $d$ nghiệm do đó $x^d-1$ có đúng $d$ nghiệm, đây la $đpcm$
$$**********$$
Áp dụng
Với $p=2$ thấy hiển nhiên tồn tại căn nguyên thủy của $2$
Với $p>2$ suy ra $p-1>1$ nên $p-1=q_1^{r_1}.q_2^{r_2}...q_k^{r_k}$
Theo bổ đề 2, phương trình $x^{q_1^{r_1}}-1 \equiv 0 \pmod{p}$ có đúng $q_1^{r_1}$ nghiệm, $x^{q_1^{r_1-1}}-1 \equiv 0 \pmod{p}$ có đúng $q_1^{r_1-1}$ nghiệm do đó số nghiệm mà thỏa mãn $x^{q_1^{r_1}}-1 \equiv 0 \pmod{p}$ mà $x^{q_1^{r_1-1}}-1 \not \equiv 0 \pmod{p}$ là $q_1^{r_1}-q_1^{r_1-1}>0$
Do đó tồn tại $x_1$ sao cho $x_1^{q_1^{r_1}}-1 \vdots p$ mà $x_1^{q_1^{r_1-1}}-1 \vdots p$
Chứng minh tương tự với $q_2,q_3,...,q_k$ tương ứng tồn tại $x_2,x_3,...,x_k$
Khi ấy chọn $g=x_1x_2x_3...x_k$ thì dễ cm $g$ là căn nguyên thủy $mod(p)$ nên có $đpcm$