1. Các tính chất chia hết về modulo
Tính chất chia hết liên quan đến modulo là những nguyên tắc cơ bản khi làm việc với phép toán chia lấy dư
(modulo).
Tính chất 1: Phép chia hết
- Nếu \( a \mod n = 0 \), nghĩa là \( a \) chia hết cho \( n \).
Ví dụ: \( 10 \mod 5 = 0 \), do đó 10 chia hết cho 5.
Tính chất 2: Đồng dư và chia hết
- Nếu \( a \equiv b \ (\text{mod}\ n) \), thì \( a - b \) chia hết cho \( n \).
Ví dụ: \( 27 \equiv 7 \ (\text{mod}\ 10) \), vì \( 27 - 7 = 20 \) và 20 chia hết cho 10.
Tính chất 3: Phép cộng modulo
- \( (a + b) \mod n = ((a \mod n) + (b \mod n)) \mod n \)
Ví dụ: \( (12 + 15) \mod 7 = ((12 \mod 7) + (15 \mod 7)) \mod 7 = (5 + 1) \mod 7 = 6 \).
Tính chất 4: Phép trừ modulo
- \( (a - b) \mod n = ((a \mod n) - (b \mod n) + n) \mod n \)
Ví dụ: \( (12 - 15) \mod 7 = ((12 \mod 7) - (15 \mod 7) + 7) \mod 7 = (5 - 1 + 7) \mod 7 = 11 \mod 7 = 4 \).
Tính chất 5: Phép nhân modulo
- \( (a \times b) \mod n = ((a \mod n) \times (b \mod n)) \mod n \)
Ví dụ: \( (12 \times 15) \mod 7 = ((12 \mod 7) \times (15 \mod 7)) \mod 7 = (5 \times 1) \mod 7 = 5 \).
Tính chất 6: Phép lũy thừa modulo
- \( (a^b) \mod n = ((a \mod n)^b) \mod n \)
Ví dụ: \( (2^5) \mod 3 = ((2 \mod 3)^5) \mod 3 = 2^5 \mod 3 = 32 \mod 3 = 2 \).
2. Định lý Fermat nhỏ (Fermat's Little Theorem)
Nếu \( p \) là một số nguyên tố và \( a \) là một số nguyên sao cho \( p \) không chia hết cho \( a \), thì:
\[
a^{p-1} \equiv 1 \ (\text{mod}\ p)
\]
Ví dụ: Giả sử \( a = 2 \) và \( p = 7 \), ta có:
\[
2^{7-1} \equiv 1 \ (\text{mod}\ 7) \quad \text{hay} \quad 2^6 \equiv 1 \ (\text{mod}\ 7)
\]
3. Định lý Euler (Euler's Theorem)
Nếu \( n \) và \( a \) là hai số nguyên nguyên tố cùng nhau (có ước chung lớn nhất là 1), thì:
\[
a^{\phi(n)} \equiv 1 \ (\text{mod}\ n)
\]
Ví dụ: \( a = 3 \) và \( n = 10 \), \( \phi(10) = 4 \), do đó:
\[
3^4 \equiv 1 \ (\text{mod}\ 10) \quad \text{hay} \quad 81 \equiv 1 \ (\text{mod}\ 10)
\]
4. Tính \( k \) chữ số đầu tiên của lũy thừa lớn
Để tính \( k \) chữ số đầu tiên của một số rất lớn, ta có thể sử dụng phương pháp dựa vào logarit. Giả sử
cần tính \( k \) chữ số đầu tiên của \( a^b \):
-
Tính tổng số chữ số của \( a^b \) bằng công thức:
\[
\text{Số chữ số} = \lfloor b \times \log_{10}(a) \rfloor + 1
\]
-
Để tìm \( k \) chữ số đầu tiên của \( a^b \), sử dụng công thức:
\[
k \text{ chữ số đầu} = \lfloor 10^{b \times (\log_{10}(a) - \lfloor b \times \log_{10}(a) \rfloor)}
\rfloor
\]
Ví dụ: Tính 5 chữ số đầu tiên của \( 2^{1000} \).
- Tính tổng số chữ số của \( 2^{1000} \):
\[
\lfloor 1000 \times \log_{10}(2) \rfloor + 1 = \lfloor 1000 \times 0.3010 \rfloor + 1 = 301 + 1 = 302
\]
- Tìm 5 chữ số đầu tiên:
\[
10^{1000 \times (\log_{10}(2) - \lfloor 1000 \times \log_{10}(2) \rfloor)} = \lfloor 10^{0.3010} \rfloor =
19950
\]
Vậy 5 chữ số đầu tiên của \( 2^{1000} \) là 19950.