đặt $\mathcal{S}=\sum_{i=1008}^{2017}\left \lfloor \frac{2^i}{2017} \right \rfloor-\sum_{i=0}^{1007}\left \lfloor \frac{2^i}{2017} \right \rfloor$ với $\left \lfloor a \right \rfloor$ là số nguyên lớn nhất không vượt quá $a$

Chứng minh rằng $2017.\mathcal{S}$ là số chính phương

(Nguồn: thầy Nguyễn Hồng Lữ)

Spoiler

một bài toán hay với lời giải thú vị

 

Đặt $p=2017$, dễ thấy $p$ là số nguyên tố lẻ và dựa vào tính chất

 

$\left(\frac{2}{p}\right)=(-1)^{\frac{p^2-1}{8}}$

 

ta sẽ có $2$ là số chính phương theo $\mathrm{mod}\; p$, hay $2^{\frac{p-1}{2}} = 1 \;(\mathrm{mod}\; p)$

 

Giả sử $2^i=a_i \;(\mathrm{mod} \; p), \; \forall i=0,\dots,\frac{p-1}{2}-1$, suy ra $2^{i+\frac{p-1}{2}}=a_i \;(\mathrm{mod}\; p), \; \forall i=0,\dots,\frac{p-1}{2}-1$

 

ta suy ra $\sum_{i=0}^{\frac{p-1}{2}-1}\left\lfloor \frac{2^i}{p}\right\rfloor=\sum_{i=0}^{\frac{p-1}{2}-1}\left(\frac{2^i}{p}-\frac{a_i}{p}\right)$

 

Tương tự $\sum_{i=\frac{p-1}{2}}^{p-2}\left\lfloor \frac{2^i}{p}\right\rfloor=\sum_{i=0}^{\frac{p-1}{2}-1}\left(\frac{2^{i+\frac{p-1}{2}}}{p}-\frac{a_i}{p}\right)$

 

Từ các kết quả trên ta có

 

$S=\sum_{i=\frac{p-1}{2}}^{p-2}\left\lfloor \frac{2^i}{p}\right\rfloor-\sum_{i=0}^{\frac{p-1}{2}-1}\left\lfloor \frac{2^i}{p}\right\rfloor=\sum_{i=0}^{\frac{p-1}{2}-1}\left(\frac{2^{i+\frac{p-1}{2}}}{p}-\frac{a_i}{p}\right)-\sum_{i=0}^{\frac{p-1}{2}-1}\left(\frac{2^i}{p}-\frac{a_i}{p}\right)=\frac{\left(2^{\frac{p-1}{2}}-1\right)^2}{p}$

$\rightarrow pS=\left(2^{\frac{p-1}{2}}-1\right)^2$ là số chính phương

Cho 5 điểm trên mặt phẳng sao cho không có 3 điểm nào thẳng hàng. Chứng minh rằng có ít nhất một tứ giác lồi có bốn đỉnh từ năm điểm đã cho.

Giải bài toán với trường hợp n>5

 

Xét bao giác lồi cho 5 điểm đó, xảy ra 3 trường hợp

 

[1] Bao giác lồi là tam giác, gọi tam giác đó là $ABC$, xét 2 điểm còn lại là $D$ và $E$,

điểm $E$ phải nằm 1 trong 3 tam giác $DAB, DBC, DCA$, không mất tính tổng quát, giả sử là tam giác $DAB$. Đường thẳng $CD$ chia mặt phẳng làm 2 nửa, nếu $E$ nằm cùng với $A$ trên 1 mặt phẳng suy ra tứ giác $ACDE$ là lồi, còn nếu $E$ nằm cùng với $B$ trên 1 nửa mặt phẳng thì tứ giác $BCDE$ là lồi

 

[2] Bao giác lồi là tứ giác, suy ra tứ giác này thoả mãn bài toán

 

[3] Bao giác lồi là ngũ giác, chọn 4 điểm bất kì đều sẽ tạo tứ giác lồi thoả mãn

cho $m,n$ là các số nguyên dương mà $m\ge n$.Tính số bộ $(x_1,x_2,...,x_{m+n})$ thỏa mãn đồng thời các điều kiện sau

$\text{i)}$   $x_i\in \left \{ -1,1 \right \}\ \ ,\forall i=\overline{1,m+n}$

$\text{ii)}$  $\sum_{i=1}^k x_i\ge 0\ \ ,\forall k=\overline{1,m+n}$

$\text{iii)}$ $\sum_{i=1}^{m+n}x_i=m-n$

 

Từ điều kiện (iii) ta suy ra có đúng $m$ số $1$ và $n$ số $-1$ trong dãy.

Với mỗi cặp $(k, \sum_{i=1}^{k}x_i)$ ta gắn với một điểm trong toạ độ, như vậy là sẽ qui về bài toán sau

 

Tìm số cách đi từ điểm toạ độ $(0, 0)$ đến điểm toạ độ $(m+n, m-n)$ sau $m+n$ bước đi sao cho trong quá trình đi ta không bước xuống khu vực toạ độ $y$ âm, ở đây với mỗi bước đi ta có thể di chuyển từ $(x,y)$ sang $(x+1, y+1)$ hoặc $(x+1, y-1)$

 

Số cách đi từ $(0,0)$ đến $(m+n,m-n)$ là $C_{m+n}^{m}$

Trong số cách này, với mỗi cách đi mà bước vào khu vực toạ độ $y$ âm, ta tạo 1 song ánh như sau

Xét quá trình từ điểm $(0,0)$ đến điểm đầu tiên bước xuống khu vực toạ độ âm $(x, -1)$, lấy đối xứng tất cả các điểm này qua đường thẳng $y=-1$, ta sẽ được 1 cách đi từ $(0,-2)$ đến $(m+n, m-n)$, và ánh xạ này là song ánh

Suy ra số các cách đi này là $C_{m+n}^{m+1}$

 

Vậy số bộ thoả mãn là $C_{m+n}^{m} - C_{m+n}^{m+1} = \frac{m+1-n}{m+1}C_{m+n}^{m}$

cho em hỏi thế nếu như $\frac{a}{b}$ là số hữu tỉ hoặc vô tỉ,ví dụ $\frac{a}{b}=1,7$ thì có là $c_{i}\equiv -i+1,7\left ( mod\; p_{i} \right )$,thế này thì sao ạ

 

Ở đây $\frac{a}{b} (\mathrm{mod} \; p)$ không phải là tính theo số hữu tỉ bình thường, mà nó có nghĩa như sau

 

Với $(b,p)=1$ thì tồn tại một số tự nhiên $x$ sao cho $bx = 1 (\mathrm{mod} \; p)$, và $\frac{a}{b} = ax (\mathrm{mod} \; p)$

 

Ví dụ như $\frac{2}{3} = 2 \times 2 = 4 (\mathrm{mod} \; 5)$

Cho $a\in \mathbb{Z}, b\in \mathbb{N}^{*}, n\in \mathbb{N}^{*}  $. Chứng minh rằng tồn tại n số hạng liên tiếp của dãy a+b,a+2b,a+3b,... đều là hợp số

 

Do tập các số nguyên tố là vô hạn (chứng minh bằng phản chứng), nên ta có thể chọn $n$ số nguyên tố phân biệt lớn hơn $\max(a,b)$

Gọi các số nguyên tố đấy là $p_1,\dots,p_n$, theo định lý thặng dư trung hoa, tồn tại $x \in N^{*}$ sao cho $x \equiv c_i (\mathrm{mod} \; p_i), \forall i=1,\dots,n$

với $c_i \equiv -i-\frac{a}{b} (\mathrm{mod} \; p_i)$

 

Nhận thấy $a+(x+i)b > p_i$ chia hết $p_i$ nên các số hạng này đều là hợp số (có thể chọn $x$ đủ lớn tuỳ ý thoả mãn)

À vầy cho mình hỏi phần mũ B >2 không thỏa mãn là vì sao vầy ) Chỉ còn phần đó thôi.

 

Cái này không phải là hiển nhiên sao

Bạn giải kĩ phần vô lí này với @@, cảm ơn rất nhiều

 

@@

Nếu tồn tại $\beta_i>0$ với $i>1$ thì ta có $\prod_{i=1}^{k}p_i^{\beta_i}$ và $\prod_{i=2}^{k}p_i^{\alpha_i}$ đều chia hết cho $p_i$,

do đó $p_1-1$ cũng phải chia hết cho $p_i$, mà do $p_i>p_1>p_1-1$ nên vô lý

@@

(Siêu Khó)

Tìm n tự nhiên sao cho a, b là 2 ước nguyên tố cùng nhau của n thì a+b-1 cũng là ước của n

 

Nhận thấy nếu $n$ chỉ có 1 ước số nguyên tố thì luôn thoả mãn, tức $n=p^{k}$ với $p$ là số nguyên tố là 1 nghiệm của bài

 

Giả sử $n$ có ít nhất 2 ước số nguyên tố, đặt $n=\prod_{i=1}^{k}p_i^{\alpha_i}$ với $p_1<\dots<p_k$ là các số nguyên tố, $\alpha_i>0, k>1$

Xét $a=p_1, b=\prod_{i=2}^{k}p_i^{\alpha_i}$, ta có $a+b-1=\prod_{i=2}^{k}p_i^{\alpha_i}+p_1-1$ là ước của $n$ và do đó có thể biểu diễn

$\prod_{i=2}^{k}p_i^{\alpha_i}+p_1-1=\prod_{i=1}^{k}p_i^{\beta_i}$

Nếu tồn tại $\beta_i > 0$ với $i>1$ thì suy ra $p_1-1$ chia hết cho $p_i$, điều này là vô lý

Suy ra $\beta_i=0$ với mọi $i>1$, tức $\prod_{i=2}^{k}p_i^{\alpha_i}+p_1-1=p_1^{\beta_1} \leftrightarrow n=p_1^{\alpha_1}(p_1^{\beta_1}-p_1+1)$

Đến đây ta dễ nhận thấy $\alpha_1\geq\beta_1\geq \alpha_2+\dots+\alpha_k+1\geq 2$

 

Tiếp theo xét $a=p_1^{\beta_1}-p_1+1, b=p_1^2$ ta có $p_1^{\beta_1}-p_1+p_1^2$ là ước của $n$

suy ra $p_1^{\beta_1-1}-1+p_1$ là ước của $p_1^{\beta_1}-p+1 \leftrightarrow p_1^2-1 = t(p_1^{\beta_1-1}+p_1-1)$ với $t$ là số tự nhiên

Nếu $\beta_1>2$ thì nhận thấy không thoả mãn, do đó $\beta_1=2$ và ta có $p_1^2-1=t(2p_1-1)$

Đến đây thì đơn giản, vì $(p_1-1,2p_1-1)=1$ nên $p_1+1$ chia hết cho $2p_1-1$, tức $p_1\leq2$

Với $p_1=2,\beta_1=2$ ta có $n=3\times2^{\alpha}$

 

Nếu $\alpha>2$ xét tiếp với $a=8,b=3$ suy ra $a+b-1=10$ là ước của $n$, điều này không thoả mãn

Vậy $\alpha=2$ và tập các số $n$ thoả mãn là $\{1,12,p^k\}$

Giả sử tồn tại 2 số $a,b \in S$ sao cho $a$ chia hết cho $b$

Đặt $a=kb$, nhận thấy $2 \leq k \leq 7$

Để ý mọi phần tử thuộc $S$ đều đồng dư với $1$ theo mod $9$, suy ra $k \equiv 1 (mod \: 9)$

Nhận thấy không tồn tại giá trị $k$ nào thoả mãn, bài toán được chứng minh 

Chứng minh rằng với mọi số nguyên dương $n$, luôn tồn tại $m \geq 1$ và $2m$ số nguyên tố $p_1,p_2,\dots,p_m,q_1,q_2,\dots,q_m,$ phân biệt sao cho thoả mãn 2 điều kiện sau

 

(1) $p_i >  q_i$ với mọi $i=1,\dots,m$

(2) $n=\sum_{i=1}^{m}p_i-q_i$

Tại sao các phần tử trong mỗi tập đều khác nhau theo modulo p ạ ? Anh giải thích kĩ hơn có được không ?

 

Giả sử tồn tại $x_1 \neq x_2$ sao cho $x_1^2 \equiv x_2^2 (mod\;p) \rightarrow (x_1+x_2)(x_1-x_2) \equiv 0 (mod\;p)$

$1 \leq |x_1-x_2|, |x_1+x_2| \leq p-1$ nên rõ ràng không thể chia hết cho $p$

Với những ý nhỏ thế này chỉ cần em đặt bút xuống thì sẽ thấy ngay thôi

Cho số nguyên tố $p$. Chứng tỏ rằng với mỗi số $p$ luôn tồn tại $x,y$ thỏa mãn $p$ là ước của $x^2+y^2+1$ với $x,y$ thuộc $Z$

 

 

 

CON YÊU BA MẸ NHIỀU LẮM

 

Trường hợp $p = 2$ thì hiển nhiên

Xét 2 tập $A=\{ -x^2\}, B=\{y^2+1\}, x, y = 0,1,...,\frac{p-1}{2}$ thì các phần tử trong mỗi tập đều khác nhau theo module $p$

Do $|A|+|B|=p+1$ nên phải có 2 phần tử giống nhau theo module $p$, do đó tồn tại $x,y$ sao cho $x^2+y^2+1$ chia hết cho $p$

Bài này đáp số là 31 chứ

Mình nhầm chút vì tính cả phần tử 1 trong đó, nên đáp án phải là $2^5-1=31$ như bạn nói

Giả sử chia $S = A \cup B$ ta sẽ có với mỗi phần tử $x \in S$ sẽ hoặc thuộc $A$ hoặc $B$ hoặc cả 2

Do vậy có tất cả $3^{|S|}$ cách chia

cho $p$ là số nguyên tố mà $p\equiv 2(mod \ 3)$.Đặt $A=x^4+x^2y^2+y^4$

CMR nếu $p\mid A$ thì $p^4\mid A$

 

U-Th

Đặt $p = 3k + 2, u=x^2, v=y^2$. Nếu $u$ hoặc $v$ chia hết cho $p$ thì ta có điều phải chứng minh

 

Nếu $(u,p)=(v,p)=1$

$(u-v)A = u^3-v^3$ chia hết cho $p$, do đó $u^{3k}-v^{3k}$ cũng chia hết cho $p$

Mặt khác theo định lý Fecma thì $u^{3k+1} \equiv v^{3k+1} (mod p)$

Từ 2 điều này suy ra $u \equiv v \equiv 0 (mod p)$, và ta có điều phải chứng minh

Gọi S là tập các số nguyên dương n là ước của a²⁵ - a với mọi a nguyên. Hãy tìm số phần tử của S.

 

Để giải bài toán này ta sử dụng tính chất sau

Với một số nguyên tố $p$ bất kì, luôn tồn tại một số $a$ sao cho $p-1$ là số $x$ nhỏ nhất thoả mãn $a^{x}-1$ chia hết cho $p$

Dễ dàng chứng minh kết quả này bằng cách để ý số nghiệm của phương trình không vượt quá số mũ.

 

Nhận thấy với mọi $a$ thì $a^{25}-a$ đều chia hết cho $p$ với $p=2,3,5,7,13$ và sử dụng kết quả trên thì ngoài các số nguyên tố này sẽ không còn số nào là ước của tất cả các số dạng $a^{25}-a$ nữa.

 

Mặt khác với $a=p$ thì $a^{25}-a$ không chia hết cho $p^2$, do đó số phần tử của $S$ là $2^{5}=32$

Thư giãn đầu óc

Xét n là 1 số tự nhiên không đổi và p là 1 ước nguyên tố bất kì của n. Gọi a là 1 số tự nhiên dương bất kì. CM các mệnh đề sau là tương đương:

i) aⁿ - a chia hết cho n ( với mọi a tự nhiên thì aⁿ - a chia hết cho n)

ii) n không chia hết cho p² và n - 1 chia hết cho p - 1 ( với mọi ước n/tố p của n thì .....)

 

Chứng minh (i) => (ii)

Gọi $p$ là một ước số nguyên tố bất kì của $n$, ta sẽ chứng minh tồn tại $a$ sao cho $a^n-a$ không chia hết cho $p^2$

(Edit: Đoạn này có thể chọn luôn $a=p$)

Giả sử không tồn tại $a$ như vậy, xét $(a+p)^n-(a+p)=(a^n-a)+p\left(\sum_{k=2}^{n}C_{n}^{k}p^{k-1}a^{n-k} + na^{n-1}-1\right)$, nhận thấy biểu thức này không chia hết cho $p^2$, vô lý. Suy ra $n$ không chia hết cho $p^2$

Tiếp theo, chọn một số $1 \leq a \leq p-1$ thoả mãn $a^{\frac{p-1}{2}} - 1$ không chia hết cho $p$, tức $p-1$ là số nhỏ nhất thoả mãn $a^x-1$ chia hết cho p.

Mặt khác $a^{n-1}-1$ chia hết cho $p$, suy ra $n-1$ chia hết $p-1$

 

Chứng minh (ii) => (i)

Đặt $n=p_1p_2...p_k$ với $p_i$ là các số nguyên tố phân biệt, với số $a$ bất kì, ta chỉ cần chứng minh $a^n-a$ chia hết cho $p_i$ là đủ

Nếu $a$ chia hết $p_i$, ta có điều hiển nhiên

Nếu $a$ nguyên tố cùng nhau với $p_i$, $a^{n-1}-1$ chia hết $a^{p_i-1}-1$ và chia hết cho $p_i$

Cho p là số nguyên tố lẻ thỏa p - 2 là bội 3. Đặt S = { y² - x³ - 1 / x,y nguyên và thuộc đoạn [0;p - 1] }. CM có nhiều nhất p phần tử của S là bội p.

 

Đặt $p=3k+2$, ta có $x^{p-1}=x^{3k+1} \equiv 1 (mod p)$ với mọi $x=1,..,p-1$

Giả sử $x_1^3 \equiv x_2^3 (mod p) \rightarrow x_1^{3k} \equiv x_2^{3k} (mod p) \rightarrow x_1^{3k+1} \equiv x_1x_2^{3k} \equiv 1 \equiv x_2^{3k+1} (mod p) \rightarrow x_1 \equiv x_2 (mod p)$

Suy ra $\{x^3\}$ là hệ thặng dư đầy đủ theo $mod p$

Với mỗi $y$ chỉ tồn tại duy nhất một giá trị $x$ sao cho $y^2-x^3-1$ chia hết cho $p$ nên $S$ có nhiều nhất $p$ phần tử là bội của $p$

Nhận thấy $ u_{2n} = (2^n-3)(2^n+3)+6=(2^n+3)u_n+6 \rightarrow (u_n, u_{2n})=(u_n, 6)=1$

Đề thi mà có cả những bài lời giải 1 dòng nữa cơ à
Nhìn đi nhìn lại thì thấy chẳng thay đổi gì so với mọi năm. Phạm vi hẹp quá dẫn đến ra bài cũng khó chăng

Đáp số như nhau cả đó em, khai triển cái biểu thức của anh là ra kết quả giống của em

Anh xin góp vui chút
Để giải quyết bài toán này ta sẽ chuyển về dạng tọa độ trong mặt phẳng cho dễ thấy
Ta cũng thay $2n-2$ bằng $2n$ cho dễ viết
Đặt $ s_m=x_1+x_2+...+x_m$ với $m=1,2,..,2n$
Xét trong mặt phẳng tọa độ các điểm $(m,s_m)$, xuất phát từ điểm $(0,0)$ và nối các điểm này lại ta sẽ được 1 đường gấp khúc
Để thỏa mãn điều kiện đề bài thì các đường này phải không cắt đường thẳng $y=-1$
Nhận thấy $s_1=1$, từ $(1,s_1)$ đi đến $(2n,s_{2n})$ (ở đây $s_{2n}=0$) có tất cả $C_{2n-1}^{n}$ cách và ta cần loại các cách đi cắt đường $y=-1$. Xét điểm $(1,-3)$ và tất cả các cách đi từ điểm này tới $(2n,s_{2n})$.Nhận thấy có tất cả $C_{2n-1}^{n-2}$ cách và dễ dàng nhận thấy mỗi cách đi sẽ đều cắt đường thẳng $y=-1$
Với mỗi cách đó xét giao điểm đầu tiên của nó với đường thẳng $y=-1$ và gọi nó là $A$. Lấy đối xứng phần từ $(1,-3)$ tới $A$ qua đường thẳng $y=-1$ ta sẽ ra 1 cách đi từ $(1,s_1)$ đến $(2n,s_{2n})$ mà cắt đường thẳng $y=-1$
Nhận thấy phép lấy đối xứng này là 1 phép song ánh, do đó kết quả ta cần tìm là $C_{2n-1}^{n}-C_{2n-1}^{n-2}$ bộ