6. Bài tập số học sưu tầm

Câu 1 (đề kiểm tra, ITMO). Chứng minh (không dùng quy nạp) rằng với mọi \(n \in \mathbb{N}\) thì

\[5 \cdot 2^{3n-2} + 3^{3n-1} \ \vdots \ 19.\]

Theo định lý Fermat nhỏ thì \(2^{18} \equiv 1 \pmod{19}\), hay \((2^3)^6 \equiv 1 \pmod{19}\). Tương tự \(3^{18} \equiv 1 \pmod{19}\). Do đó mình sẽ xét các dạng của \(n\) là \(6k\), \(6k+1\), ..., \(6k+5\).

Trường hợp 1. \(n = 6k\). Khi đó

\[\begin{split}& 2^{3n-2} = 2^{3 \cdot 6k - 2} \equiv 2^{-2} = 5 \pmod{19} \\ & 3^{3n-1} = 3^{3 \cdot 6k - 1} \equiv 3^{-1} = 13 \pmod{19} \\ \Rightarrow \ & 5 \cdot 2^{3n-2} + 3^{3n-1} \equiv 5 \cdot 5 + 13 \equiv 0 \pmod{19}.\end{split}\]

Trường hợp 2. \(n = 6k + 1\). Khi đó

\[\begin{split}& 2^{3n-2} = 2^{3 \cdot 6k + 1} \equiv 2 \pmod{19} \\ & 3^{3n-1} = 3^{3 \cdot 6k + 2} \equiv 3^{2} = 9 \pmod{19} \\ \Rightarrow \ & 5 \cdot 2^{3n-2} + 3^{3n-1} \equiv 5 \cdot 2 + 9 \equiv 0 \pmod{19}.\end{split}\]

Trường hợp 3. \(n = 6k + 2\). Khi đó

\[\begin{split}& 2^{3n-2} = 2^{3 \cdot 6k + 4} \equiv 2^{4} = 16 \pmod{19} \\ & 3^{3n-1} = 3^{3 \cdot 6k + 5} \equiv 3^{5} = 15 \pmod{19} \\ \Rightarrow \ & 5 \cdot 2^{3n-2} + 3^{3n-1} \equiv 5 \cdot 16 + 15 \equiv 0 \pmod{19}.\end{split}\]

Trường hợp 4. \(n = 6k + 3\). Khi đó

\[\begin{split}& 2^{3n-2} = 2^{3 \cdot 6k + 7} \equiv 2^{7} = 14 \pmod{19} \\ & 3^{3n-1} = 3^{3 \cdot 6k + 8} \equiv 3^{8} = 6 \pmod{19} \\ \Rightarrow \ & 5 \cdot 2^{3n-2} + 3^{3n-1} \equiv 5 \cdot 14 + 6 \equiv 0 \pmod{19}.\end{split}\]

Trường hợp 5. \(n = 6k + 4\). Khi đó

\[\begin{split}& 2^{3n-2} = 2^{3 \cdot 6k + 10} \equiv 2^{10} = 17 \pmod{19} \\ & 3^{3n-1} = 3^{3 \cdot 6k + 11} \equiv 3^{11} = 10 \pmod{19} \\ \Rightarrow \ & 5 \cdot 2^{3n-2} + 3^{3n-1} \equiv 5 \cdot 17 + 10 \equiv 0 \pmod{19}.\end{split}\]

Trường hợp 6. \(n = 6k + 5\). Khi đó

\[\begin{split}& 2^{3n-2} = 2^{3 \cdot 6k + 13} \equiv 2^{13} = 3 \pmod{19} \\ & 3^{3n-1} = 3^{3 \cdot 6k + 14} \equiv 3^{14} = 4 \pmod{19} \\ \Rightarrow \ & 5 \cdot 2^{3n-2} + 3^{3n-1} \equiv 5 \cdot 3 + 4 \equiv 0 \pmod{19}.\end{split}\]

Câu 2 (đề kiểm tra, ITMO). Tính

\[1! + 2! + \ldots + 2023! + 2024! \bmod 10.\]

Trong các giai thừa từ \(5!\) trở đi luôn có \(5\) và \(2\) do đó luôn chia hết cho \(10\). Vì vậy chỉ cần tính

\[1! + 2! + 3! + 4! = 1 + 2 + 6 + 24 \equiv 3 \bmod 10.\]

Câu 3 (đề kiểm tra, ITMO). Chứng minh số \(154^{20} + 139^{31}\) là hợp số.

Vì

\[154^{20} \equiv (-1)^{20} \equiv 1 \pmod 5 \ \text{và} \ 139^{31} \equiv (-1)^{31} \equiv -1 \pmod 5\]

nên số đã cho chia hết cho \(5\) và do đó là hợp số.

Câu 4 (đề kiểm tra, ITMO). Chứng minh số \(31^{51} + 27\) là hợp số.

Dễ thấy \(31\) là số lẻ nên lũy thừa của nó cũng là số lẻ. Tổng hai số lẻ là số chẵn nên số đã cho chia hết cho \(2\) và do đó là hợp số.

Câu 5 (đề kiểm tra, ITMO). Chứng minh với mọi \(n \in \mathbb{N}\) thì \(n^8 + 4\) là hợp số.

Ta có

\[n^8 + 4 = n^8 + 4n^4 + 4 - 4n^4 = (n^4 + 2) - (2n^2)^2 = (n^4 + 2 - 2n^2) (n^4 + 2 + 2n^2).\]

Hai biểu thức trong ngoặc luôn lớn hơn \(1\) nên suy ra \(n^8 + 4\) là hợp số.

Câu 6 (đề kiểm tra, ITMO). Tìm tất cả số nguyên tố \(p\) sao cho \(3p + 20\) và \(4p + 1\) là số nguyên tố.

Chưa làm ra.

Câu 7 (đề kiểm tra, ITMO). Tìm tất cả số nguyên tố \(p\) sao cho \(2p^2 + 5p - 2\) cũng là số nguyên tố.

Chưa làm ra.

Câu 8 (đề kiểm tra, ITMO). Chứng minh rằng không tồn tại đa thức \(P\) với hệ số nguyên sao cho \(P(40) = 30\) và \(P(19) = 24\).

Đặt

\[P(x) = a_n x^n + a_{n-1} x^{n-1} + \ldots + a_1 x + a_0.\]

Khi đó

\[P(40) = a_n \cdot 40^n + a_{n-1} \cdot 40^{n-1} + \ldots + a_1 \cdot 40 + a_0,\]

và

\[P(19) = a_n \cdot 19^n + a_{n-1} \cdot 19^{n-1} + \ldots + a_1 \cdot 19 + a_0.\]

Vì \(40^k - 19^k = (40 - 19) \cdot (\ldots)\) nên \(40^k - 19^k\) chia hết cho \(40 - 19 = 21\) với mọi \(k\).

Nói cách khác \(P(40) - P(19)\) chia hết cho \(21\), nhưng \(30 - 24 = 6\) không chia hết \(21\). Do đó không tồn tại đa thức \(P\) thỏa mãn đề bài.

Câu 9 (đề kiểm tra, ITMO). Tìm tập tất cả số \(x \in \mathbb{Z}\) sao cho \(533 x \equiv 1 \pmod{17}\).

Vì \(533 \equiv 6 \pmod{17}\) nên ta chỉ cần giải phương trình \(6 x \equiv 1 \pmod{17}\) là đủ.

Sử dụng thuật toán Euclid mở rộng có thể tính được \(6^{-1} = 3 \pmod{17}\), suy ra nghiệm là

\[x \equiv 3 \pmod{17},\]

nghĩa là \(x = 3 + 17k\) với \(k \in \mathbb{Z}\).

Câu 10 (đề kiểm tra, ITMO). Tìm số dư của \(454^{225}\) khi chia cho \(16\).

Do \(454\) chia hết cho \(2\) nên \(454^4\) chia hết cho \(16\).

Suy ra \(454^{225}\) chia hết cho \(16\).