Chưa có bài trả lời

[nhungvienkimcuong]

Một dạng toán liên quan tới số square-free

 

Trong bài viết này kí hiệu $\mathbb{P}$ là tập hợp các số nguyên tố.

1. Lí thuyết
Trong xuyên suốt bài viết, đa số các bài toán đều được thực hiện dựa trên ý tưởng, kết hợp với các tính chất nêu dưới đây.

Ý tưởng

Để chứng minh rằng tồn tại vô hạn số nguyên dương $n$ thỏa mãn mệnh đề $\mathcal{P}$ ta sẽ làm hai bước sau:

1. Chứng minh số phần tử thuộc tập hợp $\{1,2,\dots,N\}$ không thỏa mãn mệnh đề $\mathcal{P}$ luôn nhỏ hơn hoặc bằng $a(N)$.
2. Chứng minh $a(N)<N$ với $N$ đủ lớn.

 

Tính chất 1. $$\sum_{p\in \mathbb{P}} \frac{1}{p^2} <\frac{1}{2}.$$

Chứng minh.

Theo đẳng thức Euler (bài toán Basel) ta có $\sum_{n\in \mathbb{N}^*}\frac{1}{n^2}=\frac{\pi^2}{6}$. Điều này dẫn đến
\[\sum_{n\ \text{lẻ}}\frac{1}{n^2}=\sum_{n\in \mathbb{N}^*}\frac{1}{n^2}-\sum_{n\ \text{chẵn}}\frac{1}{n^2}=\frac{3}{4}\sum_{n\in \mathbb{N}^*}\frac{1}{n^2}=\frac{3}{4}\cdot\frac{\pi^2}{6}<\frac{5}{4}\]
nhờ $\pi^2<10$. Do đó
\[\sum_{p\in \mathbb{P}}\frac{1}{p^2}<-\frac{1}{1^2}+\frac{1}{2^2}+\sum_{n\ \text{lẻ}}\frac{1}{n^2}<\frac{1}{2}.\]

Tính chất 2. Với mỗi số thực dương $x$, kí hiệu số các số nguyên không vượt quá $x$ là $\pi(x)$. Khi đó $\pi(x)\sim \frac{x}{\ln x}$, hệ quả là
\[\lim_{x\to \infty}\frac{\pi(x)}{x}=0.\]
2. Ví dụ minh họa

Ví dụ 1

Cho số nguyên dương $n$. Chứng minh rằng nếu chọn $n$ số bất kì từ $2n$ số nguyên dương đầu tiên thì luôn tồn tại số square-free trong $n$ số được chọn.

Lời giải.

Với mỗi số nguyên tố $p$, ta thấy rằng có $\left\lfloor\frac{2n}{p^2}\right\rfloor$ số chia hết cho $p^2$ trong đoạn $[1,2n]$, do đó các số này không phải số square-free. Vậy số các số không phải số square-free và nằm trong đoạn $[1,2n]$ sẽ không vượt quá $S$ trong đó
\[S=\sum_{p\in \mathbb{P}}\left\lfloor\dfrac{2n}{p^2}\right\rfloor \le 2n\sum_{p\in \mathbb{P}}\frac{1}{p^2}<n\]
Vậy sẽ có nhiền hơn $n$ số square-free trong $2n$ số đầu tiên nên ta có được điều cần chứng minh.
 

Ví dụ 2 (Chọn đội tuyển Trung Quốc 2015)
Chứng minh rằng tồn tại vô hạn $n$ nguyên dương sao cho $n^2+1$ là số square-free.

Lời giải.

$\bullet$ Chặn trên số các số thuộc đoạn $[1,N]$ không thỏa đề.

Gọi $p$ là số nguyên tố bất kì, đầu tiên ta có nhận xét rằng phương trình đồng dư $x^2+1\equiv 0\pmod{p^2}$ có tối đa hai nghiệm. Do đó với $N$ là số nguyên dương nào đó thì có tối đa $2\left \lceil \frac{N}{p^2} \right \rceil$ số $n$ thuộc đoạn $[1,N]$ sao cho $p^2\mid n^2+1$. Các số vừa nêu không phải số square-free, vậy các số thuộc đoạn $[1,N]$ không thỏa đề không vượt quá
\[\sum_{p\in \mathbb{P}}2\left \lceil \frac{N}{p^2} \right \rceil\le 2\sum_{p\in \mathbb{P}}\left(\frac{N}{p^2}+1\right)=N\left(2\sum_{p\in \mathbb{P}}\frac{1}{p^2}+\frac{2\pi(N)}{N}\right).\]

$\bullet$ Chứng tỏ $\sum_{p\in \mathbb{P}}2\left \lceil \frac{N}{p^2} \right \rceil<N$ với $N$ đủ lớn.

Dễ thấy chuỗi $\sum_{p\in \mathbb{P}}\frac{1}{p^2}$ hội tụ về một số thực dương $\xi$, theo tính chất 1 thì $2\xi<1$. Theo tính chất 2 ta thấy rằng với $N$ đủ lớn thì
\[\frac{\pi(N)}{N}<\frac{1-2\xi}{2}\implies 2\sum_{p\in \mathbb{P}}\frac{1}{p^2}+\frac{2\pi(N)}{N}<1.\]

Vậy ta đã chứng minh được tồn tại vô hạn $N$ sao cho

$$\#\Big\{n\in [1,N]: n^2+1\ \text{không phải số square-free}\Big\}\le \sum_{p\in \mathbb{P}}2\left \lceil \frac{N}{p^2} \right \rceil<N.$$
Từ đây suy ra tồn tại vô hạn $n$ nguyên dương thỏa đề.
 

Ví dụ 3 (IMC 2013)
Tồn tại hay không tập $M$ chứa vô hạn số nguyên dương sao cho với mọi $a,b\in M$ mà $a\neq b$ thì $a+b$ là số square-free?

Lời giải.
Câu trả lời là có, ta sẽ xây dựng dãy $m_1<m_2<m_3<\dots$ sao cho $m_i+m_j$ là số square-free với mọi $i\neq j$. Đầu tiên ta chọn $m_1=1,m_2=2$ và giả sử đã chọn được $k$ số, bước tiếp theo ta sẽ chọn $m_{k+1}$.
Chọn $m_{k+1}=A^2u+1$ trong đó $A=(m_k+2k)!$ và $u$ sẽ chọn sau, khi đó $m_{k+1}>m_k$. Ta sẽ chọn $u$ phù hợp ($A^2u+1+m_i$ là số square-free với mọi $i=\overline{1,k}$) trong đoạn $[1,N]$ với $N$ là số nguyên dương cực lớn nào đó bằng cách đếm số giá trị $u$ không thích hợp.

$\bullet$ Ta sẽ chứng minh rằng số các giá trị $u$ không phù hợp nhỏ hơn $\frac{N}{2}+k\sqrt{N(A^2+1)}$.

Cố định $i$, xét số nguyên tố $p$ thỏa $p^2\mid A^2u+1+m_i$. Nếu $p\le 2k$ thì mâu thuẫn vì $p\mid A$, do đó $p>2k$. Ngoài ra $p^2\le A^2u+1+m_i<N(A^2+1)$, do vậy $2k<p<\sqrt{N(A^2+1)}$. Có nhiều nhất $\left \lceil \frac{N}{p^2} \right \rceil$ giá trị $u$ sao cho $p^2\mid A^2u+1+m_i$. Vậy số giá trị $u$ không thích hợp ($A^2u+1+m_i$ không phải số square-free với $i$ nào đó) không vượt quá
\begin{align*}
\sum_{i=1}^k\sum_{2k<p<\sqrt{N(A^2+1)}}\left \lceil \frac{N}{p^2} \right \rceil&\le k\sum_{2k<p<\sqrt{N(A^2+1)}}\left(\frac{N}{p^2}+1 \right)\\
&<kN\sum_{p>2k}\left(\frac{1}{p-1}-\frac{1}{p}\right)+k\sqrt{N(A^2+1)}\\
&<\frac{N}{2}+k\sqrt{N(A^2+1)}
\end{align*}

Hoàn toàn có thể chọn $N$ đủ lớn sao cho $\frac{N}{2}+k\sqrt{N(A^2+1)}<N$, do vậy tồn tại $u$ phù hợp.

 

3. Bài tập
Bài 1 (PEN)
Chứng minh rằng mọi số nguyên lớn hơn $1$ đều có thể viết dưới dạng tổng của hai số square-free.

Bài 2 (Vesselin Dimitrov)
Chứng minh rằng tồn tại vô hạn $n$ nguyên dương sao cho $\frac{1}{2}n(n+1)(n+2)(n^2+1)$ là số square-free.

Bài 3 (Cuộc thi nhóm học sinh Iran 2020)
Cho các số nguyên dương $a,b,c,d$ thỏa mãn $\gcd(a,b)=\gcd(c,d)=1$. Chứng minh rằng tồn tại vô hạn $n$ sao cho cả $x_n$ và $y_n$ đều là số square-free, trong đó
\[x_n=an+b\quad \text{và}\quad y_n=cn+d,\quad \forall n\in \mathbb{N^*}.\]
Bài 4 (Khu vực Đông Nam Trung Quốc 2020)
Sắp xếp các số square-free theo thứ tự tăng dần thu được dãy $a_1,\ a_2,\ a_3,\ \dots$. Chứng minh rằng tồn tại vô hạn $n$ nguyên dương sao cho
$$a_{n+1}-a_n=2020.$$

 

Fille bài viết:  mot dang toan so square-free.pdf   202.33K   160 Số lần tải

Bài viết đã được chỉnh sửa nội dung bởi nhungvienkimcuong: 31-07-2022 - 15:14