Các cặp số đặc biệt trong toán học năm 2024

Trong toán học, các số nguyên a và b được gọi là nguyên tố cùng nhau (tiếng Anh: coprime hoặc relatively prime) nếu chúng có Ước số chung lớn nhất là 1. Ví dụ 5 và 2 là nguyên tố cùng nhau vì chúng có ước chung lớn nhất là 1, nhưng 6 và 27 không nguyên tố cùng nhau vì chúng có ước chung lớn nhất là 3. Số 1 là nguyên tố cùng nhau với mọi số nguyên. Nhưng cũng có những trường hợp đặc biệt mà các hợp số là số nguyên tố cùng nhau. Ví dụ: 6 và 25 tuy là hợp số nhưng chúng có ước chung lớn nhất là 1 nên chúng là những số nguyên tố cùng nhau.

Một phương pháp xác định tính nguyên tố cùng nhau của hai số nguyên là sử dụng thuật toán Euclid. Phi hàm Euler của một số nguyên dương n là số các số nguyên giữa 1 và n nguyên tố cùng nhau với n.

Các điều kiện sau tương đương với điều kiện a và b nguyên tố cùng nhau:

• Tồn tại các số nguyên x và y sao cho ax + by = 1 (xem Đẳng thức Bézout).
• Số nguyên b là khả nghịch theo modulo a: nghĩa là tồn tại số nguyên y sao cho by ≡ 1 (mod a). Nói cách khác, b là một đơn vị trong vành Z/aZ của các số nguyên modulo a.
  Hình 1. Các số 4 và 9 là nguyên tố cùng nhau vì đường chéo không đi qua điểm nguyên nào trong hình chữ nhật

Ta cũng có: nếu a và b là nguyên tố cùng nhau và br ≡ bs (mod a), thì r ≡ s (mod a) (vì ta có thể chia cho b khi theo modulo a). Tiếp theo, nếu a và b1 là nguyên tố cùng nhau, và a và b2 cũng nguyên tố cùng nhau, thì a và b1b2 cũng là nguyên tố cùng nhau(vì tích của các đơn vị lại là đơn vị).

Nếu a và b là nguyên tố cùng nhau và a là ước của tích bc, thì a là ước của c. Đây là tổng quát hóa của bổ đề Euclid (nếu p là số nguyên tố, và p là ước của tích bc, thì p là ước của b hoặc p là ước của c.

Hai số nguyên a và b là nguyên tố cùng nhau nếu và chỉ nếu đoạn thẳng nối điểm có tọa độ (a, b) trong Hệ tọa độ Descartes với gốc (0,0), không có điểm nào trên nó có tọa độ nguyên. (Hình 1.)

Xác suất để hai số nguyên chọn ngẫu nhiên là nguyên tố cùng nhau bằng 6/π2 (xem pi), xấp xỉ 60%.Xem để hiểu rõ hơn.

Hai số tự nhiên a và b là nguyên tố cùng nhau nếu và chỉ nếu 2a − 1 và 2b − 1 là nguyên tố cùng nhau.

Nếu n≥1 là một số nguyên, các tập hợp số nguyên tố cùng nhau với n, lấy theo modulo n, tạo thành một nhóm với phép nhân; nó được ký hiệu là (Z/nZ)× hoặc Zn*.

Cho n số nguyên a1, a2,..., an. Các số này được gọi là nguyên tố cùng nhau nếu ước chung lớn nhất của n số đó bằng 1.

Cần phân biệt với khái niệm nguyên tố cùng nhau từng đôi một hay đôi một nguyên tố cùng nhau. Các số a1, a2,..., an được gọi là nguyên tố cùng nhau từng đôi một nếu từng cặp hai số khác nhau trong chúng là nguyên tố cùng nhau. Nói cách khác, nguyên tố cùng nhau từng đôi một là điều kiện mạnh hơn của nguyên tố cùng nhau, một dãy số nguyên tố cùng nhau từng đôi một thì cũng sẽ nguyên tố cùng nhau nhưng ngược lại chưa chắc đã đúng

Ví dụ: Ba số 2, 10, 15 là nguyên tố cùng nhau, nhưng không nguyên tố cùng nhau từng đôi một.

Khái niệm nguyên tố cùng nhau từng đôi một trở thành giả thuyết quan trọng trong nhiều kết quả của lý thuyết số, chẳng hạn như định lý thặng dư Trung Quốc.

Khi có vô hạn số, ta vẫn có các dãy thoả mãn điều kiện nguyên tố cùng nhau từng đôi một, chẳng hạn như dãy các só nguyên tố, dãy Sylvester hoặc dãy các số Fermat

I. Dãy Fibonaci

Dãy số Fibonaci được xác định bởi công thức sau:

{f0=0.f1=1.fi=fi−1+fi−2,với i≥2.\begin{cases}f_0 = 0.\\f_1 = 1.\\ f_i = f_{i - 1} + f_{i - 2},&\text{với }i \ge 2.\end{cases}

Một số phần tử đầu tiên của dãy Fibonaci là: 0,1,1,2,3,5,80, 1, 1, 2, 3, 5, 8 Ngoài ra, số Fibonaci thứ NN còn có thể tính bằng công thức tổng quát:

fN=15×[(1+52)N−(1−52)N] (1)f_N = \frac{1}{\sqrt{5}}\times \left[\left(\frac{1 + \sqrt{5}}{2}\right)^N - \left(\frac{1 - \sqrt{5}}{2}\right)^N\right] \ (1)

Dãy Fibonaci là đáp án của một số bài toán dưới đây:

1. Bài toán cổ về các cặp thỏ

Phát biểu bài toán:

• Ban đầu chỉ có một cặp thỏ được sinh ra.
• Hai tháng sau khi ra đời, mỗi cặp thỏ sẽ sinh ra một cặp thỏ con mới.
• Khi đã sinh con rồi thì cứ mỗi tháng tiếp theo, chúng lại sinh được một cặp con mới.
• Giả sử các con thỏ không bao giờ chết, hãy đếm số lượng cặp thỏ ở tháng thứ N?N?

Ví dụ: Với N=5,N = 5, ta thấy:

Giải thích:

• Giữa tháng thứ nhất: 11 cặp (cặp ban đầu).
• Giữa tháng thứ hai: 11 cặp (cặp ban đầu vẫn chưa đẻ).
• Giữa tháng thứ ba: 22 cặp (cặp ban đầu đẻ thêm một cặp con).
• Giữa tháng thứ tư: 33 cặp (cặp ban đầu tiếp tục đẻ).
• Giữa tháng thứ năm: 55 cặp (cặp ban đầu tiếp tục đẻ và cặp thứ hai bắt đầu đẻ).

2. Bài toán xếp Domino

Phát biểu bài toán: Đếm số cách xếp N−1N - 1 thanh Domino có kích thước 2×12 \times 1 để phủ kín một bảng ô vuông kích thước 2×(N−1)2 \times (N - 1).

Ví dụ: Có 88 cách khác nhau để xếp các thanh Domino kích thước 2×12 \times 1 phủ kín bảng 2×5 (N=6,f6=8)2 \times 5 \ (N = 6, f_6 = 8):

3. Cài đặt

Đối với các giá trị N (N≤107)N \ (N \le 10^7) không quá lớn, ta có thể tính trực tiếp số Fibonaci bằng công thức truy hồi fi=fi−1+fi−2f_i = f_{i - 1} + f_{i - 2}. Trong trường hợp NN lớn, cần phải sử dụng Phép nhân ma trận để tính toán, bài toán này sẽ được đề cập tới sau.

Cài đặt bằng công thức truy hồi:

long long fibo(int N)
{
    if (N <= 1)
        return N;
    int fi_2 = 0, fi_1 = 1, cur_fi = 0;
    for (int i = 2; i <= N; ++i)
    {
        cur_fi = fi_1 + fi_2;
        fi_2 = fi_1;
        fi_1 = cur_fi;
    }
    return fi_ntext;
}

II. Dãy Catalan

Số Catalan được xác định bởi công thức sau:

CatalanN=1N+1×C2NN=(2N)!(N+1)!×N!;với N≥0Catalan_N = \frac{1}{N + 1}\times C_{2N}^{N} = \frac{(2N)!}{(N + 1)! \times N!}; \text{với } N \ge 0

Một số phần tử đầu tiên của dãy Catalan là: 1,1,2,5,14,42,132,...1, 1, 2, 5, 14, 42, 132,...

Số Catalan là đáp án của các bài toán sau:

1. Bài toán đặt ngoặc

Phát biểu bài toán: Cho trước số nguyên không âm N,N, hãy đếm số cách khác nhau để đặt NN dấu ngoặc mở và NN dấu ngoặc đóng đúng đắn. Cách đặt ngoặc đúng đắn có thể phát biểu đệ quy như sau:

• ()() là một cách đặt ngoặc đúng.
• Nếu XX là một cách đặt ngoặc đúng thì (X),()X(X), ()X và X()X() cũng là cách đặt ngoặc đúng.

Ví dụ: Với N=3,N=3, ta có 55 cách đặt ngoặc đúng sau:

((())),(()()),(())(),()(()),()()()((())), (()()), (())(), ()(()), ()()()

2. Đếm cây nhị phân

Phát biểu bài toán: Cho trước số nguyên không âm N, hãy đếm số cây nhị phân khác nhau có đúng (N+1)(N+1) lá?

Ví dụ: Với N=3N = 3:

3. Chia đa giác

Phát biểu bài toán: Cho một đa giác lồi gồm (N+2)(N+2) đỉnh. Ta chia đa giác thành các tam giác bằng cách vẽ các đường chéo không cắt nhau trong đa giác. Hỏi có bao nhiêu cách chia như vậy?

Ví dụ: Với N=4N = 4:

4. Cài đặt

Dưới đây cài đặt chương trình tính số Catalan thứ N (N≤106)N \ (N \le 10^6) và đưa ra kết quả là phần dư sau khi chia cho 109+710^9+7

long long modular_exponentiation(long long A, long long B, long long M)  // Tính A^B % M.
{
    if (B == 0)
        return 1LL;
    long long half = modular_exponentiation(A, B / 2LL, M) % M;
    if (B & 1)
        return (((half * half) % M) * (A % M)) % M;
    else
        return (half * half) % M;
}
long long inverse_modulo(long long A, long long M) // Nghịch đảo modulo M của A.
{
    return modular_exponentiation(A, M - 2, M);
}
long long catalan_N(long long N, long long M)
{
    long long x = 1, y = 1;
    for (int i = N + 2; i <= 2 * N; ++i)
        x = (x * i) % M;
    for (int i = 1; i <= N; ++i)
        y = (y * i) % M;
    y = inverse_modulo(y, M);
    return (x * y) % M;
}
int main()
{
    long long M = 1e9 + 7;
    cout << catalan_N(N, M);
}

III. Số Euler (Eulerian Number)

Số Euler A(N,M)A(N, M) là số lượng hoán vị của các số từ 11 tới NN mà có đúng MM số lớn hơn số đứng liền trước nó. Lấy ví dụ, với N=3,M=1,N = 3, M = 1, có 44 hoán vị từ 11 tới 33 mà có đúng 11 số lớn hơn số liền trước nó, thể hiện trong bảng dưới đây:

Số Euler là hệ số của đa thức Euler bậc MM với công thức:

AN(t)=∑M=0NA(N,M)×tMA_N(t) = \sum_{M = 0}^N A(N, M)\times t^M

Ta có thể tính số Euler bằng hệ thức truy hồi sau:

A(N,M)={0,với M≥N hoặc N=0.1,với M=0.(N−M)×A(N−1,M−1)+(M+1)×A(N−1,M),trường hợp khaˊc.A(N, M) = \begin{cases}0, &\text{với } M \ge N \text{ hoặc } N = 0.\\ 1, &\text{với } M = 0. \\(N - M)\times A(N - 1, M - 1) + (M + 1) \times A(N - 1, M), &\text{trường hợp khác.}\end{cases}

Cài đặt: Dưới đây cài đặt chương trình tính số Euler bằng đệ quy, ngoài ra bạn đọc có thể suy nghĩ cách cài đặt bằng quy hoạch động:

long long euler_number(int N, int M)
{
    if (M == 0)
        return 1;
    if (M >= N || N == 0)
        return 0;
    return (N - M) * euler_number(N - 1, M - 1) + 
           (M + 1) * euler_number(N - 1, M);
}

IV. Tam giác Pascal:

• Tam giác Pascal là một công thức xác định các tổ hợp chập kk của n,n, bằng tính chất của tổ hợp: Cnk=Cn−1k−1+Cn−1k (0

• Ngoài ra, tam giác Pascal còn sử dụng để tính các hệ số của khai triển nhị thức Newton bậc N (a+b)NN \ (a + b)^N thành một đa thức có N+1N+1 số hạng. Nhị thức này đã được chứng minh bởi Issac Newton vào năm 1665,1665, với công thức như sau:

(a+b)N=∑k=0NCNk×an−k×bk(a+b)^{N=\sum_{k = 0}^N C^k_N\times a}{n - k} \times b^k

• Cài đặt: Xây dựng tam giác Pascal gồm NN hàng:

  void pascal_triangle(int N) {

  for (int i = 0; i <= N; ++i) // Cột đầu tiên của mọi hàng bằng 1.  
      c[i][0] = 1;  
  for (int i = 1; i <= N; ++i)  
      for (int j = 1; j <= i; ++j)  
          c[i][j] = c[i - 1][j - 1] + c[i - 1][j];  
  

  }

V. Công thức bao hàm - loại trừ:

• Công thức bao hàm - loại trừ là một công thức sử dụng để tính lực lượng (số lượng phần tử) của hợp của nhiều tập hợp. Công thức được phát biểu như sau: "Để tính lực lượng của hợp của nhiều tập hợp, ta tính tổng lực lượng các tập hợp đó, rồi trừ đi lực lượng của giao của các cặp hai tập hợp khác nhau, rồi cộng lực lượng của giao các bộ ba tập hợp khác nhau, rồi trừ đi lực lượng của các bộ bốn tập hợp, và cứ thế cho đến khi ta xét đến giao của tất cả các tập hợp."
• Đối với các tập hợp, công thức có thể được viết ở dạng như sau: Giả sử có NN tập hợp A1,A2,A3,...,ANA_1, A_2, A_3,..., A_N. Lực lượng của hợp của NN tập hợp là:∣⋃i=1NAi∣=∑i=1n∣Ai∣−∑i≠j∣Ai∩Aj∣+∣A1∩A2∩A3∣+∣A1∩A2∩A4∣+⋯+|\bigcup_{i=1}^N A_i| = \sum_{i=1}^n |A_i| - \sum_{i \ne j} |A_i \cap A_j| + |A_1 \cap A_2 \cap A_3| + |A_1 \cap A_2 \cap A_4| + \cdots + ∣AN−2∩AN−1∩AN∣−⋯−(−1)n∣A1∩A2∩…∩AN∣|A_{N-2} \cap A_{N-1} \cap A_N| - \cdots - (-1)^n|A_1 \cap A_2 \cap … \cap A_N|
• Ta có thể minh họa công thức bằng một sơ đồ Venn trong trường hợp N=3N = 3 như sau:
  Như sơ đồ, ta thấy lực lượng của A∩B∩CA \cap B \cap C bằng tổng lực lượng của A,B,CA, B, C trừ đi lực lượng của các giao A∩B,B∩C,C∩AA \cap B, B \cap C, C \cap A rồi cộng thêm lực lượng của A∩B∩CA \cap B \cap C:

∣A∪B∪C∣=∣A∣+∣B∣+∣C∣−∣A∩B∣−∣B∩C∣−∣C∩A∣+∣A∩B∩C∣| A \cup B \cup C | = |A| + |B| + |C| - |A \cap B| - |B \cap C| - |C \cap A| + |A \cap B \cap C|

Bằng phương pháp tương tự ta có thể minh họa được công thức với NN tập hợp.

• Ví dụ: Đếm số lượng số từ 11 tới NN và không chia hết cho số nào trong tập {2,3,5}\{2, 3, 5\}:

  int count_numbers(int N) {

  return N - N / 2 - N / 3 - N / 5 + N / (2  3) +  
         N / (3  5) + N / (2  5) - N / (2  3 * 5);  
  

  }
  Ta có thể biến đổi bài toán thành đếm phần bù: Đếm số lượng phần tử chia hết cho ít nhất một số trong tập {2,3,5}\{2, 3, 5\} rồi lấy NN trừ đi số lượng đó. Đặt AA là tập hợp các phần tử chia hết cho 2, B2,\ B là tập hợp các phần tử chia hết cho 3, C3, \ C là tập hợp các phần tử chia hết cho 55 từ 1 tới NN. Cần tính ∣A∪B∪C∣|A \cup B \cup C|. Dựa vào công thức bao hàm, loại trừ, ta có:

∣A∪B∪C∣=∣A∣+∣B∣+∣C∣−∣A∩B∣−∣B∩C∣−∣C∩A∣+∣A∩B∩C∣| A \cup B \cup C | = |A| + |B| + |C| - |A \cap B| - |B \cap C| - |C \cap A| + |A \cap B \cap C|

\=⌊N2⌋+⌊N3⌋+⌊N5⌋−⌊N2.3⌋−⌊N2.5⌋−⌊N3.5⌋+⌊N2.3.5⌋=\left \lfloor{\frac{N}{2}} \right \rfloor+\left \lfloor{\frac{N}{3}} \right \rfloor+\left \lfloor{\frac{N}{5}} \right \rfloor-\left \lfloor{\frac{N}{2.3}} \right \rfloor-\left \lfloor{\frac{N}{2.5}} \right \rfloor-\left \lfloor{\frac{N}{3.5}} \right \rfloor+\left \lfloor{\frac{N}{2.3.5}} \right \rfloor