Đến nội dung

Hình ảnh

$$3^{\frac{F_{m}-1}{2}} \equiv -1(\mod F_{m})$$

- - - - - hxthanh nguyenta98 perfecstrong

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

#1
dark templar

dark templar

    Kael-Invoker

  • Hiệp sỹ
  • 3788 Bài viết
Bài toán: Ta gọi 1 số là số Fermat khi số đó có dạng:$F_{m}=2^{2^{m}}+1;m \in \mathbb{N^*}$.Hãy chứng mình rằng:
$$F_{m} \in \mathbb{P} \iff 3^{\frac{F_{m}-1}{2}} \equiv -1(\mod F_{m})$$

Bài viết đã được chỉnh sửa nội dung bởi dark templar: 03-11-2012 - 20:16

"Do you still... believe in me ?" Sarah Kerrigan asked Jim Raynor - Starcraft II:Heart Of The Swarm.

#2
nguyenta98

nguyenta98

    Thượng úy

  • Hiệp sỹ
  • 1259 Bài viết

Bài toán: Ta gọi 1 số là số Fermat khi số đó có dạng:$F_{m}=2^{2^{m}}+1;m \in \mathbb{N^*}$.Hãy chứng mình rằng:
$$F_{m} \in \mathbb{P} \iff 3^{\frac{F_{m}-1}{2}} \equiv -1(\mod F_{m})$$

Giải như sau:
$\boxed{1}$ Nếu $F_m=2^{2^m}+1$ nguyên tố, khi ấy suy ra $F_m$ không có dạng $12k\pm1$ do đó $3$ không là số chính phương $mod(F_m)$ do đó $3^{\frac{F_m-1}{2}} \equiv -1 \pmod{F_m}$ đpcm
$\boxed{2}$ Đảo lại, khi $3^{\frac{F_m-1}{2}} \equiv -1 \pmod{F_m} \Rightarrow 3^{F_m-1}-1 \vdots F_m$ $(1)$
Suy ra $3^{2^{2^n}}-1 \vdots F_m$ gọi $h$ là cấp $3$ mod $(F_m)$ khi đó $h|F_m-1=2^{2^n} \Rightarrow h=2^k$ với $k\le 2^n$
Ta thấy ngay $k=2^n$ vì nếu không thì $k\le 2^{n-1} \Rightarrow h|\frac{F_m-1}{2} \Rightarrow 3^{\frac{F_m-1}{2}}-1 \vdots F_m$ mẫu thuẫn $(1)$ do đó $k=2^n$ suy ra cấp của $3$ $mod(F_m)$ là $F_m-1$
Giả sử phản chứng $F_m$ là hợp số
Đặt $F_m=p_1^{a_1}...p_i^{a_i}$ với $p_1,...,p_i$ nguyên tố
Khi đó $\phi(F_m)=\prod(p_i-1).\prod(p_i^{a_i-1})$
Mặt khác $F_m-1$ là cấp của $3$ mod $(F_m)$ do đó $(p_i-1).\prod(p_i^{a_i-1}) \vdots F_m-1$
Tuy nhiên $gcd(F_m-1,p_i)=1$ do đó $\prod(p_i-1) \vdots F_m-1 \Rightarrow \prod(p_i-1)\geq F_m-1=p_1^{a_1}...p_i^{a_i}-1$
Khi ấy buộc $i=1$ vì nếu $i>1$ ta sẽ cm $\prod(p_i-1)<\prod(p_i^{a_i})-1$ với $i>1$
Thấy $i=2$ thì $\prod(p_i-1)=(p_1-1)(p_2-1)$ còn $\prod(p_i^{a_i})-1=p_1p_2-1$ dễ dàng cm $p_1p_2-1>(p_1-1)(p_2-1)$ vì nó tương đương $p_1+p_2>2$ đúng do $p_1,p_2$ nguyên tố
Giả sử đúng đến $i$ ta sẽ cm đúng đến $i+1$
Thật vậy theo GTQN $(p_1-1)(p_2-1)...(p_i-1)<p_1^{a_1}...p_{i}^{a_{i}}-1$ do đó $p_{i+1}.(p_1-1)(p_2-1)...(p_i-1)<p_1^{a_1}...p_{i}^{a_{i}}.p_{i+1}-p_{i+1}$
Lại thấy rõ ràng $p_1^{a_1}...p_{i}^{a_{i}}.p_{i+1}-p_{i+1}<p_1^{a_1}...p_{i+1}^{a_{i+1}}-1$ (do $a_{i+1}\geq 1$)
Và rõ ràng $p_{i+1}.(p_1-1)(p_2-1)...(p_i-1)>(p_{i+1}-1).(p_1-1)(p_2-1)...(p_i-1)$
Suy ra ngay $(p_1-1)(p_2-1)...(p_i-1)<p_1^{a_1}...p_{i+1}^{a_{i+1}}-1$ nên giả thiết quy nạp được cm
Như vậy ta chứng minh được $i>1$ thì bài toán không thỏa do đó $i=1$
Khi ấy $(p_1-1) \vdots p_1^{a_1}-1$ suy ra $a_1=1$ vì nếu $a_1>1$ thì $p_1^{a_1}-1>p_1-1$
Suy ra $F_m-1=p_1-1 \Rightarrow F_m=p_1$ là số nguyên tố, đây chính là $đpcm$
Bài toán được giải quyết hai chiều

Bài viết đã được chỉnh sửa nội dung bởi nguyenta98: 04-11-2012 - 14:12






Được gắn nhãn với một hoặc nhiều trong số những từ khóa sau: hxthanh, nguyenta98, perfecstrong

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

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