tanlsth

đặ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)

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$

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$

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$

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$