Căn nguyên thủy và ứng dụng

Giới thiệu

Chúng ta đã thấy rằng với bất kỳ số nguyên dương n và bất kỳ số nguyên a nguyên tố cùng nhau với n, cấp modulo n của a là ước của φ(n) và đặc biệt nó không thể vượt quá φ(n). Trong phần này, chúng ta quan tâm đến việc đặc trưng hóa những số n mà đạt được giới hạn này, tức là những số n mà tồn tại a sao cho gcd(a,n)=1ordn(a)=φ(n). Hãy đặt tên cho những số a như vậy.

Định nghĩa

Cho n là một số nguyên dương. Một số nguyên a được gọi là căn nguyên thủy modulo n nếu gcd(a,n)=1ordn(a)=φ(n).

Ví dụ

1 là căn nguyên thủy mod 2, 2 là căn nguyên thủy mod 3, 3 là căn nguyên thủy mod 4, 23 là căn nguyên thủy mod 5, 5 là căn nguyên thủy mod 6, ...

Tính chất

Tính chất 1

Nếu a là một căn nguyên thủy modulo n và nếu ba(modn), thì b cũng là một căn nguyên thủy modulo n.

Tính chất 2

Nếu a là một căn nguyên thủy modulo n thì {1,a,a2,...,aφ(n)1} là một hệ thặng dư thu gọn modulo n.

Hệ quả

Nếu a là một căn nguyên thủy modulo n thì với mọi số nguyên x nguyên tố cùng nhau với n, tồn tại một số nguyên dương k sao cho xak(modn).

Tính chất 3

Nếu a là căn nguyên thủy mod n thì b là căn nguyên thủy mod n khi và chỉ khi bak với gcd(k,φ(n))=1.

Tính chất 4

Cho p là số nguyên tố lẻ và a là căn nguyên thủy mod p. Khi đó nếu a là căn nguyên thủy mod p2 thì a là căn nguyên thủy mod pn với mọi n.

Tính chất 5

Mọi số nguyên tố p đều có căn nguyên thủy.

Bổ đề

Cho p là một số nguyên tố lẻ. Khi đó, với mọi ước số dương d của φ(p)=p1, có đúng φ(d) số n{1,2,...,p1} sao cho ordp(n)=d.

Hệ quả

Có đúng φ(p1)1 căn nguyên thủy modulo p.

Tính chất 6

(Định lý Gauss) Một số nguyên dương n có căn nguyên thủy khi và chỉ khi n=1,2,4,pk,2pk với p là số nguyên tố lẻ và k nguyên dương.

Ứng dụng

Bài toán 1

Cho số nguyên tố p. Tìm tất cả các số nguyên dương k sao cho Sk=1k+2k++(p1)k chia hết cho p.

Chứng minh

Do p nguyên tố nên tồn tại x là căn nguyên thủy mod p. Khi đó Sk1+xk++x(p2)k(modp) Nếu (p1)k thì Sk1+1++1p1(modp) Nếu (p1)k thì từ xk1(modp)x(p1)k1(modp) ta suy ra Skx(p1)k1xk10(modp) Vậy các số k cần tìm là tất cả các số không chia hết cho p1.

Bài toán 2

Cho p>10 là một số nguyên tố. Chứng minh rằng tồn tại các số nguyên dương m,n với p>m+n sao cho p là ước của 5m7n1.

Chứng minh

Gọi g là một căn nguyên thủy modulo p. Giả sử 5ga(modp)7gb(modp), trong đó p1>a,b (lưu ý rằng (5,p)=(7,p)=1a,bp1). Khi đó, ta có: 5b7a(modp). Nếu b>a, chọn (m,n)=(p1b,a). Ngược lại, nếu a>b, chọn (m,n)=(b,p1a). Dễ dàng kiểm tra rằng các giá trị này thỏa mãn bài toán.

Bài toán 3

Tìm tất cả các số nguyên tố p,q sao cho: α3pqα0(mod3pq) với mọi số nguyên α.

Chứng minh

Đầu tiên, ta nhận thấy rằng 3,p,q là các số nguyên tố phân biệt. Thật vậy, giả sử p=q. Khi đó: n3p2n(modp2),nZ+ Tuy nhiên, nếu n=p, ta có: p3p2p(modp2)p3p211(modp)01(modp) điều này vô lý.

Bây giờ, gọi g1,g2 lần lượt là các căn nguyên thủy modulo pq. Khi đó: g13qpg1(modp)p13pq1 Tương tự: q13pq1 Do đó, ta có: p13q1q13p1

Đặt 3q1=x(p1)3p1=y(q1) với x,yN. Giả sử p>q. Ta nhận thấy rằng 1x3.

Nếu x=1, ta có: 3q1=p13q=p điều này vô lý.

Nếu x=3, ta có: 3q1=3p3 Xét modulo 3, ta được: 20(mod3) điều này cũng vô lý.

Do đó, x=2. Khi đó: 3q1=2p23p1=y(q1) Giải hệ phương trình này để tìm q, ta được: q=2y+12y9 Ta có: 2y+12y9=1+102y9 Do đó, y=5 hoặc y=7.

Nếu y=5, thì q=11p=17.

Nếu y=7, thì q=3p=5.

Tuy nhiên, 3,p,q phải là các số nguyên tố phân biệt, nên chỉ có thể có: (p,q)=(11,17) là nghiệm duy nhất.

Bài toán 4

Giả sử rằng p>3 là một số nguyên tố. Chứng minh rằng tích các căn nguyên thủy của p nằm trong khoảng từ 1 đến p là đồng dư với 1 theo modulo p.

Chứng minh

Gọi g là một căn nguyên thủy của p. Khi đó, các căn nguyên thủy của p là các số gk với k nguyên dương thỏa mãn gcd(k,ϕ(p))=1, trong đó ϕ(p)=p1 là hàm Euler.

Tổng quát, số lượng các căn nguyên thủy của pϕ(ϕ(p))=ϕ(p1).

Các căn nguyên thủy tạo thành một tập con trong nhóm nhân modulo p. Ta có thể nhóm các căn nguyên thủy thành các cặp đối xứng (gk,gp1k), vì gp1k cũng là một căn nguyên thủy.

Tích của mỗi cặp đối xứng là: gkgp1k=gp1.gp11(modp) theo Định lý Fermat nhỏ, nên tích của mỗi cặp là đồng dư với 1 modulo p.

Cuối cùng, tích của tất cả các căn nguyên thủy của p là tích của các tích trong các cặp, tức là: các căn nguyên thủygk1(modp).

Do đó, ta đã chứng minh được rằng tích các căn nguyên thủy của p nằm trong khoảng từ 1 đến p là đồng dư với 1 theo modulo p, đpcm.

Bài toán 5

(Bulgaria 2017) Cho pq là các số nguyên tố lẻ sao cho q>p. Đặt Ak=kp1+kp2++k+1 với k{1,2,,q1}. Xác định tất cả các số dư có thể có khi tích A1A2Aq1 được chia cho q.

Chứng minh

Gọi g là một căn nguyên thủy modulo q. Khi đó, tích A1Aq1 có thể được viết lại như sau: A1Aq1=pk=1q2gpk1gk1=pk=1q2(gpk1)k=1q2(gk1)

- Nếu gcd(p,q1)=1, thì hai tích k=1q2(gpk1)k=1q2(gk1) bằng nhau và khác 0 theo mod q. Do đó, kết quả cuối cùng là p.

- Nếu pq1, thì gpq1p10(modq), dẫn đến tích bằng 0 theo mod q.

Vậy, kết quả cuối cùng là:

  • p nếu pq1,
  • 0 nếu pq1.

Bài toán 6

Cho m,n là các số nguyên dương. Chứng minh rằng tồn tại một số nguyên dương k sao cho: 2k1999(mod3m)2k2009(mod5n)

Chứng minh

Sử dụng tính chất 4, ta dễ dàng suy ra rằng 2 là một căn nguyên thủy modulo 3m và modulo 5n. Do đó, tồn tại các số nguyên dương k1,k2 sao cho: 2k11999(mod3m)2k22009(mod5n) Xét các đồng dư này theo modulo 3 và 5, ta suy ra rằng k1k2 đều là số chẵn. Định lý số dư Trung Hoa đảm bảo sự tồn tại của một số nguyên dương a sao cho: ak12(mod3m1)ak22(mod25n1) Đặt k=2a và sử dụng định lý Euler, ta thu được: 2k1999(mod3m)2k2009(mod5n) như mong muốn.

Bài toán 7

(Iran 2012) Cho p là một số nguyên tố lẻ. Chứng minh rằng tồn tại một số nguyên dương x sao cho x4x đều là các căn nguyên thủy modulo p.

Chứng minh

Chọn một căn nguyên thủy g modulo p và viết 2gk(modp) với một số nguyên dương k nào đó. Nếu chúng ta có thể tìm được một số nguyên dương a sao cho aa+2k đều nguyên tố cùng nhau với p1, thì x=ga4xga+2k(modp) sẽ là các căn nguyên thủy modulo p và chúng ta đã hoàn thành. Gọi q1,...,qs là các ước nguyên tố của p1, với q1=2. Nếu i>1 thì qi>2, do đó tồn tại ai{0,1,...,qi1} khác 0 và 2k(modqi). Đặt a1=1. Theo định lý số dư Trung Hoa, chúng ta có thể chọn một số nguyên a sao cho aai(modqi) với mọi 1is. Khi đó, theo cách xây dựng, aa+2k không chia hết cho qi với bất kỳ i nào, do đó chúng nguyên tố cùng nhau với p1. Kết quả được suy ra.

Bài toán 8

Cho a là một số nguyên dương lẻ và b là một số nguyên dương chẵn. Biết rằng gcd(a,2b1)=1. Chứng minh rằng:

a1b+2b++ab

Chứng minh

Bước 1. Nếu a=pk với p là một số nguyên tố lẻ và k là một số nguyên dương, thì kết luận đúng.

Chứng minh. Quy nạp theo k.

  • Trường hợp k=1:

Gọi g là căn nguyên thủy modulo p. Khi đó:

1b+2b++(p1)b+pbgb+g2b++g(p1)b

=gb(g(p1)b1)gb1

Tử số là bội của p. Nếu p chia hết mẫu số, thì:

pgb1p1bp2b1

Điều này mâu thuẫn, do đó:

gb(g(p1)b1)gb10(modp)

  • Giả sử kết luận đúng với k1:

Tổng 1b+2b++(pk)b chia thành hai phần: các số là bội của p và các số khác.

Gọi g là căn nguyên thủy modulo pk. Khi đó, tổng phần thứ hai:

gb+g2b++gϕ(pk)bgb(gϕ(pk)b1)gb1

Theo logic tương tự, biểu thức này bằng 0 modulo pk.

Phần thứ nhất:

pb(1b+2b++p(k1)b)

Theo trường hợp k1, phần này là bội của pb×pk1, nên tổng là bội của pk.

Bước 2. Kết luận đúng với mọi số lẻ a.

Chứng minh.

  • a=1: Hiển nhiên.
  • a>1: Giả sử a=p1e1p2e2ptet.

Với mọi i, ta có:

piei1b+2b++pieibpiei1b+2b++ab

(vì pieia).

Do các piei nguyên tố cùng nhau, ta có:

a1b+2b++ab

Và chúng ta đã hoàn thành chứng minh.

Bài toán

Tìm tất cả số nguyên tố p sao cho tồn tại a,b,c phân biệt thỏa mãn a,b,c là căn nguyên thủy mod p nhưng abc không là căn nguyên thủy mod p.

Chứng minh

Mệnh đề chỉ đúng nếu p không phải là số nguyên tố Fermat, nghĩa là p22n+1 với bất kỳ số nguyên dương n.

Đặt agx,bgy,cgz(modp) với một căn nguyên thủy g và các số nguyên x,y,z, ta thấy rằng mệnh đề tương đương với điều sau: Có tồn tại các số nguyên x,y,z sao cho gcd(x,p1)=gcd(y,p1)=gcd(z,p1)=1gcd(x+y+z,p1)>1? Tôi khẳng định rằng điều này đúng khi và chỉ khi p không phải là số nguyên tố Fermat.

Đầu tiên, giả sử p không phải là số nguyên tố Fermat. Khi đó, tồn tại một số nguyên tố lẻ q là ước của p1. Chọn x1(modq),y1(modq),z2(modq), và x,y,z1(modp1qνq(p1)) (chúng ta có thể làm được điều này nhờ Định lý Thặng dư Trung Hoa - CRT).

Khi đó, điều kiện về gcd được thỏa mãn, nhưng x+y+z0(modq), nên qgcd(x+y+z,p1), dẫn đến gcd(x+y+z,p1)>1. Do đó, điều này khả thi khi p không phải là số nguyên tố Fermat.

Ngược lại, nếu p là số nguyên tố Fermat, thì p1=22n, và điều kiện gcd tương đương với x,y,z là các số lẻ. Khi đó, x+y+z cũng là số lẻ, nên ta có gcd(x+y+z,p1)=1. Do đó, điều này không khả thi khi p là số nguyên tố Fermat.

Vì vậy, chúng ta đã đặc trưng hóa tất cả các giá trị p thỏa mãn đề bài, đpcm.

Định lý

Nếu p là một số nguyên tố lớn hơn 3Φ(p1)/(p1)>1/3, trong đó Φ là hàm phi Euler, thì p có các căn nguyên thủy liên tiếp.

Bổ đề

Nếu p là một số nguyên tố lớn hơn 3, thì có đúng một nửa số căn nguyên thủy theo modulo p sao cho số liền sau không là thặng dư toàn phương.

Chứng minh bổ đề

Gọi ξ là một căn nguyên thủy theo modulo p. Khi đó, p1p2 là hai số nguyên tố cùng nhau, do đó ξp2 cũng là một căn nguyên thủy theo modulo p.

Hơn nữa, ξξp2(modp)p>3. Vì ξ không là một thặng dư toàn phương nên từ đồng dư thức: ξ(ξp2+1)=ξp1+ξξ+1(modp), ta suy ra rằng ξ+1 không là một thặng dư toàn phương nếu và chỉ nếu ξp2+1 là một thặng dư toàn phương.

Do đó, đúng một trong hai số ξξp2 là căn nguyên thủy sao cho số đứng liền sau không là thặng dư toàn phương. Kết luận của bổ đề được suy ra bằng cách xét tất cả các cặp căn nguyên thủy (ξ,ξp2).

Chứng minh định lý

Gọi p là một số nguyên tố lớn hơn 3 thỏa mãn Φ(p1)/(p1)>1/3. Giả sử rằng không có hai căn nguyên thủy liên tiếp theo modulo p. Khi đó, theo bổ đề, một nửa trong số Φ(p1) căn nguyên thủy có số đứng liền sau là các thặng dư không toàn phương, và không căn nguyên thủy nào là thặng dư toàn phương.

Do mỗi căn nguyên thủy không là một thặng dư toàn phương, suy ra tồn tại ít nhất (3/2)Φ(p1) thặng dư không toàn phương, vượt quá tổng số thặng dư không toàn phương là (p1)/2 (do Φ(p1)/(p1)>1/3). Đây là một mâu thuẫn.

Do đó, định lý được chứng minh.

Nhận xét

Bài đăng phổ biến từ blog này

Các bài toán về thặng dư toàn phương

Các bài toán về dãy số nguyên

Các bài toán về hàm số học