Hệ thặng dư đầy đủ là một trong các cơ sở quan trọng của số học. Nhờ nó, ta có thể chứng minh được dễ dàng định lý Fermat nhỏ, định lý Wilson.
Nói sơ qua về định nghĩa, với $m>1$ là số nguyên dương. Tập hợp các số nguyên $\{a_1, a_2, \ldots, a_m \}$ là hệ thặng dư đầy đủ $\pmod m$ nếu như các số đó đôi một không đồng dư với nhau theo $\pmod m$.
Trong bài viết nhỏ này, chúng ta sẽ cùng tìm hiểu một số ví dụ vận dụng hệ thặng dư đầy đủ trong việc giải các bài toán số học, tổ hợp.
Bài
1. Cho
số nguyên dương $n\ge 3$ và đa giác đều $n$ đỉnh. Trên mỗi đỉnh của đa giác,
người ta chọn điền các số nguyên dương nào đó. Tiếp theo, với mỗi đường chéo hoặc
cạnh bất kỳ, người ta viết số dư của tổng hai số được điền trên hai đầu mút của
đoạn thẳng đó khi chia cho $m=\frac{n(n-1)}{2}.$ Chứng minh rằng với mọi $n$
không là số chính phương và chia $4$ dư $0,1$ thì không tồn tại cách điền như
thế sao cho tất các các số được điền trên đường chéo và cạnh là đôi một phân biệt.
Lời
giải.
Theo giả thiết thì $m$
số điền trên cạnh, đường chéo phải lập được thành hệ thặng dư đầy đủ $\bmod m.$
Giả sử có cách điền các
số trên đa giác, trong đó có $a$ số chẵn, $b$ số lẻ với $a+b=n$. Khi đó, việc
tính tổng các số trong $n$ số đó sẽ sinh ra $ab$ số lẻ và $\frac{{{a}^{2}}+{{b}^{2}}-a-b}{2}$
số chẵn.
Vì $n\equiv 0,1\text{
}(\bmod 4)$ nên $m=\frac{n(n-1)}{2}$ là số chẵn, để có được hệ thặng dư thì
$ab=\frac{{{a}^{2}}+{{b}^{2}}-a-b}{2}\Leftrightarrow
{{(a-b)}^{2}}=a+b=n$.
Tuy nhiên, $n$ không phải là số chính phương nên điều
kiện trên không thỏa.
Bài
2.
a) Cho số nguyên tố $p$
và hai hệ thặng dư đầy đủ $\bmod p$ là $({{a}_{1}},{{a}_{2}},\ldots
,{{a}_{p}})$ và $({{b}_{1}},{{b}_{2}},\ldots ,{{b}_{p}})$.
Chứng minh rằng ${{a}_{1}}{{b}_{1}},{{a}_{2}}{{b}_{2}},\ldots
,{{a}_{p}}{{b}_{p}}$ không là hệ thặng dư đầy đủ $\bmod p.$
b) Tìm tất cả $n$ nguyên dương để tồn tại hai hệ thặng
dư đầy đủ $\bmod n$ sao cho tổng tương ứng của chúng theo chỉ số cũng là hệ thặng
dư đầy đủ mod $n.$
Lời
giải.
a) Giả sử $p|{{a}_{r}},p|{{b}_{s}}$ với $r,s\in
\{1,2,3\ldots p\}$ thì có hai trường hợp:
- Nếu $r\ne s$ thì ${{a}_{r}}{{b}_{r}},{{a}_{s}}{{b}_{s}}$
cùng chia hết cho $p$ nên không thỏa.
- Nếu $r=s$ thì có thể giả sử $r=s=p$, ta xét các số
còn lại của hệ.
Ta cũng có
$({{a}_{1}}{{b}_{1}})({{a}_{2}}{{b}_{2}})\ldots ({{a}_{p-1}}{{b}_{p-1}})=({{a}_{1}}{{a}_{2}}\ldots
{{a}_{p-1}})({{b}_{1}}{{b}_{2}}\ldots {{b}_{p-1}})\equiv {{(-1)}^{2}}=1(\bmod
p)$
theo định lý Wilson, điều này chứng tỏ các số ${{a}_{1}}{{b}_{1}},{{a}_{2}}{{b}_{2}},\ldots
,{{a}_{p}}{{b}_{p}}$ không lập được thành hệ thặng dư đầy đủ mod $p.$ (đpcm)
b) Số $n$ lẻ. Chỉ cần
xét tổng các số tương tự như việc xét tích ở trên.
Bài
3. Gọi
$P$ là tích các số nguyên tố không vượt quá $2018.$ Số nguyên dương $n$ được gọi
là tốt nếu như nó chỉ có ước nguyên tố thuộc $P$ và không tồn tại $a,d\in
{{\mathbb{Z}}^{+}}$ để $a,a+d,\ldots ,a+2018d$ đều nhỏ hơn $n$ và nguyên tố
cùng nhau với $n.$
a) Chứng minh rằng $2018P$ là số tốt.
b) Chứng minh rằng $2018P$ là số tốt lớn nhất.
Lời
giải.
a) Giả sử có $a,d\in
{{\mathbb{Z}}^{+}}$ để $a,a+d,\ldots ,a+2018d$ đều nhỏ hơn $2018P$ và nguyên tố
cùng nhau với $2018P.$ Vì $a+2018d<2018P$ nên $d<P$, chứng tỏ tồn tại số
nguyên tố $p<2018$ để $(d,p)=1.$
Khi đó, các số $a,a+d,\ldots
,(p-1)d$ lập thành hệ thặng dư đầy đủ $\bmod p$ nên sẽ có số chia hết cho $p$;
trong khi $p|2018P$, mâu thuẫn.
b) Giả sử có số tốt $m>2018P$,
chọn $a=1,d=P$ thì dễ thấy $a,d$ thỏa mãn điều kiện đề cho, mâu thuẫn.
Bài
4.
a) Cho đa thức $P(x)$ hệ
số nguyên và hai số nguyên $a,b>1$ nguyên tố cùng nhau. Giả sử khi $x\in
\mathbb{Z},$ $P(x)$ chạy qua một hệ thặng dư đầy đủ mod $a,b$. Chứng minh rằng $P(x)$
cũng chạy qua một hệ thặng dư đầy đủ mod $ab.$
b) Cho đa thức $P(x)$ hệ
số nguyên sao cho tồn tại $c\in \mathbb{Z},c>1$ để $P({{x}_{1}}),P({{x}_{2}}),\ldots
,P({{x}_{c}})$ không chia hết cho $c$ với ${{x}_{1}},{{x}_{2}},\ldots
,{{x}_{c}}$ là một hệ thặng dư đầy đủ $\bmod \text{ }c.$ Chứng minh rằng $P(x)$
không có nghiệm nguyên.
Lời
giải.
a) Giả sử có $P({{x}_{1}}) \equiv
{{a}_{1}} \pmod a,P({{x}_{2}})\equiv {{b}_{1}} \pmod b$, chọn ${{x}_{0}}$ thỏa
mãn ${{x}_{0}} \equiv {{x}_{1}} \pmod a$ và ${{x}_{0}}\equiv {{x}_{2}} \pmod b$ (thặng dư Trung Hoa). Khi đó $P({{x}_{0}})-P({{x}_{1}})$ chia hết cho $a$ hay $P({{x}_{0}})\equiv
{{a}_{1}}(\bmod a),P({{x}_{0}})\equiv {{b}_{1}}(\bmod b)$ nên
$P({{x}_{0}})\equiv
c(\bmod ab)$
với $c$ xác định theo ${{a}_{1}},{{b}_{1}}$. Cho ${{a}_{1}},{{b}_{1}}$
lần lượt chạy qua các số $\{0,1,\ldots ,a-1\},\{0,1,\ldots ,b-1\}$ thì dễ thấy $c$
sẽ chạy qua $\{0,1,\ldots ,ab-1\}$.
b) Giả sử $P(x)$ có nghiệm nguyên $x=a$ thì đặt $P(x)=(x-a)Q(x).$
Khi $x$ chạy qua một hệ
thặng dư đầy đủ $\bmod \text{ }c$ thì $x-c$ cũng thế, tức là phải có một số
chia hết cho $c$ hay $P(x)$ tương ứng cũng chia hết cho $c,$ mâu thuẫn.
Bài
5.
a) Cho số nguyên tố $p$ lẻ và với $k\in \{0,1,\ldots
,p-2\}$, đặt ${{S}_{k}}={{1}^{k}}+{{2}^{k}}+\cdots +{{(p-1)}^{k}}$. Chứng minh
rằng ${{S}_{k}}$ chia hết cho $p.$
b) Cho đa thức $P(x)$
nguyên thỏa mãn $P(0)=0,P(1)=1$ và tồn tại số nguyên tố $p$ sao cho $P(n)$ chia
$p$ dư $0$ hoặc $1$ với mọi $n\in \mathbb{Z}.$ Chứng minh rằng $\deg P\ge p-1.$
Lời
giải.
a) Do $k<p-1$ nên tồn tại $a$ nguyên để ${{a}^{k}}\ne
1 \pmod p.$ Xét
${{a}^{k}}{{S}_{k}}={{a}^{k}}+{{(2a)}^{k}}+\cdots
+{{((p-1)a)}^{k}}$.
Do $a,2a,\ldots ,(p-1)a$ lập thành hệ thặng dư thu gọn
$\bmod p$ nên
${{a}^{k}}{{S}_{k}}\equiv
{{S}_{k}}(\bmod p)$, suy ra ${{S}_{k}}\equiv 0(\bmod p).$
b) Giả sử $\deg P\le p-2$ thì ta viết $P(x)=\sum\limits_{i=0}^{n}{{{a}_{i}}{{x}^{i}}}$,
trong đó $n\le p-2.$ Theo câu a thì
$P(1)+P(2)+\cdots
+P(p-1)\equiv 0(\bmod p).$
Tuy nhiên, do $P(1)=1$ và $P(i)\equiv 0,1(\bmod p)$ nên
vế trái không chia hết cho $p,$ mâu thuẫn.
Bài
6. Tìm
tất cả các số nguyên dương $n$ sao cho tồn tại hoán vị $\{{{a}_{1}},{{a}_{2}},\ldots
,{{a}_{n}}\}$ của $\{1,2,\ldots ,n\}$ sao cho $\{{{a}_{1}}+1,{{a}_{2}}+2,\ldots
,{{a}_{n}}+n\}$ và $\{{{a}_{1}}-1,{{a}_{2}}-2,\ldots ,{{a}_{n}}-n\}$ cũng là hệ
thặng dư đầy đủ mod $n.$
Lời
giải.
Trước hết, xét hiệu \[0\equiv
\sum\limits_{i=1}^{n}{{{a}_{i}}}-\sum\limits_{i=1}^{n}{i}\equiv
\sum\limits_{i=1}^{n}{({{a}_{i}}-i)}\equiv
\sum\limits_{i=1}^{n}{i}=\frac{n(n+1)}{2}(\bmod n)\] nên $n$ lẻ. Tiếp theo, ta cũng có
$\frac{4n(n+1)(2n+1)}{6}=2\left(
\sum\limits_{i=1}^{n}{(a_{i}^{2}+{{i}^{2}})}
\right)=\sum\limits_{i=1}^{n}{\left[
{{({{a}_{i}}+i)}^{2}}+{{({{a}_{i}}-i)}^{2}} \right]}\equiv
\frac{2n(n+1)(2n+1)}{6}(\bmod n)$
nên $n$ không chia hết cho $3.$
Do đó $(n,6)=1.$ Ta chỉ cần xét ${{a}_{i}}\equiv
2i(\bmod n)$ là thỏa mãn đề bài.
Bài
7.
Có $m>1$ học sinh đứng
trên vòng tròn. Cô giáo phát kẹo cho một học sinh nào đó, coi là học sinh thứ $1$
và theo chiều kim đồng hồ, cô lần lượt phát kẹo cho học sinh thứ ${{1}^{2}}+{{2}^{2}},{{1}^{2}}+{{2}^{2}}+{{3}^{2}},\ldots
$ cứ như thế (một học sinh có thể nhận được kẹo nhiều lần, và khi đếm hết vòng
thì cô tiếp tục đếm sang vòng mới). Số $m$ nguyên dương được gọi là tốt nếu học
sinh nào cũng có kẹo sau sau hữu hạn lần phát kẹo.
a) Chứng minh rằng $m$
tốt chỉ có ước nguyên tố là $2$ hoặc $3.$
b) Tìm tất cả các số tốt.
Lời
giải.
Thứ tự của học sinh thứ $n$ được phát kẹo là $f(n)=\frac{n(n+1)(2n+1)}{6}$.
Xét số $m$ tốt thì $f(n)$
có thể chạy qua hệ thặng dư đầy đủ $\bmod m.$ Ta thấy nếu có số nguyên tố $p|m$
thì $p$ cũng tốt.
Giả sử $m$ tốt có ước nguyên tố $p$ khác $2,3.$ Khi
đó, $p\equiv 1,5(\bmod 6)$ và
$f(p+n)=\frac{(p+n)(p+n+1)(2p+2n+1)}{6}$
$=\frac{n(n+1)(2n+1)}{6}+p\left[
\frac{(p+1)(2p+1)}{6}+{{n}^{2}}+pn+n \right]$
$\equiv \frac{n(n+1)(2n+1)}{6}=f(n)\text{
}(\bmod p). $
Do đó, chỉ cần xét các số $n\in \{1,2,\ldots ,p\}$. Tuy
nhiên,
$f(p)=f(p-1)+{{p}^{2}}\equiv
f(p-1)\text{ }(\bmod p)$
nên các số $f(1),f(2),\ldots ,f(p)$ không thể lập
thành hệ thặng dư đầy đủ mod $p.$
Tiếp theo, ta chứng
minh rằng mọi số $m={{2}^{a}}{{3}^{b}}$ với $a,b\ge 0$ và không đồng thời bằng $0$
đều tốt.
Thật vậy,
Ta cần chỉ ra rằng với mọi $k\in \{0,1,\ldots
,m-1\}$ thì đều tồn tại $n$ để $m|f(n)-k$ hay
$\frac{n(n+1)(2n+1)-6k}{6}$
chia hết cho $m.$
Đặt $P(x)=2{{x}^{3}}+3{{x}^{2}}+x-6k$, cần chứng
minh tồn tại $x$ để $P(x)$ chia hết cho ${{2}^{a+1}}\cdot {{3}^{b+1}}.$
Ta có $P(0)=-6k$ chia hết cho $2$ và $3$; ngoài ra ${P}'(x)=6{{x}^{2}}+6x+1$,
không chia hết cho $2$ và $3$ nên theo bổ đề Hensel, ta luôn chọn được
$0\le
{{x}_{1}}\le {{2}^{a+1}}-1$ để ${{2}^{a+1}}|P({{x}_{1}})$;
$0\le
{{x}_{2}}\le {{3}^{b+1}}-1$ để ${{3}^{b+1}}|P({{x}_{2}})$.
Đến đây, vì $\gcd
({{2}^{a+1}},{{3}^{b+1}})=1$ nên theo thặng dư Trung Hoa, ta dễ dàng chọn được ${{x}_{0}}$
để $P({{x}_{0}})$ chia hết cho ${{2}^{a+1}}\cdot {{3}^{b+1}}.$
Vậy tất cả các số tốt cần
tìm là $m={{2}^{a}}{{3}^{b}}$ với $a,b\ge 0$ và $a,b$ không đồng thời bằng $0$.
