Đến nội dung

Hình ảnh

Chứng minh rằng $a \le \left\lfloor1 + \sqrt{p}\right\rfloor$

- - - - -

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

#1
Ego

Ego

    Thượng sĩ

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

Biết rằng $p$ là một số nguyên tố lẻ. Gọi $a$ là số nguyên dương bé nhất nhỏ nhất không chính phương modulo $p$. Chứng minh rằng $a \le \left\lfloor1 + \sqrt{p}\right\rfloor$



#2
lahantaithe99

lahantaithe99

    Trung úy

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

Bài này khá đơn giản

 

Do tính nhỏ nhất của $a$ nên $\left ( \frac{1}{p} \right )=\left ( \frac{2}{p} \right )=...= \left ( \frac{a-1}{p} \right )=1$

Ta đi tìm số $t$ sao cho $\left ( \frac{t}{p} \right )=-1\Leftrightarrow \left ( \frac{ta}{p} \right )=1$ $(1)$

 

Để ý bổ đề sau: Nếu $x,y\in\mathbb{N}$ mà $\frac{x}{y}\not\in\mathbb{Z}$ thì $\frac{x-1}{y}+1\geq \left \lfloor \frac{x}{y} \right \rfloor+1$ 

$\Rightarrow x-1+y\geq \left \lfloor \frac{x}{y} \right \rfloor.y+y$

Chọn $x=p, y=a,\left \lfloor \frac{x}{y} \right \rfloor+1=b\Rightarrow at\leq p+a-1\Rightarrow at-p\leq a-1$. Kết hợp với $(1)$ suy ra $\left ( \frac{at-p}{p} \right )=1\Leftrightarrow 1=\left ( \frac{a}{p} \right )\left ( \frac{t}{p} \right )\Rightarrow \left ( \frac{t}{p} \right )=-1$. 

Trường hợp đẹp nhất là $t=a$. Nếu $a> \left \lfloor \sqrt{p}+1 \right \rfloor$, dễ chứng minh $t< \left \lfloor \sqrt{p} \right \rfloor+1\leq \left \lfloor \sqrt{p}+1 \right \rfloor$, khi đó $t\neq a$, tức là có một số nhỏ hơn $a$ cũng không là scp mod $p$ ( vô lý)

Do đó ta có đpcm

----------------------------------------------------------------------

P.s: Lần thứ ba làm bài này  :oto:


Bài viết đã được chỉnh sửa nội dung bởi lahantaithe99: 15-05-2016 - 08:51





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

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