Cho số nguyên dương $n>1.$ Tìm số hàm không giảm $f: \{1,2,...,n\} \to \{1,2,...,n\}$ thỏa mãn điều kiện $f(x)\leq x$ với mọi $x\in \{1,2,...,n\}$

Lời giải bài 20. Từ điều kiện đầu cho ta các số trên phân biệt (lưu ý là $\gcd(0, a) = a$). Ta sẽ sử dụng các bổ đề sau:
Bổ đề. Một số tự nhiên $n$ lẻ có thể viết dưới dạng tổng hai số chính phương nguyên tố cùng nhau khi và chỉ khi mọi ước của $n$ đều có dạng $4k + 1$

Cho mình hỏi tại sao lại nguyên tố cùng nhau vậy?

Hướng đi của mình dài :v

Nhận xét $1$: mọi số nguyên tố dạng $4l+1$ đều có thể biểu diễn dưới dạng tổng $2$ số chính phương. Cái này cơ bản.

Nhận xét $2$: mọi số nguyên dương có dạng $2^{\alpha }(4l+1)$ với $\alpha  =0$ hoặc $\alpha  =1$ hoặc $\alpha=2$ hoặc $\alpha$ bất kì

đều có thể biểu diễn dưới dạng tổng $2$ số chính phương

cái này cm rất dễ dựa vào nhận xét $1$.

 

Nếu $p=4t+1$, chọn $a=4$, $b=4t-3$ thì $2ab=2^3(4t-3)$, theo nhận xét $2$ ta có $đpcm$

Nếu $p=4t+3$, chọn $a=2$, $b=4t+1$ thì $2ab=2^2(4t+1)$, theo nhận xét $2$ ta cũng có $đpcm$.

Các trường hợp $p$ nhỏ nhỏ rất dễ để chỉ ra nên ko xét.

Cho mình hỏi ở nhận xét 2, $4l+1$ có phải là số nguyên tố không? Nếu không thì mình thấy trường hợp số $l=5$, $\alpha =0$ sai. Còn nếu $4l+1$ là số nguyên tố thì phần ở dưới, $4t-3$ chưa chắc là số nguyên tố.

Công thức của dãy $\frac{\frac{c^{2}}{d^{2}}+\frac{e^{2}}{f^{2}}}{\frac{c}{d}+\frac{e}{f}}$ 

Ý mình là tại sao $x_n$ không thuộc $\mathbb{Z}$?

Hiển nhiên $x_{3}$ không nguyên , cũng dễ thấy $x_{n}$ hữu tỷ với mọi $n$

Ta đặt $x_{n-1}=\frac{c}{d},x_{n-2}=\frac{e}{f}$ thế thì $x_{n}=\frac{(cf)^{2}+(ed)^{2}}{df(cf+ed)}$ không thuộc $Z$

Thật ra không cần điều kiện nguyên tố cùng nhau chỉ cần $>1$ và phân biệt

Vif $a$ khác $b$ thì $\frac{a^{2}+b^{2}}{a+b}=a+b-\frac{2ab}{a+b}$

Bạn làm chỗ này rõ giúp mình được không. Cảm ơn bạn 

(Croatia TST 2011) Với $a,b$ là hai số nguyên dương nguyên tố cùng nhau và $a,b > 1,$ cho dãy $(x_n)$ thỏa mãn 

Chào buổi sáng bạn Stoker   chắc bạn đọc cùng tài liệu với mình

https://www.scribd.c...onal-Equations 

=)) Mod qua tha em sáng rồi mờ mắt rồi .

Bài số $10$ nhé =)) 

Thật ra mình gặp bài đó trong chuyển khảo phương trình hàm mà thấy lời giải không chính xác nên hỏi các bạn thử

P/s: Cảm ơn bạn, tài liệu rất hay 

Tìm tất cả hàm số $f: \mathbb{R} \to \mathbb{R}$ thỏa mãn

$$f(yf(x)+x)+f(xf(y)-y)=f(x)-f(y)+2xy,\ \forall\ x,y \in \mathbb{R}$$

Cách của mình.

Ta sẽ chứng minh $p\mid a^{2^{n+1}}+1$ với $a$ nguyên dương nào đó, rồi tương tự như bài của Ego ta có điều phải chứng minh.

Theo trên ta có nếu $p$ là ước của $2^{2^n}+1$ thì $p\equiv 1\ (\text{mod}\ 2^{n+1})$

Mà $n\geq 2$ nên $p\equiv 1\ (\text{mod}\ 8)$

Do đó tồn tại $a$ sao cho $a^2\equiv 2\ (\text{mod}\ p)$

Hay $a^{2^{n+1}}\equiv 2^{2^n} \equiv -1\ (\text{mod}\ p) \implies p\mid a^{2^{n+1}}+1.$ Ta có điều phải chứng minh.

Hình như bài toán phải là $p$ có dạng $2^{n + 1}k + 1$. Ví dụ với $n = 1$ thì bài toán của bạn đâu đúng.
Bài này cũng khá kinh điển rồi. Mình nhớ có một bài (ý tưởng từ bài này) trong đề China TST đánh giá độ lớn của ước nguyên tố $p$ này :-D.
Yêu cầu bài toán chứng minh tương đương với $p\equiv 1\pmod{2^{n + 1}}$
Ta có $p\mid 2^{2^{n}} + 1 \implies \text{ord}_{p}(2)\mid 2^{n + 1} \implies \text{ord}_{p}(2) = 2^{n + 1}$
Mặt khác, để ý $p$ lẻ, áp dụng định lý Fermat nhỏ, $2^{p - 1} \equiv 1\pmod{p} \implies 2^{n + 1} \mid p - 1$.
Ta kết thúc chứng minh. $\bigstar$.

Remark

Hình như có lần mình chứng minh bằng thuần định lý Fermat nhỏ ở AoPS hay sao á.... Dài.

Mới đầu mình đọc trong wiki thấy $n+2$ nên thấy kì. 

Mình có thử giá trị $n=5,6,9$ thấy thỏa mà không chứng minh được nên đăng. Cũng có thể bài toán đúng với $n\geq 2.$ Bạn xem thử xem sao.

Chứng minh rằng nếu $p$ là ước nguyên tố của $2^{2^n}+1$ thì $p$ có dạng $2^{n+2}k+1.$