Bổ đề: Mọi phương trình đồng dư modulo [TEX]p[/TEX] có bậc [TEX]n[/TEX] thì có không quá [TEX]n[/TEX] nghiệm modulo p.
Chứng minh:
Dễ thấy phương trình bậc 1 thỏa mãn.
Giả sử bổ đề đúng với [TEX]n-1[/TEX], tức mọi phương trình đồng dư modulo [TEX]p[/TEX] bậc nhỏ hơn [TEX]n[/TEX] luôn có không quá [TEX]n-1[/TEX] nghiệm modulo [TEX]p[/TEX].
Khi đó xét phương trình đồng dư modulo [TEX]p[/TEX] bậc [TEX]n[/TEX]. Ta đưa về [TEX]f(x) \equiv 0 (\mod p)[/TEX] với [TEX]f(x)[/TEX] là đa thức bậc [TEX]n[/TEX], hệ số bậc cao nhất là [TEX]a[/TEX].
Giả sử phương trình [TEX]f(x) \equiv 0 (\mod p)[/TEX] có [TEX]n+1[/TEX] nghiệm modulo [TEX]p[/TEX] phân biệt [TEX]x_0,x_1,...,x_n[/TEX]
Xét [TEX]h(x)=f(x)-a(x-x_1)(x-x_2)...(x-x_n)[/TEX].
Phương trình [TEX]h(x) \equiv 0 (\mod p)[/TEX] là phương trình đồng dư modulo [TEX]p[/TEX] bậc nhỏ hơn [TEX]n[/TEX] hoặc không có bậc.
+ Nếu [TEX]h(x) \equiv 0 (\mod p)[/TEX] là phương trình đồng dư modulo [TEX]p[/TEX] bậc nhỏ hơn [TEX]n[/TEX] thì theo giả thiết quy nạp thì phương trình đó không quá [TEX]n-1[/TEX] nghiệm modulo [TEX]p[/TEX]. Mà phương trình trên có ít nhất [TEX]n[/TEX] nghiệm modulo [TEX]p[/TEX] là [TEX]x_1,x_2,...,x_n[/TEX] nên mâu thuẫn.
+ Nếu [TEX]h(x) \equiv 0 (\mod p)[/TEX] là phương trình đồng dư modulo [TEX]p[/TEX] không có bậc thì [tex]f(x) \equiv a(x-x_1)(x-x_2)...(x-x_n)(\mod p) \forall x\Rightarrow f(x_0) \equiv a(x_0-x_1)(x_0-x_2)...(x_0-x_n) (\mod p) \Rightarrow a(x_0-x_1)(x_0-x_2)...(x_0-x_n) \equiv 0 (\mod p)[/tex](mâu thuẫn do [TEX]x_0,x_1,...,x_n[/TEX] phân biệt theo modulo [TEX]p[/TEX].
Vậy bổ đề được chứng minh.
Quay lại bài toán:
Giả sử [TEX]degP=a,deqQ=b[/TEX][tex],t=\max\left \{ a,b \right \}[/tex]
Khi đó chọn [TEX]p > t[/TEX] thì [TEX]P(x) \equiv Q(x+b_p) (\mod p)[/TEX]
Lấy dãy [TEX]p_1,p_2,...[/TEX] là các số nguyên tố lớn hơn [TEX]t[/TEX].
Ta chọn được [TEX]r \in \mathbb{Q}[/TEX] sao cho [TEX]r-b_{p_i} \vdots p_i \forall i[/TEX]
Đặt [TEX]P(x)=Q(x+r)+h(x)[/TEX] thì [TEX]h(x) \equiv 0 (\mod p_i)[/TEX] theo bổ đề.
Mà cho [TEX]i[/TEX] chạy đến vô cùng thì [TEX]h(x)=0 \Rightarrow [/TEX] đpcm.
[TẶNG BẠN] TRỌN BỘ Bí kíp học tốt 08 môn
