Myagmarjaral

Үлдэгдлийн тухай Хятадын сонгодог теорем

Хятадууд манай тооллын эхээр, тухайлбал I зуунд Сунь Цзу гэдэг математикчийн лавтай мэддэг байсан "Үлдэгдлийн тухай Хятадын теорем" зүй ёсоор ордог. Энэхүү теоремийн гоё сайхныг уг теоремийн томъёолол болон баталгааг ойлгож мэдэх төдийхнөөр бус түүнийг хэрэглэж үзсэнээр мэдэж болно. Эхлээд "Үлдэгдлийн тухай Хятадын теорем"-д ашиглаглах тодорхойлолтуудыг авч үзье.

ТОДОРХОЙЛОЛТ

ТОДОРХОЙЛОЛТ 1. R нь (+) ба (*) гэсэн хоёр үйлдэлтэй олонлог бөгөөд (R,+) нь абелийн бүлэг, (*) үйлдэл нь ассоциатив хуульд захирагдах, (+) ба (*) үйлдлүүд нь баруун, зүүн дистрибутив хуулиар холбогдсон байвал түүнийг цагираг гэж нэрлээд (R, +, *) гэж тэмдэглэдэг. Хэрэв(R∋ ∀x,y)(xy=yx) байвал R-ийг коммутатив цагираг, хэрэв R∋ ∃e,R∋ ∀a,ae=ea=a байвал R-ийг нэгжтэй цагираг гэдэг.

ТОДОРХОЙЛОЛТ 2 Н ба R-ийн дэд цагираг байг. Хэрэв Н дэд цагирагийн бүх элементийн баруун (зүүн) талаас нь R-ийн дурын элементээр үржүүлэхэд дахиад Н-ын элемент гардаг бол Н-ыг R цагирагийн баруун (зүүн) идеал гэдэг. Хэрэв Н дэд цагираг баруун ч зүүн ч идеал болдог бол түүнийг хоёр талт идеал гэнэ.

ТЕОРЕМ

ТЕОРЕМ (Үлдэгдлийн тухай Хятадын теорем). R нь нэгжтэй коммутатив цагираг, R_1, R_2,..., R_n нь энэхүү цагиргийн i≠j үед R_i+R_j=R байх идеалууд бол R цагиргийн дурын x_1,x_2,…,x_n элементүүдийн хувьд x≡ x_i (mod R_i ),i=1,2,…,n байх x элемент R цагиргаас олдоно. Үүнд: x≡ x_i (mod R_i ) гэдэг нь x=x_i+x_i, R_i ∋ r_i, i=1,n ̅ байна гэсэн үг юм.

Баталгаа

n-ээр индукцэлж баталъя. n=2 байг. R=R_1+R_2 учраас e=a_1+a_2 байх R_1 ∋a_1, R_2 ∋ a_2 элемент олдоно. x_1, x_2 гэсэн дурын хоёр элемент, R-ээс авбал, x=x_1 a_2+x_2 a_1 нь бидний олох элемент болно. Үнэхээр R ∋ a_1 учир R_1 ∋ a_1 x_1, x_2 a_1 . R_1 ∋ x-x_1=x_1 a_2+x_2 a_1-x_1=x_1 (a_2-e)+x_2 a_1=x_1 a_1+x_2 a_1 байна. Иймд x≡x_1 (mod R_1 ). Үүнтэй адилаар x≡x_2 (mod R_2 ) болохыг баталж болно. Теоремийг (n-1) идеалуудын бүлийн хувьд батлагдсан гэж үзье. R_1+R_i=R учраас i≥2 байх бүх i -ийн хувьд e=a_i+b_i байх R_1∋a_1,R_i ∋ b_i, i=2,3,…,n элементүүд олдоно. e=a_i+b_i учир (a_2+b_2) (a_3+b_3 )… (a_n+b_n)-e болно. R-ийг коммутатив гэдгийг ашиглавал (a_2+b_2) (a_3+b_3 )… (a_n+b_n) элемент нь R_1+R_2 R_3...R_n-ийн элемент болно гэж гарна. Иймд R_1+R_2 R_3...R_n=R болно. R_1,R_2 R_3...R_n хоёр идеал нь теоремын n=2 үе дэх нөхцөлийг хангана. Иймээс e, 0 гэсэн хоёр элемент R цагиргаас авбал y_1≡e(mod R_1 ),y_1≡0(mod R_i…R_r) байх R ∋ y_1 элемент олдоно. Энэ сэтгэлгээг R_2 ба R_1 R_3...R_n хосод гэх мэт. R_n ба R_1 R_2...R_n-1 хосод хэрэглэнэ. y_j≡e (mod R_j ),y_j≡0 (mod R_1… R_j-1 R_(j+1)…R_n) байх y_1,y_2,…,y_n элементүүд олдоно. R_1 R_2… R_(j-1) R_(j+1)… R_n ⊂ R_i,i≠ j,i=1,n ̅ байх учраас y_(j )≡0 (mod R_1...R_j-1 R_j+1…R_n) бичлэгийг y_j≡ 0 (mod R_i),i=j гэж бичиж болох юм. x=x_1 y_1+...+x_n y_n нь бидний олох элемент мөн. Жишээ нь: x=x_1 (mod R_1) болохыг үзүүлье. x-x_1=x_1 y_1+x_2 y_2+...+x_n y_n-x_1=x_2 y_2+...+x_n y_n+x_1 (y_1-e) ба i≥2 үед y_i≡0(mod R_i) учраас R∋ x_2 y_2+...+x_n y_n ба y_1≡ e(mod R_1) буюу R_1 ∋ y_1-e байгааг бодолцвол x≡x_1 (mod R_1) болох нь батлагдана. Теорем батлагдав.

МӨРДЛӨГӨӨ

R цагиргийн оронд Z бүхэл тоон цагираг, мөн Ф[x] олон гишүүнтүүдийн цагиргийг авбал дараах чухал мөрдлөгүүд гарна.

МӨРДЛӨГӨӨ 1(Үлдэгдлийн тухай Хятадын сонгодог теорем). Z цагиргийн хос хосоороо харилцан анхны m_1, m_2,...,m_n тоонууд ба дурын а_1,а_2,...,a_n бүхэл тоонуудын хувьд a ≡ a_i (mod m_i),i=1,n ̅ байх 0 бүхэл тоо олдоно. Баталгаа. Эхлээд, хэрэв а, b нь харилцан анхын натурал тоонууд байвал ax_0+by_0 =1 байх x_0 y_0 бүхэл тоонууд олдоно гэж баталья. M={ax+by|Z ∋ x,y} олонлогийг авч үзье. М-д орох эерэг тоонуудаас хамгийн багыг нь d_0 гэе. d_0 =1 гэж баталбал хангалттай. M ∋ d_0 учраас ямар нэг x_0,y_0 бүхэл тоонуудын хувьд d_0=ax_0+bx_0 байна. a, b тоог a=d_0 c_1+r_1,0≤r_1<d_0, b=d_0 c_2+r_2,0≤r_2<d_0 дүрстэй бичье. Ийнхүү r_1=a-d_0 c_1=a(1-x_0 c_1)+b(-y_0 c_1) r_2=a-d_0 c_2=a(-x_0 c_2)+b(1-y_0 c_2) болно. Эдгээр тоонууд М-д орно. d_0 нь М-ийн хамгийн бага эерэг тоо гэдгийг анхаарвал r_1=r_2=0. Иймд a:d_0, b:d_0, a,b нь харилцан энгийн тоонууд учраас d_0=1 байна. (m_i,m_j)=1 учраас m_i u+m_j υ =1 байх бүхэл тоонууд олдоно. Иймээс(m_i)+(m_j)=Z байна. Үүнд (m_i)- ээр m_i элементээр төрөгдсөн идеалыг тэмдэглэв. Үлдэгдлийн тухай Хятадын теоремын нөхцөл биелэх учир дурдсан чанартай a тоо олдоно.

МӨРДЛӨГӨӨ 2. Ф[x] цагиргийн хос хосоороо харилцан анхны f_1(x),...,f_n (x) олон гишүүнтүүд ба дурын φ_1(x),φ_2(x),...,φ_n(x)олон гишүүнтүүдийн хувьд f(x) ≡ φ_i(x)(mod f_i (x)), i=1,n ̅ байх Ф[x] ∋ f(x) олон гишүүнт олдоно. Баталгаа нь 1-р мөрдлөгөөтэй төстэй.

Жишээ бодолт

Бодлого 1. Ямар ч натурал n-ийн хувьд тус бүрт нь нэгээс их бүхэл тооны квадратад хуваагддаг дараалсан ширхэг натурал тоо олдоно гэж батал.

Бодолт. P_1,P_2,...,P_n-үүд нь ялгаатай анхны тоо байг. Тэгвэл 1-р мөрдлөгөө ёсоор P_1^2,P_2^2,...,P_n^2-уудад хуваахад харгалзан P_1^2-1,P_2^2-2,...,P_n^2-n гэсэн үлдэгдлүүд өгдөг m натурал тоо олдоно. Иймд m+1,m+2,...,m+n гэсэн дараалсан n ширхэг тоо нь харгалзан P_1^2,P_2^2,...,P_n^2-уудад хуваагдана.

Бодлого 2. 1≤n≤k байх n бүхний хувьд k*2^n+1 тоо зохимол тоо байхаар натурал к тоог олж болно гэж батал.

Бодолт. Fm=22m+1 гэсэн Фермагийн тоо авья. F0=3, F1=5, F2=17, F3=257, F4=65537 тоонууд энгийн тоо байдаг. Харин F5=641p,p нь F1-ээс их анхны тоо байна. 1-р мөрдлөгөө ёсоор: k≡1(mod F_i ),i=0,1,2,3,4 k≡-1(mod p) k≡1(mod 641) байх к натурал тоо олдоно. n=2^m (2t+1),m=0,1,2,… хэлбэрийн тоонуудыг авч үзье. 2^(2^s)≡-1(mod F_s ),s=0,1,2,3,4 2^(2^5)≡-1(mod 641),2^(2^P)≡-(mod p)⟹2^(2^m)≡1(mod p),m≥6 байна. Дээр дурдсан k-ийн хувьд m=0:k*2^n+1=k*2^2t+1+1≡1*(-1)+1=0(mod 3) m=1:k*2^n+1=k*2^2(2t+1)+1≡1*(-1)+1=0(mod 5) m=2:k*2^n+1=k*2^4(2t+1)+1≡1*(-1)+1=0(mod 17) m=3:k*2^n+1=k*2^8(2t+1)+1≡1*(-1)+1=0(mod 257) m=4:k*2^n+1=k*2^16(2t+1)+1≡1*(-1)+1=0(mod 65537) m=5:k*2^n+1=k*2^32(2t+1)+1≡1*(-1)+1=0(mod 641) m≥6:k*2^n+1=k*2^2(2t+1)+1≡1*(-1)+1=0(mod p)

Бодлого 3. m_1,m_2…,m_s нь хос хосоороо харилцан энгийн натурал тоонууд байг ψ:Z -> Z/(m_1 Z) ⊕… ⊕ Z/(m_s Z) буулгалтын Z ∋ ∀n -ийн хувьд ψ(n)=(ψ_1(n),…,ψ_s(n)) үүнд, ψ_i:Z -> Z/(m_i Z) каноник гомоморфизм гэж тодорхойльё. m=m_1 m_2…m_s гэе. Тэгвэл ψ нь Z/mZ -ийг +Z/m_1Z+... +Z/(m_s Z) -д буулгах изоморфизм болно гэж батал. Бодолт. ψ нь гомоморфизм байна гэдэг нь илт болно. ψ-ийн цөмийг ольё. ψ(n)=(b_1…,b_s) байх гарцаагүй бөгөөд хүрэлцээтэй нөхцөл нь ψ_i(n)=b_i,i=1,2,…s байх явдал юм. Тодруулбал n=b_i (mod m_i ),i=1,2,…,s байна. Мөрдлөгө 1 ёсоор n=b_i(mod m_i) байх n ямагт олдоно. Иймээс ψ(n)=0 байх гарцаагүй бөгөөд хүрэлцээтэй нөхцөл нь n=0(mod m_i ),i=1,2…,s байх явдал юм. Ийнхүү ψ-ийн цөм нь mZ=(m) идеалтай давхацна. Иймээс ψ нь Z/mZ ба Z/(m_1 Z)+⋯+Z/(m_s Z)хоорондох изоморфизм болно.