Đến nội dung

Hình ảnh

$\prod_{i=1}^{p}(i^{2}+i+1) \equiv 3 (mod p)$

- - - - -

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

#1
halloffame

halloffame

    Thiếu úy

  • Điều hành viên OLYMPIC
  • 522 Bài viết

Cho $p$ là số nguyên tố chia $3$ dư $2.$ Chứng minh $\prod_{i=1}^{p}(i^{2}+i+1) \equiv 3 (mod p).$


Bài viết đã được chỉnh sửa nội dung bởi halloffame: 07-03-2016 - 22:35

Sự học như con thuyền ngược dòng nước, không tiến ắt phải lùi.


#2
Ego

Ego

    Thượng sĩ

  • Điều hành viên OLYMPIC
  • 296 Bài viết

$p = 2$ là tầm thường. Xét $p \ge 3$:
Theo định lý Fermat, $4^{p} \equiv 4\pmod{p}$.
Do đó ta cần chứng minh $\prod_{i = 1}^{p}4(i^{2} + i + 1) \equiv 12\pmod{p}$
Hay $\prod_{i = 1}^{p}[(2i + 1)^{2} + 3] \equiv 12\pmod{p}$
Do $\text{gcd}(p, 2) = 1$ nên $\{2j + 1\}\;\; j = \overline{1, p}$ lập thành một hệ thặng dư đầy đủ modulo $p$.
Vậy ta cần chứng minh $\prod_{i = 1}^{p}(i^{2} + 3) \equiv 12 \pmod{p} (i)$
Với mọi $i, j = \overline{1, p - 1}$ thì $i^{2} + 3 \equiv j^{2} + 3\pmod{p} \iff i \equiv \pm j\pmod{p}$
$(i) \iff \left[\prod_{i = 1}^{\frac{p - 1}{2}}(i^{2} + 3)\right]^{2} \equiv 4\pmod{p}$
Xét $P(x) = \prod_{i = 1}^{\frac{p - 1}{2}}[x - (i^{2} + 3)] - \left((x - 3)^{\frac{p - 1}{2}} - 1\right)$ có bậc bé hơn $\frac{p - 1}{2}$ và nhận $i^{2} + 3$ làm nghiệm $\forall i = \overline{1, \frac{p - 1}{2}}$ nên theo định lý Lagrange thì $P(x) \equiv 0\pmod{p} \; \forall x \in \mathbb{Z}$ (lưu ý các nghiệm ta đã khác nhau theo modulo $p$ nên khẳng định của định lý Lagrange sẽ đúng)
So sánh hệ số thấp nhất của đa thức cho ta $\prod_{i = 1}^{\frac{p - 1}{2}}(i^{2} + 3) \equiv (-3)^{\frac{p - 1}{2}} - 1\pmod{p}$
Do $\left(\frac{-3}{p}\right) = -1$ nên $(-3)^{\frac{p - 1}{2}} \equiv -1\pmod{p}$.
Điều này dẫn đến $\prod_{i = 1}^{\frac{p - 1}{2}}(i^{2} + 3) \equiv -2\pmod{p} \implies \left[\prod_{i = 1}^{\frac{p - 1}{2}}(i^{2} + 3)\right]^{2} \equiv 4\pmod{p}$
Xong. $\bigstar$.
 


Bài viết đã được chỉnh sửa nội dung bởi Ego: 07-03-2016 - 23:52


#3
lahantaithe99

lahantaithe99

    Trung úy

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

Với modulo $3$ có cách giải nhẹ nhàng hơn. Cách giải sử dụng định lý Lagrange sử dụng tốt cho nhiều trường hợp

Bổ đề: Với $a,b\in\mathbb{N}$,$p\nmid a,b$ thỏa mãn $p=3k+2$ nguyên tố thì nếu $a\equiv b\pmod p\Leftrightarrow a^3\equiv b^3\pmod p$

Chứng minh:

Chiều thuận hiển nhiên đúng. Ta chứng minh chiều đảo. Áp dụng định lý Fermat nhỏ thì $a^{3k+1}-b^{3k+1}\equiv 0\pmod p$ $\Leftrightarrow a(a^{3k}-b^{3k})+b^{3k}(a-b)\equiv 0\pmod p$

Vì $a^3-b^3\equiv 0\pmod p$ nên $b^{3k}(a-b)\equiv 0\pmod p$, $(b,p)=1$ nên $(a\equiv b\pmod p$

Quay trở lại bài toán

 $P=\prod ^{p}_{i=1}(i^2+i+1)=3\prod ^{p}_{i=2}\frac{i^3-1}{i-1}$

Xét tập $\left \{ 2^3-1, 3^3-1,...,p^3-1 \right \}$. Nếu tập này không phải hệ thặng dư thu gọn thì tồn tại $x_i,x_j\in\overline{2,p}$  sao cho $x_i^3\equiv x_j^3\pmod p\Leftrightarrow x_i\equiv x_j\pmod p$. Dễ thấy vô lý

Suy ra $(2^3-1)(3^3-1)...(p^3-1)\equiv (2-1)(3-1)...(p-1)=(p-1)!\pmod p$

$\Rightarrow P\equiv 3\pmod p$


Bài viết đã được chỉnh sửa nội dung bởi lahantaithe99: 10-03-2016 - 23:16





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

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