BITEXEDU Chuyên trang chia sẻ tài liệu, kinh nghiệm ứng dụng giải toán trên máy tính cầm tay
Bài 2: Lý thuyết số
- 21/07/2025
- 896 lượt xem
| Bài toán 1: Tìm ước nguyên tố lớn nhất của số $303265^2+30785^2+31047^2$ |
Vậy ước nguyên tố lớn nhất của số đã cho là $3089$.
| Bài toán 2: Tìm ước nguyên tố lớn nhất của số $3689^3+9478777^2$ |
Vậy ước nguyên tố lớn nhất của số đã cho là $8893$.
| Bài toán 3: Tính tổng các ước lẻ của số $21077548$ |
Phân tích ra thừa số nguyên tố và loại ước nguyên tố chẵn: 
.
Khi đó tổng các ước lẻ của số đã cho là:
Việc tính tổng các ước lẻ của số $21077548$ (tức là tổng các ước của $5269387$) như trên là cách thực hiện trực quan nhưng phức tạp. Ta có công thức sau đây để tính tổng các ước của một số nguyên sau khi đã phân tích ra thừa số nguyên tố:
Ký hiệu $\sigma (n)$ là tổng các ước của một số nguyên $n$. Ta phân tích $n$ ra thừa số nguyên tố $n=p_1^{k_1}.p_2^{k_2}.\dots.p_m^{k_m}$. Khi đó $$\boldsymbol{\sigma(n)=\displaystyle \prod_{i=1}^{m}
\dfrac{p_i^{k_i+1}-1}{p_i-1}}$$
Nếu $k_i=1$ thì dùng hằng đẳng thức $a^2-b^2$, phân số tương ứng thu gọn thành $p_i+1$.
Chẳng hạn nếu $n=a.b.c$ là tích của các thừa số nguyên tố $a, b, c$ thì
Kết quả cụ thể cho bài toán trên: 
| Tương tự 1. Tính tổng các ước lẻ của số $722311904.$ |
Kết quả: Tổng các ước lẻ của số $722311904$ là 
| Tương tự 2. Tính tổng các ước lẻ của số $71500021$ sao cho chữ số tận cùng của ước lẻ đó là $7$. |
Ta có: 
Tất cả các ước của số đã cho đều là ước lẻ và có dạng $19^a.37^b.53^c.101^d$ với $a \in \big\{ 0, 1,2 \big\}; b \in \big\{0, 1 \big\} ; c \in \big\{0,1\big\} ; d\in \big\{0,1\big\}$.
Vì $101^d$ với $d\in \big\{0,1\big\}$ luôn có chữ số đơn vị là $1$ nên ta chỉ xét bộ ba $19^a.37^b.53^c$.
Nếu $b=0$ thì $a=1, c=1$. Ta có 2 ước lẻ tận cùng bằng $7$ lần lượt ứng với $d=0, d=1$.
Nếu $b=1$ thì $a=2, c=0$ hay $a=0, c=0$. Ta có 4 ước lẻ tận cùng bằng $7$ lần lượt ứng với $d=0, d=1$.
6 ước lẻ cần tìm là $19^a.37^b.53^c.101^d$ với
$\boldsymbol{b=0, a=c=1}, $ $d=0$: $19\times 53$
$b=0, a=c=1, d=1$: $19\times 53\times 101$
$\boldsymbol{b=1, a=2, c=0}, $ $d=0$: $19^2\times 37$
$b=1, a=2, c=0, d=1$: $19^2\times 37\times 101$
$\boldsymbol{b=1, a=0, c=0}, $ $d=0$: $37$
$b=1, a=0, c=0, d=1$: $37\times 101$
Vậy tổng cần tìm là 
| Bài toán 4. Tìm số tự nhiên $n$ sao cho số $83151900^n$ có $5267025$ ước số. |
Ta có: 
. Vậy $83151900^n=2^{2n}.3^{3n}.5^{2n}.13^n.23^n.103^n$.
Chỉ quan tâm tới số ở trên lũy thừa, ta có số các ước của số $83151900^n$ là $(2n+1)(3n+1)(2n+1).(n+1).(n+1).(n+1)=(n+1)^3(2n+1)^2(3n+1)$
Theo yêu cầu bài toán ta giải phương trình $(n+1)^3(2n+1)^2(3n+1)=5267025$
. Vậy $n=8$.
| Nhận xét dành cho giáo viên: Nếu lấy $n$ nguyên dương thì vế trái là một hàm tăng nên nghiệm nguyên dương là duy nhất. |
| Bài toán 5: Tìm các ước nguyên tố của số $A = 2177^7 + 3421^7 + 5287^7$. |
Ta phân tích số $8788763$ ra thừa số nguyên tố. Máy tính Casio 880-BTG khá mạnh nhưng không thể thực hiện được công việc này trên chức năng 
của nó.
Theo phương pháp của Thầy Nguyễn Trường Chấng ta lần lượt chia số đã cho cho các số lẻ nhỏ hơn hay bằng
$\sqrt{8788763} \approx $ 
, có khoảng 1482 số lẻ như vậy.
Việc thực hiện phép chia này cũng bất khả thi, vì theo thuật toán sau đây sau khoảng hơn 800 lần bấm $\fbox{EXE}$ :
dù mỗi phép chia chỉ thực hiện khoảng 0,5 giây cũng sẽ mất 15 phút và không giám sát được quá trình.
Ở đây chúng ta sẽ sử dụng Thuật toán RHO (còn gọi là thuật toán Pollard’s rho) là một thuật toán phân tích số nguyên thành thừa số, được phát minh bởi John Pollard vào năm 1975. Chúng ta sẽ chạy thuật toán này trên bảng tính.
I. Mô tả thuật toán.
1. Chọn hàm giả ngẫu nhiên: $f(x)=x^2+1\quad (\text{mod}\ n)$.
2. Xây dựng vòng lặp
$\qquad\qquad\qquad\qquad\qquad x_0=2, y_0=2$ và
$\qquad\qquad\qquad\qquad\qquad x_m=f(x_{m-1})=x_{m-1}^2+1\quad (\text{mod}\ n )$,
$\qquad\qquad\qquad\qquad\qquad y_m=f\left(f(y_{m-1})\right)=(y_{m-1}^2+1)^2+1\quad (\text{mod}\ n )$.
3. Xây dựng vòng lặp xong ta tính $\text{UCLN}(|x_m-y_m|, n)$. Ứng với bước lặp nào mà UCLN lớn hơn 1 và nhỏ hơn $n$ thì UCLN đó là thừa số thứ nhất, thừa số thứ hai sẽ là $\dfrac{n}{\text{thừa số thứ nhất} }$.
| II. Áp dụng cho $\boldsymbol{n=8788763}$. |
Mở một bảng tính 
, nhập $x_1=x_0^2+1=5, y_1=(y_0^2+1)^2+1=26$ vào $\rm A_1, B_1$
. Gán $x=8788763$ vào biến nhớ 
.
Đưa con trỏ vào $\rm A_2$ điền công thức:
Đưa con trỏ vào $\rm C_1$ điền công thức:
(phần bị khuất là $\rm \boldsymbol{((B_1^2+1)\div x)}$, 
.
Đưa con trỏ vào $\rm B_2$ điền công thức: 
(phần bị khuất là $\rm \boldsymbol{((C_1^2+1)\div x)}$, 
Đưa con trỏ vào $\rm E_2$ điền công thức: 
.
Vòng lặp dừng lại ở bước thứ 16 và xuất ra thừa số $1697$.
Ta có: 
. Vậy $8788763=1697\times 5179$.
| Giải thích:
1. Trong cột A dòng dưới là ánh xạ (bình phương cộng 1) của dòng trên (mod 8788763). 2. Trong cột B dòng dưới là ánh xạ 2 lần của dòng trên (mod 8788763). Nhưng kết quả trung gian (ánh xạ lần đầu) quá lớn nên ánh xạ qua cột C rồi ánh xạ cột C để hoàn thành cột B. |
 |
Sở dĩ gọi là thuật toán RHO vì xét một hệ trục tọa độ $Oxy$ các điểm có tọa độ $(x_n;y_n)$ khi $n$ chạy từ $1$ đến vô cực sẽ vẽ một đồ thị hình chữ hy lạp: $\rho$ (rho). |
Thuật toán này nổi tiếng khi vào năm 1980 nó phân tích $F_8=2^{256}+1$ thành tích của hai thừa số nguyên tố $$1238926361552897 × 93461639715357977769163558199606896584051237541638188580280321$$
1. Tính tổng các ước nguyên tố của số $A=18343^3+9877^4+4233^5$.
2. Tìm tổng tất cả các ước nguyên tố của số $A = 8533^2 + 6307^3 +10759^2$.
3. Tìm tổng tất cả các ước nguyên tố của số $1994096512$.
4. Tìm tổng tất cả các ước lẻ của số $1968260028$.
5. Tìm một số $A=3^m.5^n.11^p\quad (m, n, p \in \mathbb{N})\ \text{và}\ p>1 $ biết rằng $3A$ có số ước nhiều hơn số ước của $A$ là $28$ và số $25A$ có số ước nhiều hơn số ước của $A$ là $70$.
Hướng dẫn. Giải hệ phương trình $$\left\lbrace\begin{array}{ll}(m+2)(n+1)(p+1)-(m+1)(n+1)(p+1)&=28\\
(m+1)(n+3)(p+1)-(m+1)(n+1)(p+1)&=70\end{array} \right. ⇔ \left\lbrace\begin{array}{ll}(n+1)(p+1)&=28=4.7\\
(m+1)(p+1)&=35=5.7\end{array} \right.$$
Dựa vào tích các số nguyên để tìm $m+1, n+1, p+1$. Do điều kiện $p>1$ nên không chọn $p+1=1$.
PHÂN TÍCH MỘT SỐ RA THỪA SỐ NGUYÊN TỐ
Do bộ nhớ của máy tính cầm tay có hạn nên trên bảng tính của thuật toán RHO chúng ta sử dụng 16 dòng. Nếu đến dòng 16 mà vẫn không ra kết quả, ta sẽ gán A16 vào biến nhớ A và B16 vào biến nhớ B. Sau đó nhập A và B lần lượt vào A1, B1 bảng tính sẽ được cập nhật. Lúc này nếu bài toán có kết quả thì xong, nếu vẫn không ra kết quả thì lặp lại như trên. Tuy nhiên để tránh bị lặp quá lâu ví dụ đối với số $68450159$ chúng ta có thể sử dụng Thuật toán Fermat.
|
THUẬT TOÁN FERMAT
|
|
1. Tính $x=\left[\sqrt{n} \right]+1$ (giá trị trần của $x$).
2. Tính $y=\sqrt{x+^2-n}$. Nếu $y$ là số nguyên thì $n=(x-y)(x+y)$. 2. Nếu $y$ không là số nguyên thì tăng $x$ lên 1 đơn vị và lặp lại. |
Áp dụng bằng số với $\boldsymbol{n=68450159}$.
Thực hành trên bảng tính:
Mở một bảng tính, gán số $68450159$ vào biến nhớ $x$ 
.
Nhập $\left[\sqrt{x} \right]+1$ vào A1 . Điền công thức $\sqrt{\text{A1}^2-x}$ vào B1-B10 : 
Điền công thức để tăng lên 1 đơn vị vào A2-A10 
.
Vậy $\qquad 68450159=8609\times 7951$.
About TS. Nguyễn Thái Sơn
