Đa thức và Hệ thặng dư đầy đủ

2021/02/09 15:59

#toán #vấn đề mở #thặng dư #đa thức #số học

Bài toán: Với một đa thức P(x)Z[x]P(x) \in \mathbb{Z}[x] bất kì. Khi nào thì {P(0),P(1)P(p1)}\left \{ P(0),P(1)\cdots P(p-1) \right \} tạo thành một hệ thặng dư đầy đủ module pp? Tìm tất cả các đa thức như vậy.

Lời giải cho bài toán với P(x)=xnP(x) = x^n.

– Con Heo –

Một số kiến thức

  1. Đa thức
  2. Đồng dư và hệ thặng dư đầy đủ
  3. Định lý Fermat nhỏ
  4. Định lý Wilson
  5. Định lý Lagrange về đa thức

Một số định nghĩa

Cho đa thức P(x)Z[x]P(x) \in \mathbb{Z}[x] và số nguyên tố pp.

  1. Ta định nghĩa P(x)P(x)đầy đủ nếu tập S={P(x)xN,0xp1}S = \left \{P(x)|x\in \mathbb{N}, 0 \le x \le p-1 \right \} là một hệ thặng dư đầy đủ module pp.
  2. Ta định nghĩa p[x]p[x] là tập các đa thức hệ số nguyên có bậc p1\le p-1 và các hệ số thuộc [0,p1]\left [ 0,p-1 \right ].

Áp dụng định lý Fermat nhỏ, ta có thể đưa các đơn thức có bậc p\ge p về các đơn thức có bậc p1\le p-1 theo module pp. Ngoài ra, hệ số của P(x)P(x) cũng có thể rút gọn theo module pp. Đa thức sau khi được thu gọn được gọi là tương ứng với P(x)P(x) theo module pp, kí hiệu P(x)\overline{P}(x). Do vậy từ việc xét các đa thức trên p[x]p[x] thì ta suy ra được các đa thức trên Z[x]\mathbb{Z}[x].

Một số kết quả

Cho đa thức P(x),Q(x)Z[x]P(x), Q(x) \in \mathbb{Z}[x] và số nguyên tố pp.

Kết quả 1. Nếu P(x)P(x) đầy đủ module pp thì với aZ\forall a \in \mathbb{Z} luôn tồn tại x0Zx_{0} \in \mathbb{Z} để P(x0)a(modp)P(x_{0}) \equiv a (mod p).

Kết quả 2. Nếu P(x)P(x) đầy đủ module pp thì với a,bZ,a≢b(modp)a,b \in \mathbb{Z}, a \not\equiv b (mod p) thì P(a)≢P(b)(modp)P(a) \not\equiv P(b) (mod p).

Hệ quả 1. Nếu P(x)P(x) đầy đủ module ppa,bZ\exists a,b \in \mathbb{Z} để P(a)P(b)(modp)P(a) \equiv P(b) (mod p) thì ab(modp)a \equiv b (mod p).

Kết quả 3. P(x)P(x) đầy đủ module pp     \iff kP(x+m)+akP(x+m) + a đầy đủ module pp, aZ,(k,p)=1a \in \mathbb{Z},(k,p)=1.

Kết quả này dễ chứng minh.

Kết quả 4.1. P(x),Q(x)P(x), Q(x) đầy đủ module pp     \implies P(Q(x))P(Q(x)) đầy đủ module pp.

Chứng minh. Chứng minh phản chứng.

Giả sử P(Q(x))P(Q(x)) không đầy đủ module pp. Khi đó a,bZ,a≢b(modp)\exists a,b \in \mathbb{Z}, a \not\equiv b (mod p)P(Q(a))P(Q(b))(modp)P(Q(a)) \equiv P(Q(b)) (mod p).

P(x),Q(x)P(x), Q(x) đầy đủ module pp, từ Hệ quả 1.

    \implies Q(a)Q(b)(modp)Q(a) \equiv Q(b) (mod p)

    \implies ab(modp)a \equiv b (mod p) (mâu thuẫn vì a≢b(modp)a \not\equiv b (mod p)).

Vậy Kết quả 4.1. được chứng minh.

Kết quả 4.2. P(Q(x))P(Q(x)) đầy đủ module pp     \implies P(x),Q(x)P(x), Q(x) đầy đủ module pp.

Chứng minh. Chứng minh phản chứng.

Giả sử Q(x)Q(x) không đầy đủ module pp. Khi đó a,bZ,a≢b(modp)\exists a,b \in \mathbb{Z}, a \not\equiv b (mod p)Q(a)Q(b)(modp)Q(a) \equiv Q(b) (mod p).

    \implies P(Q(a))P(Q(b))(modp)P(Q(a)) \equiv P(Q(b)) (mod p).

P(Q(x))P(Q(x)) đầy đủ module pp. Theo Hệ quả 1.

    \implies ab(modp)a \equiv b (mod p). (vô lý vì a≢b(modp)a \not\equiv b (mod p))

Do đó Q(x)Q(x) phải đầy đủ module pp.

Giả sử P(x)P(x) không đầy đủ module pp. Khi đó a,bZ,a≢b(modp)\exists a,b \in \mathbb{Z}, a \not\equiv b (mod p)P(a)P(b)(modp)P(a) \equiv P(b) (mod p).

Q(x)Q(x) đầy đủ module pp, áp dụng Kết quả 1. suy ra a0,b0Z\exists a_{0},b_{0} \in \mathbb{Z} để Q(a0)a,Q(b0)b(modp)Q(a_{0}) \equiv a, Q(b_{0}) \equiv b (mod p).

    \implies P(Q(a0))P(Q(b0))(modp)P(Q(a_{0})) \equiv P(Q(b_{0})) (mod p).

P(Q(x))P(Q(x)) đầy đủ module pp. Theo Hệ quả 1.

    \implies a0b0(modp)a_{0} \equiv b_{0} (mod p).

    \implies Q(a0)Q(b0)(modp)Q(a_{0}) \equiv Q(b_{0}) (mod p).

    \implies ab(modp)a \equiv b (mod p). (vô lý vì a≢b(modp)a \not\equiv b (mod p))

Vậy Kết quả 4.2. được chứng minh.

Hệ quả 2. P(x)P(x) đầy đủ module pp     \iff Pn(x)P_{n}(x) đầy đủ module pp (nN)(n \in \mathbb{N}*) với Pn(x)=P(P(P(x)))nxP_{n}(x)=\underbrace{P(P(\cdots P(x)))}_{n} \forall x.

Kết quả 4.3. Nếu P(x)P(x) hoặc Q(x)Q(x) không đầy đủ module pp thì P(Q(x))P(Q(x)) không đầy đủ module pp.

Đây là hệ quả trực tiếp của Kết quả 4.2..

Kết quả 4.4. Nếu P(Q(x))P(Q(x)) không đầy đủ module pp thì P(x)P(x) hoặc Q(x)Q(x) không đầy đủ module pp.

Đây là hệ quả trực tiếp của Kết quả 4.1..

Kết quả 5. (tham khảo Turkey MO 2000) Hệ số của xp1x^{p-1} trong P(x)\overline{P}(x) đầy đủ module pp00.

Chứng minh tham khảo Turkey MO 2000.

Kết quả 6. Với P(x),Q(x)p[x]P(x), Q(x) \in p[x]. P(x)Q(x)(modp)xP(x)Q(x)P(x) \equiv Q(x) (mod p) \forall x \Leftrightarrow P(x) \equiv Q(x).

Chứng minh. Xét G(x)=P(x)Q(x)G(x)=P(x)-Q(x).

P(x),Q(x)p[x]P(x), Q(x) \in p[x] nên G(x)p[x]G(x) \in p[x]. Do đó, degG(x)p1deg G(x) \le p-1.

Mặt khác, G(x)p,xZG(x) \vdots p, \forall x \in \mathbb{Z}.

Áp dụng định lý Lagrange về đa thức, ta có G(x)0(modp)G(x) \equiv 0 (mod p). Mà G(x)p[x]G(x) \in p[x] nên G(x)0G(x) \equiv 0.

Suy ra P(x)Q(x)P(x) \equiv Q(x).

Vậy Kết quả 6. được chứng minh.

Hệ quả 3. P(x)≢Q(x)P(x) \not\equiv Q(x) thì x0,P(x0)Q(x0)̸p\exists x_{0}, P(x_{0})-Q(x_{0}) \not\vdots p.

Kết quả 7.p!p! đa thức P(x)P(x) đầy đủ module pp trên p[x]p[x].

Chứng minh. Xét dãy số có pp phần tử (dn)n=0(d_{n})_{n=0} {0dnp1dnP(n)(modp),0np1\left\{\begin{matrix} 0 \le d_{n}\le p-1\\ d_{n}\equiv P(n) (mod p) \end{matrix}\right., 0 \le n \le p-1. Gọi DD là tập các dãy số (dn)n=0(d_{n})_{n=0}pp phần tử mà d0,d1dp1d_{0},d_{1}\cdots d_{p-1} là một hoán vị của 0,1p10,1\cdots p-1\mho là tập các đa thức đầy đủ trên p[x]p[x].

Xét S:DS:\mho \rightarrow D

P(dn)n=0{0dnp1dnP(n)(modp),0np1P \mapsto (d_{n})_{n=0} \left\{\begin{matrix} 0 \le d_{n}\le p-1\\ d_{n}\equiv P(n) (mod p) \end{matrix}\right., 0 \le n \le p-1 .

Dễ thấy SS là một ánh xạ. Ta chứng minh SS là một song ánh.

Chứng minh SS đơn ánh. Hệ quả của Kết quả 6..

Chứng minh SS toàn ánh. Xét một dãy số dnDd_{n} \in D

và đa thức TTdegTp1deg T \le p-1T(0)=d0,T(1)=d1,T(p1)=dp1T(0)=d_{0},T(1)=d_{1}\cdots,T(p-1)=d_{p-1}.

Khi đó TT là duy nhất và T(x)Z,xZT(x) \in \mathbb{Z}, \forall x \in \mathbb{Z}. Áp dụng công thức nội suy Lagrange, ta có:

T(x)=i=0p1dijixjijT(x)=\sum_{i=0}^{p-1}d_{i}\prod_{j\neq i}^{}\frac{x-j}{i-j}

Suy ra T(x)Q[x]T(x) \in \mathbb{Q}[x].

Mặt khác,

(p1)!T(x)=i=0p1di(p1)!jixjij=i=0p1di(p1)!ji(xj)i!(p1i)!(1)p1i=i=0p1di(1)p1i(p1i)ji(xj)(p-1)!T(x)=\sum_{i=0}^{p-1}d_{i}(p-1)!\prod_{j\neq i}^{}\frac{x-j}{i-j}=\sum_{i=0}^{p-1}d_{i}\frac{(p-1)!\prod_{j\neq i}^{}(x-j)}{i!(p-1-i)!(-1)^{p-1-i}}=\sum_{i=0}^{p-1}d_{i}(-1)^{p-1-i}\binom{p-1}{i}\prod_{j\neq i}^{}(x-j)

Suy ra (p1)!TZ[x]-(p-1)!T \in \mathbb{Z}[x].

T(x)Z,xZT(x) \in \mathbb{Z}, \forall x \in \mathbb{Z} nên theo định lý Wilson, (p1)!1(modp)(p-1)! \equiv -1 (mod p) suy ra

(p1)!T(n)T(n)=dn(modp),0np1-(p-1)!T(n) \equiv T(n) = d_{n} (mod p), 0 \le n \le p-1.

Suy ra P=(p1)!TP=\overline{-(p-1)!T} là đa thức thuộc \mho có ảnh là dnd_{n} qua ánh xạ SS.

Do đó SS toàn ánh.

Như vậy, SS song ánh.

Suy ra, =D=p!|\mho|=|D|=p!.

Vậy Kết quả 7. được chứng minh.

Kết quả 8. P(x)P(x) đầy đủ module pp thì n\exists n để Pn(x)=x\overline{P_{n}}(x) = x module pp.

Chứng minh. Xét các đa thức P2,P3P_{2},P_{3}\cdots, theo nguyên tắc Dirichlet, a,bN,ab\exists a, b \in \mathbb{N},a \neq b sao cho Pa(x)Pb(x)(modp),xZP_{a}(x)\equiv P_{b}(x) (mod p),\forall x \in \mathbb{Z}.

Hay P(Pa1(x))P(Pb1(x))(modp),xZP(P_{a-1}(x)) \equiv P(P_{b-1}(x)) (mod p),\forall x \in \mathbb{Z}.

PP đầy đủ module pp nên theo Hệ quả 1.

Pa1(x)Pb1(x)(modp),xZP_{a-1}(x) \equiv P_{b-1}(x) (mod p),\forall x \in \mathbb{Z}.

Sau một hữu hạn lần. ta có P(x)Pn+1(x)(modp),xZ(nN)P(x) \equiv P_{n+1}(x) (mod p),\forall x \in \mathbb{Z} (n \in \mathbb{N}*).

    \implies xPn(x)(modp),xZx \equiv P_{n}(x) (mod p),\forall x \in \mathbb{Z} hay Pn(x)=x\overline{P_{n}}(x)=x module pp.

Vậy Kết quả 8. được chứng minh.

Bài toán liên quan (không xét ở đây) (Iran TST 2012) Cho số nguyên tố pp, p>2p>2. Ta gọi một đa thức hệ số nguyên

P(x)=anxn+...+a0P(x)=a_{n} x^n +...+a_{0}

kk-thặng dư nếu i>0p1iaik(modp)\sum_{\begin{matrix} i>0\\p-1|i \end{matrix}}^{}a_{i} \equiv k (mod p).

Chứng minh rằng tập {P(0),P(1)P(p1)}\left \{ P(0),P(1)\cdots P(p-1) \right \} là một hệ thặng dư đầy đủ module pp khi và chỉ khi các đa thức P(x),P(x)2,P(x)p2P(x), P(x)^2,\cdots P(x)^{p-2}00-thặng dư và P(x)p1P(x)^{p-1}11-thặng dư.

P(x)=xnP(x)=x^n

Ta chứng minh được kết quả sau

Cho pp là số nguyên tố, với nn là số tự nhiên bất kì ta có: xnx^n đầy đủ module pp \Leftrightarrow (n,p1)=1(n,p-1)=1

Chứng minh.

(    )(\implies) xnx^n đầy đủ module pp \Longrightarrow (n,p1)=1(n,p-1)=1.

Dễ thấy trường hợp p=2p=2 đúng.

Trường hợp p>2p>2

Khi np1n \vdots p-1 thì theo định lý Fermat nhỏ, xnx^n không đầy đủ module pp.

Khi n̸p1n \not\vdots p-1

Với n>p1n > p-1, theo định lý Fermat nhỏ, xnxn(modp),nn(modp1),1n<p1x^n \equiv x^{n'} (mod p), n' \equiv n (mod p-1), 1\le n' <p-1. Như vậy ta chỉ xét trường hợp np1n \le p-1.

Với np1n \le p-1

Chứng minh phản chứng, giả sử (n,p1)=d>1(n,p-1) = d >1.

Đặt P(x)=xnP(x) = x^n.

P(1)P(xp1d),x̸pP(1)\equiv P(x^{\frac{p-1}{d}}), \forall x \not\vdots p.

Do P(x)P(x) đầy đủ module pp nên xp1d1(modp),x̸px^{\frac{p-1}{d}} \equiv 1 (mod p), \forall x \not\vdots p. (vô lý vì khi đó theo Kết quả 6., xp1dxp1)x^{\frac{p-1}{d}} \equiv x^{p-1})

Vậy chiều thuận được chứng minh.

()( \Longleftarrow) (n,p1)=1xn(n,p-1) =1 \Longrightarrow x^n đầy đủ module pp.

Đặt P(x)=xnP(x) = x^n.

Do (n,p1)=1(n,p-1)=1 nên k\exists k để nk1n^k \equiv 1 (mod(mod p1)p-1).

Định lý Fermat nhỏ     \implies Pk(x)=xnkx(modp)P_{k}(x)=x^{n^k} \equiv x (mod p).

xx đầy đủ module pp nên Pk(x)P_{k}(x) đầy đủ module pp. Theo Hệ quả 2. thì ta có P(x)P(x) cũng đầy đủ module pp.

Chiều đảo được chứng minh.

Vậy bài toán được chứng minh.

Lưu ý. Sử dụng bài toán Iran TST 2012 cũng chứng minh được.

Tìm tất cả các đa thức đầy đủ module pp

Về lý thuyết, với mỗi hoán vị của {0,1p1}\left \{ 0,1\cdots p-1 \right \} theo như cách áp dụng công thức nội suy Lagrange như ở chứng minh. Kết quả 7., ta có thể xác định được đa thức tương ứng và từ đó xác định được tất cả các đa thức đầy đủ module pp.

Với đa thức dạng xnx^n thì đa thức đầy đủ module pp     \iff (n,p1)=1(n,p-1)=1.

Vậy với các đa thức dạng xn+xmx^n+x^m hay những đa thức gồm nhiều đơn thức nữa hơn thì sao?

C.H đã xác định được (p1)p(2φ(p1)1)(p-1)p(2\varphi (p-1)-1) đa thức đầy đủ module pp.

Đó là các đa thức có dạng P(x)=axd+bP(x)=a x^d +b với (a,p)=1,(d,p1)=1(a,p)=1,(d,p-1)=1

và các đa thức P(x+m)amdP(x+m) - a m^d với d>1,m{1p1}d>1,m\in\left \{ 1\cdots p-1 \right \} cũng đầy đủ module pp và đôi một phân biệt cùng với các đa thức có dạng như P(x)P(x).

Quay trở về Blog