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$
Chứng minh rằng $a \le \left\lfloor1 + \sqrt{p}\right\rfloor$
#2
Đã gửi 15-05-2016 - 02:19
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
Bài viết đã được chỉnh sửa nội dung bởi lahantaithe99: 15-05-2016 - 08:51
- bangbang1412, nhungvienkimcuong, Element hero Neos và 1 người khác yêu thích
2 người đang xem chủ đề
0 thành viên, 2 khách, 0 thành viên ẩn danh