[Algorithm] Phương pháp sắp xếp mới, mà tôi gọi là Domain Sorting.

Tựa:
    Sắp xếp xưa nay là một vấn đề hoàn toàn không mới mẻ và đã có rất nhiều thuật toán về sắp xếp từ đơn giản đến phức tạp như sắp xếp nổi bọt, sắp xếp chèn, sắp xếp trộn, sắp xếp nhanh... Tuy nhiên, dữ liệu ở đời thực quả thật thú vị khi chúng luôn ngẫu nhiên và sự ngẫu nhiên này giá trị ở chỗ chúng luôn có khoảng tăng và giảm nhất định, mà các phương pháp sắp xếp cổ điển chưa tận dụng được. Vậy nên tôi nghĩ ra phương pháp sắp xếp theo miền.

Chi tiết:
    Trước tiên ta xuất phát từ một số bài toán nhỏ như sau, với định nghĩa "miền" là một dải giá trị liên tục đơn điệu tăng  [a,b] với a,b được gọi là "bao miền":

           Cho trước 2 miền giao nhau [a,b] và [c,d], làm thế nào để trộn hai miền này để thu được miền [a,d]?

           Nhận xét 1: Nếu a=b và |[c,d]|<=2 việc trộn miền chỉ đơn thuần là so sánh a với hai bao miền còn lại, rồi tìm cách đặt a vào miền đó.
           Nhận xét 2: Nếu [a,b]={a,[g,h],b} thuộc [c,d], việc trộn với độ phức tạp O(n), được thực hiện như sau: Giả sử [c,d]={c1,...,cn,{e,[i,k],f},dn,..,d1}, với [e,f] và [a,b] là hai miền giao nhau hoặc bao nhau, ta trộn miền [a] và miền [c1,e] theo Nhận xét 1, tương tự với b. Sau đó tiếp tục trộn miền [i,k] và miền con [g,h] của [a,b] vào nhau.
           Nhận xét 3: Nếu 2 miền giao nhau, ta tách thành 3 miền, và chỉ xử lý phần giao nhau.
           Nhận xét 4: Với một dãy các miền không giao nhau, ta trộn 2 miền kề nhau đôi một, sau đó lặp lại cho đến khi chỉ còn 1 miền, nếu gặp 2 miền giao nhau ta lại làm mịn tiếp.

          Dựa trên những nhận xét trên, ta có sắp xếp miền với tư tưởng đệ quy. Ví dụ:
                                  1  5  7   3   6   7   3   2   6   9   4   2   10
                                 [1  5  7]  [3  6   7]  [3  2]  [6  9]  [4   2] [10]   (đây là các khoảng tăng giảm)
                                 [1  5  7]  [3  6   7]  [2  3]  [6  9]  [2   4] [10]   (lật thành toàn bộ tăng)
                                 [1  [5]--[3  6  7]  7]   [2   3   6   9]  [2  4  10]   (trộn miền 1-2, 3-4, 5-6)
                                 [1  [3  [5]   6   7]  7]   [2  3  6   9]  [2  4  10]    (trộn miền con của 1-2)
                                 [1   3   5    6   7    7]   [2   3  6   9]  [2   4   10]
                                 [1  [2   3   6   9]--[3   5   6  7  7] ]  [2   4  10]   (trộn miền 1-2)
                                 [1  2   3   [6]--[3  5  6   7   7]  9]  [2  4   10]     (trộn miền con của 1-2)
                                 [1  2   3    3   5   [6]--[6]  7  7   9]  [2  4  10]
                                 [1  2   3    3   5   6   6  7  7   9]  [2  4  10]
                                 [1  2   [3   3   5   6   6   7   7  9]--[2  4  10] ]
                                 [1  2   2   [4]--[3   3   5   6   6   7   7  9]  10]
                                 [1  2   2   3   3  [4]  5   6  6  7  7  9  10]
                                 [1  2   2   3   3  4  5   6  6  7  7  9  10]               xong!

Tóm lại:
         Trên đây là những bước triển khai rất sơ sài về một phương pháp sắp xếp cảu tôi, có lẽ bạn đang thắc mắc tại sao tôi viết loằng ngoằng ra vài dòng sau đó vứt đấy, thì tôi xin điều trần rằng:
          - Thuật toán tuy mới nhưng khi nhìn lại và suy ngẫm, tôi cho rằng nó chẳng có gì thú vị. Thậm chí nếu nhìn sâu ra thì đệch mợ, nó na ná merge sort cải tiến. Thế mới cay!
          - Về độ phức tạp, nó không tốt hơn các loại sort đang thông dụng, tôi ước chừng cũng rơi vào khoảng NlogN nếu gặp case xấu, tức là ngang merge sort nếu vào case xấu, cụ thể là khi các dãy tăng đơn điệu có độ dài bằng nhau và bằng 2. Tôi sẽ kiểm chứng lại sau!...
         Cuối cùng thì vẫn sướng sướng vì nghĩ ra cái gì đó, hi vọng một ngày nào đó tôi tìm ra cái gì mới hơn ở trong bài viết này. Cheer!

[Toán] Chứng minh Fermat nhỏ bằng sơ cấp

Ta vốn biết các chứng minh liên quan đến nhóm cylic Z/n và phi hàm Euler. Nhưng với sơ cấp thì sao.
Fermat nhỏ được phát biểu như sau:

"Định lý nhỏ của Fermat khẳng định rằng nếu ${\displaystyle p}$ là một số nguyên tố, thì với số nguyên ${\displaystyle a}$ bất kỳ, ${\displaystyle a^{p}-a}$ sẽ chia hết cho ${\displaystyle p}$."

 Xuất phát từ khai triển của nhị thức Newton ta có

Dễ dàng thấy rằng nếu n nguyên tố  chia hết cho n (với mọi n). Vậy nên

Nên 

Sau a lần ta được