AdamátorZápiskyHlášky

Teorie čísel

Zápisky z přednášek prof. Ing. Zuzany Masákové, Ph.D.

Známka je primárně za domácí úkoly, popřípadě za ústní zkoušku týkající se jejich řešení.

Motivace

Cvičení Najděte všechna x,y∈ℤ taková, že x2−y2=35.
Řešení
(x+y)⋅(x−y)=35.
Probereme všechny možnosti, jak rozložit 35 na součin dvou celých čísel, a porovnáme je s levou stranou.
35=1⋅35⟶x=18,y=−1735=5⋅7⟶x=6,y=−135=7⋅5⟶x=6,y=135=35⋅1⟶x=18,y=1735=−1⋅−35⟶x=−18,y=1735=−5⋅−7⟶x=−6,y=135=−7⋅−5⟶x=−6,y=−135=−35⋅−1⟶x=−18,y=−17
Cvičení Najděte všechna x,y∈ℤ taková, že x2−2y2=35.
Řešení
(x+2y)⋅(x−2y)=35.
Nyní již musíme číslo 35 rozložit ne v oboru celých čísel, ale v oboru ℤ[2]. Jak to udělat, to se naučíme v tomto kurzu.

Na konci si dokážeme velkou Fermatovu větu pro n=3,4.

Algebraická čísla

Definice Nechť S⊂T jsou tělesa. Prvek α∈T je algebraický nad S, pokud existuje polynom f∈S[x] takový, že f(α)=0.
Věta Je-li α∈T algebraický nad S, potom existuje právě jeden monický polynom f∈S[x] minimálního stupně takový, že f(α)=0. Navíc je-li g∈S[x] libovolný polynom splňující g(α)=0, potom f|g.
Důkaz Nechť f,f~ jsou dva různé polynomy minimálního stupně ze všech nenulových polynomů s kořenem α. Položme h≔f−f~. Jelikož musí být degh≥degf=degf~, nemohou být oba polynomy f,f~ monické. Tím jsme dokázali jednoznačnost f. Nechť dále g≕qf+r,q,r∈S[x],degr<degf. Potom také r(α)=0, tedy podle minimality stupně musí být r=0.
Definice Polynom f z této věty nazveme minimální polynom prvku α.
Definice Nechť α∈T. Potom definujeme ideál
Iα≔{g∈S[x]|g(α)=0}.
Poznámka α je algebraický nad S, právě když Iα≠{0}.
Poznámka Předchozí věta plyne z toho, že S[x] je obor hlavních ideálů.
Věta Minimální polynom f algebraického prvku α∈T nad S je ireducibilní nad S. Naopak pokud je nějaký monický polynom f∈S[x] s kořenem α ireducibilní nad S, potom je to minimální polynom α.
Důkaz
  • Nechť f je minimální polynom a f=g⋅h,g,h∈S[x]. Potom 0=f(α)=g(α)⋅h(α). Tedy bez újmy na obecnosti g(α)=0. Z věty plyne, že f|g. Jelikož zároveň g|f, musí se rovnat až na násobení konstantou.
  • Nechť f je ireducibilní monický s kořenem α a f~ je minimální polynom α. Potom f~|f a z ireducibility plyne, že f=f~.
Definice Nechť f∈S[x] je monický polynom:
f(x)=xn+∑i=0n−1cixi.
Potom jeho doprovodná matice (v TIGRu tomu říkají matice společnice) je Mf∈Sn×n,
Mf≔(010⋯0001⋯0⋮⋮⋮⋱⋮000⋯1−c0−c1−c2⋯−cn−1).
Věta Polynom f∈S[x] je charakteristický polynom matice Mf až na znaménko.
Důkaz Rozvojem podle posledního řádku.
Věta Je-li α∈T kořen polynomu f∈S[x], potom je α vlastním číslem Mf s vlastním vektorem (1;α;…;αn−1).
Důkaz
Mf⋅(1α⋮αn−2αn−1)=(αα2⋮αn−1−∑i=0n−1ciαi)=(αα2⋮αn−1αn)=α⋅(1α⋮αn−2αn−1).
Věta Prvek α∈T je algebraický nad S, právě když je vlastním číslem nějaké matice M∈Sn×n.
Důkaz
(⇒)
Plyne z předchozího tvrzení.
(⇐)
Je-li α vlastní číslo M, potom je kořenem jejího vlastního polynomu, tudíž je algebraické.
Definice Množinu algebraických komplexních čísel nad ℚ budeme značit 𝔸.
Definice Tenzorový součin matic A∈ℚr×s,B∈ℚm×n je A⊗B∈ℚrm×sn,
A⊗B≔(B1,1A⋯B1,nA⋮⋱⋮Bm,1A⋯Bm,nA).
Čteme „á tenzor bé“.
Poznámka S tenzorovým součinem jsme se již setkali v 01TA (pod názvem Kroneckerův součin), 01TKO a 01TEMA.
Věta Nechť A∈ℚr×s,B∈ℚm×n,C∈ℚs×t,D∈ℚn×p. Potom
(A⊗B)⋅(C⊗D)=(A⋅C)⊗(B⋅D).
Důkaz
(A⊗B)⋅(C⊗D)=(B1,1A⋯B1,nA⋮⋱⋮Bm,1A⋯Bm,nA)⋅(D1,1C⋯D1,pC⋮⋱⋮Dn,1C⋯Dn,pC)=(∑j=1nB1,jDj,1AC⋯∑j=1nB1,jDj,pAC⋮⋱⋮∑j=1nBm,jDj,1AC⋯∑j=1nBm,jDj,pAC)=((BD)1,1AC⋯(BD)1,pAC⋮⋱⋮(BD)m,1AC⋯(BD)m,pAC)=(A⋅C)⊗(B⋅D).
Věta Nechť α∈ℂ je vlastní číslo A∈ℚr×r a β∈ℂ je vlastní číslo B∈ℚm×m. Potom α⋅β je vlastní číslo A⊗B.
Důkaz Nechť u,v jsou příslušné vlastní vektory. Potom
(A⊗B)⋅(u⊗v)=(A⋅u)⊗(B⋅v)=(α⋅u)⊗(β⋅v)=(α⋅β)⋅(u⊗v).
Věta Nechť α∈ℂ je vlastní číslo A∈ℚr×r a β∈ℂ je vlastní číslo B∈ℚm×m. Potom α±β je vlastní číslo (A⊗𝐈m)±(𝐈r⊗B).
Důkaz Nechť u,v jsou příslušné vlastní vektory. Potom
((A⊗𝐈m)±(𝐈r⊗B))⋅(u⊗v)=(A⊗𝐈m)⋅(u⊗v)±(𝐈r⊗B)⋅(u⊗v)=(A⋅u)⊗(𝐈m⋅v)±(𝐈r⋅u)⊗(B⋅v).=(α⋅u)⊗v±u⊗(β⋅v)=(α±β)⋅(u⊗v).
Věta 𝔸 je podtěleso ℂ.
Důkaz Nechť α,β∈𝔸 s minimálními polynomy f,g. Potom jsou to vlastní čísla matic Mf,Mg. Z předchozích dvou tvrzení plyne uzavřenost na násobení, sčítání a odčítání. Zbývá ověřit uzavřenost na inverzi. Je-li α≠0,f(x)=xn+∑i=0n−1cixi, máme detMf=±c0≠0 (nenulovost plyne z ireducibility). Potom matice Mf−1 má vlastní číslo α−1.
Definice Stupeň algebraického prvku α∈T nad S je stupeň jeho minimálního polynomu.
Poznámka Z předchozí věty plyne, že je-li α∈𝔸,α≠0 stupně r a β∈𝔸 stupně m, potom α⋅β,α±β mají stupeň nanejvýš r⋅m a α−1 má stupeň přesně r.
Příklad Nechť α≔2,β≔3. Jejich minimální polynomy jsou f(x)=x2−2,g(x)=x2−3. Z toho můžeme vytvořit doprovodné matice
Mf=(0120),Mg=(0130).

Chceme-li najít polynom s kořenem α⋅β=6, spočteme si

Mf⊗Mg=(0001002003006000).

Charakteristický polynom této matice je

det(Mf⊗Mg−x⋅𝐈)=x4−12x2+36=(x2−6)2.

Všimněme si, že jsme tím nedostali minimální polynom x2−6, ale dostali jsme jeho násobek.

Pro nalezení polynomu s kořenem α+β=2+3 použijeme matici

Mf⊗𝐈2+𝐈2⊗Mg=(0100200000010020)+(0010000130000300)=(0110200130010320).

Její charakteristický polynom je

det(Mf⊗𝐈2+𝐈2⊗Mg−x⋅𝐈)=x4−10x2+1.

Kořeny tohoto polynomu jsou ±5±26. Skutečně platí 2+3=5+26. Mají nějaký význam ostatní kořeny? Pokud uvažujeme všechny kořeny původních minimálních polynomů f,g, tedy ±2,±3, vyšly nám všechny jejich možné součty.

Věta Je-li f∈ℚ[x] ireducibilní, potom všechny jeho kořeny jsou různé.
Důkaz Nechť α je kořen f. Potom f je minimální polynom pro α. Jelikož degf′<degf, nemůže být α kořenem f′, takže jako kořen f má násobnost 1.
Definice Čísla α1,…,αn∈ℂ jsou algebraicky sdružená, pokud mají stejný minimální polynom.
Poznámka Jsou-li α,β∈𝔸 s algebraicky sdruženými čísly α1,…,αn;β1,…,βm, potom z tenzorové konstrukce plyne, že všechna algebraicky sdružená čísla k α⋅β jsou ve tvaru αi⋅βj. Ovšem ne všechna čísla v tomto tvaru k nim musí být algebraicky sdružená, protože polynom vzniklý z tenzorové konstrukce nemusí být ireducibilní.

Tělesa ℚ(α)

Definice Nechť α∈𝔸. Potom definujeme
ℚ(α)≔⋂{T⊂ℂ|Ttěleso,α∈T}.
Poznámka Pro konzistenci s obecnou definicí z ALGE bychom měli psát
ℚ(α)≔⋂{T⊂ℂ|Ttěleso,T⊃ℚ,α∈T}.
Ovšem podmínka T⊃ℚ je zbytečná, protože ℚ je prvotěleso ℂ, takže každé podtěleso ℂ obsahuje ℚ.
Věta Nechť α∈𝔸 stupně n. Potom
ℚ(α)={∑i=0n−1aiαi|ai∈ℚ}={g(α)|g∈ℚ[x],degq<n}.
Důkaz Stačí ukázat, že množina na pravé straně je těleso. Nejprve dokážeme, že
M≔{g(α)|g∈ℚ[x],degq<n}={g(α)|g∈ℚ[x]}.
Zřejmě platí ⊂. Naopak nechť g∈ℚ[x] a f je minimální polynom pro α. Vydělíme se zbytkem g≕q⋅f+r,degr<n. Potom g(α)=q(α)⋅f(α)+r(α)=r(α)∈M. Tím jsme dokázali, že M je okruh.

Zbývá uzavřenost na inverzi. Nechť g∈ℚ[x],g≠0,degg<n. Jelikož f je ireducibilní a degg<n=degf, jsou f,g nesoudělné. Podle Bézoutovy věty existují u,v∈ℚ[x] takové, že 1=g⋅u+f⋅v. Speciálně 1=g(α)⋅u(α)+f(α)⋅v(α)=g(α)⋅u(α), tedy g(α)−1=u(α)∈M.

Poznámka Druhá část důkazu plyne z toho, že ℚ(α)=ℚ(x)/Iα=ℚ(x)/f. Na ALGE jsme si dokazovali, že faktorizací okruhu podle maximálního hlavního ideálu vznikne těleso.
Věta Nechť α,αi∈𝔸 jsou algebraicky sdružené. Potom ℚ(α)≃ℚ(αi).
Důkaz Označme f minimální polynom pro α,αi. Pro g(α)∈ℚ(α) definujme σi(g(α))≔g(αi). Dokážeme, že σi je izomorfismus. Zjevně je surjektivní. Injektivita plyne z toho, že pokud g(αi)=h(αi), potom (g−h)(αi)=0. Jelikož deg(g−h)<degf, musí být g=h, tedy speciálně g(α)=h(α). Zbývá ověřít, že σi je homomorfismus, což je snadné.
Příklad Mějme α=α1≔2,α2≔−2,f(x)=x2−2. Potom
ℚ(2)={a+b⋅2|a,b∈ℚ},
ℚ(−2)={a−b⋅2|a,b∈ℚ}.
V tomto případě ℚ(2)=ℚ(−2). Máme triviální izomorfismus σ1=id a netriviální izomorfismus σ2.
Příklad Mějme
α=α1≔23,α2≔23⋅exp2π𝕚3,α3≔23⋅exp4π𝕚3,f(x)=x3−2.
Potom
ℚ(23)={a+b⋅23+c⋅43|a,b,c∈ℚ}∈ℝ,
ℚ(23⋅exp2π𝕚3)={a+b⋅23⋅exp2π𝕚3+c⋅43⋅exp2π𝕚3|a,b,c∈ℚ}∉ℝ,
ℚ(23⋅exp4π𝕚3)={a+b⋅23⋅exp4π𝕚3+c⋅43⋅exp4π𝕚3|a,b,c∈ℚ}∉ℝ.
Všimněme si, že ℚ(α1)≠ℚ(α2) (jedno je podmnožina ℝ a druhé ne). Zároveň platí ℚ(α3)=ℚ(α2)¯, ovšem nějak můžeme dokázat, že si také nejsou rovny. Z toho speciálně plyne, že ℚ(α2) není uzavřené na komplexní sdružení.
Věta Je-li α∈𝔸 stupně n, potom ℚ(α) je lineární prostor nad ℚ dimenze n s bází 1,α,…,αn−1.
Důkaz Soubor zjevně generuje celý prostor. Lineární nezávislost plyne z toho, že minimální polynom pro α je stupně n, takže pokud ∑i=0n−1biαi=0, musí být bi=0.
Věta Nechť α,β∈𝔸. Potom existuje γ∈𝔸 takové, že ℚ(α,β)=ℚ(γ).
Poznámka Z toho indukcí plyne, že pro libovolnou konečnou M⊂𝔸 existuje γ∈𝔸 takové, že ℚ(M)=ℚ(γ).
Důkaz Nechť f,g jsou minimální polynomy pro α,β stupňů n,m a α=α1,…,αn;β=β1,…,βm jsou algebraicky sdružená čísla. Zvolme libovolné c∈ℚ∖{αi−αβ−βj|i∈n^,j∈m^∖{1}} a definujme γ≔α+c⋅β. Zřejmě je ℚ(γ)⊂ℚ(α,β). Pro opačnou inkluzi stačí dokázat α,β∈ℚ(γ).

Označme h(x)≔f(γ−c⋅x)∈ℚ(γ)[x]. Speciálně h(β)=f(γ−c⋅β)=f(α)=0. Pro j≠1 je h(βj)≠0, protože

h(βj)=0⟺γ−c⋅βj=αi⟺α+c⋅β−c⋅βj=αi⟺c⋅(β−βj)=αi−α⟺c=αi−αβ−βj.
Z toho plyne, že g,h mají právě jeden společný kořen, a sice β. Z toho plyne x−β=nsd(g,h)∈ℚ(γ)[x], tedy speciálně β∈ℚ(γ). Potom také α=γ−c⋅β∈ℚ(γ).
Příklad Pro α≔2,β≔3 požadujeme
c∈ℚ∖{2−23+3,2+23+3}=ℚ∖{0,23}.
Vezmeme-li například c≔1, máme ℚ(2,3)=ℚ(2+3).
Příklad Mějme α≔23,α′≔23⋅exp2π𝕚3,α″≔23⋅exp4π𝕚3. Jelikož α″=−α−α′, máme ℚ(α,α′,α″)=ℚ(α,α′). Tentokrát volba c≔1 nefunguje, ale třeba c≔−1 ano, takže ℚ(α,α′,α″)=ℚ(α−α′).
Definice Nechť α=α1,α2,…,αn∈𝔸 jsou algebraicky sdružená stupně n a β=g(α)∈ℚ(α). Potom tělesový polynom pro β je
Pβ(x)≔∏i=1n(x−σi(β)).
Příklad Nechť α1,2≔±2. Potom máme izomorfismy σ1=id a σ2(α+β2)=α−β2. Pro β=α+β2 je
Pα+β2(x)=(x−(α+β2))⋅(x−(α−β2))=x1−2ax+a2−2b2∈ℚ[x].

Symetrické polynomy

Definice Polynom F∈T[x1,…,xn] je symetrický, pokud pro všechny π∈𝕊n je
F(x1,…,xn)=F(xπ(1),…,xπ(n)).
Příklad Polynom F(x1,x2,x3)=x12+x22+x32−3x1x2x3 je symetrický.
Příklad Polynom F(x1,x2,x3)=x12x2+x22x3+x32x1 není symetrický, protože F(x1,x2,x3)≠F(x2,x1,x3).
Definice Elementární symetrické funkce na n proměnných jsou polynomy e1,…,en∈T[x1,…,xn], kde
ek(x1,…,xn)≔∑{∏j=1kxij|1≤i1<⋯<ik≤n}.
Příklad Pro n=2 je
e1(x1,x2)=x1+x2,
e2(x1,x2)=x1x2.
Všimněme si, že máme-li polynom
f(x)=x2+Ax+B=(x−x1)(x−x2),
potom
−A=x1+x2,
B=x1x2.
Příklad Pro n=3 je
e1(x1,x2,x3)=x1+x2+x3,
e2(x1,x2,x3)=x1x2+x1x3+x2x3,
e3(x1,x2,x3)=x1x2x3.
Všimněme si, že máme-li polynom
f(x)=x2+Ax2+Bx+c=(x−x1)(x−x2)(x−x3),
potom
−A=x1+x2+x3,
B=x1x2+x1x3+x2x3,
−C=x1x2x3.
Věta Vietovy vzorce Nechť f(x)∈T[x],
f(x)=xn+∑i=0n−1aixi=∏i=1n(x−xi).
Potom pro všechna i∈n^ platí
an−i=(−1)i⋅ei(x1,…,xn).
Důkaz Stačí roznásobit výraz ∏i=1n(x−xi).
Věta základní věta o symetrických polynomech Nechť F∈T[x1,…,xn] je symetrický polynom. Potom existuje polynom G∈T[x1,…,xn] takový, že F=G(e1,…,en).
Příklad Mějme symetrický polynom F(x1,x2,x3)=x12+x22+x32−3x1x2x3. Potom F=e12−2e2−3e3.
Důkaz Nechť
F(x1,…,xn)=∑(i1,…,in)∈Ici1,…,in∏j=1nxjij.
Každou n-tici (i1,…,in) nazveme výškou odpovídajícího členu. Členy seřadíme lexikograficky sestupně podle výšky; ten s nejvyšší výškou bude vedoucí člen. Jelikož n-tice přirozených čísel jsou dobře uspořádané, důkaz můžeme provést indukcí před výšku vedoucího členu. Má-li vedoucí člen výšku (0,…,0), potom F je konstantní polynom, takže stačí vzít G≔F. Nechť výška vedoucího členu je (k1,…,kn) a věta platí pro všechny polynomy, kde vedoucí člen má lexikograficky menší výšku. Označme j1≔k1−k2,j2≔k2−k3,…,jn≔kn. Díky symetrii víme, že j1,…,jn jsou nezáporné. Potom výška polynomu ∏i=1neiji je (k1,…,kn). Označme
F~≔F−ck1,…,kn∏i=1neiji.
Potom F~ má lexikograficky menší výšku vedoucího členu. Nyní stačí použít indukční předpoklad.
Věta Nechť α∈𝔸,β∈ℚ(α). Potom Pβ(x)∈ℚ[x].
Důkaz Polynom Pβ je zjevně symetrický, takže ho podle předchozí věty dokážeme napsat jako polynomiální kombinaci elementárních symetrických funkcí. Z Vietových vzorců plyne, že ek(α1,…,αn)∈ℚ.
Věta Nechť α∈𝔸 stupně n a β∈ℚ(α). Potom β∈𝔸 stupně nanejvýš n.
Důkaz ℚ(α) je vektorový prostor nad ℚ stupně n, takže hodnoty 1,β,…,βn jsou lineárně závislé. Netriviální lineární konbinace sčítající se na nulu nám dá polynom s kořenem β.
Věta Nechť β∈𝔸,β∈ℚ(α). Potom Pβ=hk, kde h je minimální polynom pro β a k∈ℕ.
Důkaz Jelikož Pβ(β)=0, musí být h|Pβ. Nechť k je nejvyšší číslo takové, že Pβ=hkg,g∈ℚ[x]. Nechť dále h(x)=∑i=0mhixi. Potom
h(σj(β))=∑i=0khi⋅(σj(β))i=∑i=0kσj(hi)⋅σj(βi)
Důsledek Je-li β∈ℚ(α), potom degβ|degα.

Norma a stopa v ℚ(α)

Definice Nechť α=α1,…,αn jsou sdružené a β∈ℚ(α). Potom
Poznámka Všimněme si, že norma a stopa jsou (až na znaménko) koeficienty stupně 0, resp. n−1 u Pβ, z čehož plyne, že jsou racionální.
Věta multiplikativita normy Nechť β,γ∈ℚ(α). Potom
N(β⋅γ)=N(β)⋅N(γ).
Důkaz
N(β⋅γ)=∏i=1nσi(β⋅γ)=∏i=1nσi(β)⋅σi(γ)=N(β)⋅N(γ).
Věta aditivita stopy Nechť β,γ∈ℚ(α). Potom
Tr(β+γ)=Tr(β)+Tr(γ).
Důkaz
Tr(β+γ)=∑i=1nσi(β+γ)=∑i=1nσi(β)+σi(γ)=Tr(β)+Tr(γ).
Věta Nechť β∈𝔸. Potom
TrMβ=Trℚ(β)(β).
Důkaz Vlastní čísla Mβ jsou β1,…,βn, takže Mβ∼diag(β1,…,βn). Z toho plyne
TrMβ=Trdiag(β1,…,βn)=∑i=1nβi=∑i=1nσi(β)=Trℚ(β)(β).

Kvadratická tělesa

Příklad Mějme zlatý řez φ=1+52. Potom ℚ(φ)=ℚ(5).
Definice Číslo m∈ℤ je čtvercuprosté, pokud ∀d∈ℕ:d|m⟹d=1.
Poznámka Nechť α∈𝔸 stupně 2. Potom můžeme psát α=a+mb, kde a,m∈ℤ,b∈ℕ a m je čtvercuprosté a různé od 1. Máme ℚ(α)=ℚ(m). Můžeme tedy bez újmy na obecnosti uvažovat tělesa pouze ve tvaru ℚ(m) po čtvercuprosté m různé od 1. Tato tělesa jsou vzájemně různá.
Definice Nechť m∈ℤ∖{1} je čtvercuprosté. Potom
Poznámka V kvadratickém tělese pro a,b∈ℤ platí
σ(a+bm)=a−bm,
Pa+bm(x)=(x−(a+m))(x−(a−m))=x2−2ax+a2−mb2,
Tr(a+bm)=2a,
N(a+bm)=a2−mb2,
ℚ(a+bm)∼ℤ2.

Cyklotomická tělesa

Definice Nechť n∈ℕ. Potom grupa n-tých kořenů jedničky je
Cn≔{exp2π𝕚nj|j=0,…,n−1}.
Poznámka Nechť k⟂n a ξ≔exp2π𝕚n. Potom
Cn={(ξk)j|j=0,…,n−1}.
Definice Nechť n∈ℕ,ξ≔exp2π𝕚n. Potom n-tý cyklotomický polynom je
Φn(x)≔∏k=1k⟂nn(x−ξk).
Věta Nechť n∈ℕ. Potom
xn−1=∏d|nΦd(x).
Důkaz Triviální.
Důsledek Porovnáme-li stupně polynomů, dostaneme známý vzoreček
n=∑d|nφ(d).
Příklad V grupě C12 jsouPlatí
xn−1=Φ12(x)⋅Φ6(x)⋅Φ4(x)⋅Φ3(x)⋅Φ2(x)⋅Φ1(x),
kde
Φ1(x)=x−1,
Φ2(x)=x+1,
Φ3(x)=(x−ξ4)(x−ξ8)=x2+x+1,
Φ4(x)=(x−𝕚)(x+𝕚)=x2+1,
Φ6(x)=(x−ξ2)(x−ξ10)=x2−x+1,
Φ12(x)=(x−ξ1)(x−ξ5)(x−ξ7)(x−ξ11)=x4−x2+1.
Všimněme si, že ačkoli cyklotomické polynomy vznikly z hnusných iracionálních komplexních čísel, jejich koeficienty jsou celočíselné.
Věta Nechť n∈ℕ. Potom Φn∈ℤ[x], Φn(0)=±1 a Φn je ireducibilní nad ℚ.
Důkaz Indukcí na n. Máme
xn−1=∏d|nΦd(x)=Φn(x)⋅∏d|nd<nΦd(x)≕(xk+∑i=0k−1aixi)⋅(xl+∑i=0lbixi).
Speciálně −1=a0b0. Podle indukčního předpokladu b0=±1, takže a0=−1b0=∓1. Porovnáme koeficienty u dalších členů:
0=a0b1+a1b0∴a1=−a0b1b0∈ℤ,
0=a0b2+a1b1+a2b0∴a2=−a0b2+a1b1b0∈ℤ.
Obdobně můžeme pokračovat dál, čímž dokážeme, že všechny koeficienty jsou celé. Ireducibilitu dokazovat nebudeme.
Důsledek Nechť n∈ℕ,ξ≔exp2π𝕚n. Potom ξ∈𝔸 stupně φ(n) s minimálním polynomem Φn.
Poznámka Máme
ℚ(ξ)={∑i=0φ(n)−1aiξi|ai∈ℚ}.
Jelikož všechna sdružená čísla ξ1,…,ξφ(n) jsou mocniny ξ, platí ℚ(ξi)=ℚ(ξ).
Poznámka Speciálně pro n∈ℙ je ξi=ξi. Potom {σ1,…,σp−1} tvoří grupu automorfismů. Tato grupa je komutativní:
σiσj(ξ)=σi(ξj)=ξij=σj(ξi)=σjσi(ξ).

Racionální aproximace reálných čísel

Máme nějaké ξ∈ℝ a chceme najít p,q∈ℤ taková, že |ξ−pq| je nějakým způsobem malé vzhledem k velikosti q.

Když máme pevně dané q, tak je to jednoduché. Dostaneme tím racionální číslo vzdálené nanejvýš 12q.

Co kdybychom hledali libovolné q≤n pro pevně dané n? Ukáže se, že potom najdeme mnohem lepší aproximaci.

Definice Nechť n∈ℕ. Potom Fareyovy zlomky řádu n jsou posloupnost 0=f0<f1<⋯<fk=1, kde
{f0,…,fk}=ℱn≔{pq|p≤q≤n}.
Zlomky budeme vždy uvažovat v základním tvaru.
Příklad Pro n=5 máme
f0=0,f1=15,f2=14,f3=13,f4=25,f5=12,f6=35,f7=23,f8=34,f9=45,f10=1.
Věta Pro každé n∈ℕ je
#ℱn=1+∑d=1nφ(d).
Důkaz Pro každý možný jmenovatel d jsou zahrnuty všechny zlomky s čitatelem nesoudělným s d. K tomu ještě máme navíc jedničku.
Věta Pro každé dva po sobě jdoucí Fareyovy zlomky ab<cd platí c⋅b−a⋅d=1.
Poznámka Máme-li dva libovolné zlomky ab<cd, potom 0<cd−ab=c⋅b−a⋅db⋅d. Sousední Fareyovy zlomky tedy nabývají minimální možné vzdálenosti mezi zlomky s daným jmenovatelem.
Důkaz Podle Bézoutovy věty existují x,y∈ℤ takové, že b⋅x−a⋅y=1. Zároveň pro každé r∈ℤ je (x+r⋅a,y+r⋅b) také řešení, tedy
b⋅x1−a⋅y1≔b⋅(x+r⋅a)−a⋅(y+r⋅b)=1.
Vezměme r takové, že n−b<y1≤n. Potom x1y1−ab=1y1⋅b>0. Jelikož cd je nejmenší Fareyův zlomek větší než ab, máme ab<cd≤x1y1. Předpokládejme pro spor, že cd<x1y1. Potom
cd−ab=c⋅b−a⋅db⋅d≥1b⋅d,
x1y1−cd=x1⋅d−y1⋅cy1⋅d≥1y1⋅d,
1y1⋅b=x1y1−ab≥1b⋅d+1y1⋅d=y1+by1⋅b⋅d>ny1⋅b⋅d.
Z toho plyne d>n, což je spor. Musí tedy být cd=x1y1, tudíž platí c⋅b−a⋅d=b⋅x1−a⋅y1=1.
Věta mediánová vlastnost Pro každé tři po sobě joucí Fareyovy zlomky ab<ef<cd platí, že prostřední je „špatně spočtený součet“ krajních:
ef=a+cb+d.
Důkaz Podle předchozí věty platí b⋅e−a⋅f=1,c⋅f−d⋅e=1. Vynásobíme první rovnost c, druhou rovnost a a sečteme je, čímž dostaneme
b⋅e⋅c−d⋅a⋅e=c+a.
Analogicky vynásobením d a b dostaneme
b⋅c⋅f−a⋅d⋅f=b+d.
Z toho plyne
c+ab+d=e⋅(b⋅c−a⋅b)f⋅(b⋅c−a⋅b)=ef.
Věta Dirichletova Pro každé ξ∈ℝ∖ℚ existuje pq∈ℚ takové, že
|ξ−pq|<1q2.
Důkaz Uvažujme bez újmy na obecnosti ξ∈(0,1)∖ℚ. Pro každé n∈ℕ vezměme po sobě jdoucí Fareyovy zlomky ab<cd řádu n takové, že ab<ξ<cd. Je-li b<d, potom
|ξ−ab|<|cd−ab|=1b⋅d<1b2.
Pro d<b analogicky. Zároveň platí, že vzdálenost mezi sousedními Fareyovými zlomky je nanejvýš 1n, takže pro n→∞ najdeme nekonečně mnoho různých vhodných pq.

Řetězové zlomky

Definice Nechť ξ∈ℝ. Označme ξ0≔ξ. Pro každé i∈ℕ vezmeme ai≔⌊ξi⌋. Pokud ξi∈ℤ, potom zastavíme, jinak ξi+1≔1ξi−ai. Potom (ai) je řetězový zlomek pro ξ. Značíme ξ=[a0;a1,…].
Poznámka Název je odvozen z toho, že platí
ξ=a0+1a1+1⋱+1an+1ξn+1.
Poznámka V angličtině se čísla ai jmenují partial quotients a čísla ξi complete quotients.
Věta Řetězový zlomek čísla ξ∈ℝ je konečný, právě když ξ∈ℚ.
Důkaz Implikace doprava je zřejmá. Dokažme implikaci doleva. Nechť ξ=pq. Potom p=a0q+r0,q=a1r0+r1,r0=a2r1+r2,… Jelikož q>r0>r1>⋯, musí algoritmus po konečném počtu kroků skončit.
Definice Nechť n∈ℕ. n-tý kontinuální polynom v proměnných x0,…,xn−1 je polynom Kn(x0,…,xn−1) definovaný rekurzivně jako
K0()≔1,
K1(x0)≔x0,
Kn+1(x0,…,xn)≔Kn−1(x0,…,xn−2)+xnKn(x0,…,xn−1).
Příklad
  • K2(x0,x1)=1+x0x1,
  • K3(x0,x1,x2)=x0+x2+x0x1x2.
Věta Pro x0∈ℝ,x1,…,xn∈ℝ+ platí
x0+1x1+1⋱+1xn−1+1xn=Kn+1(x0,…,xn)Kn(x1,…,xn).
Důkaz Indukcí. Pro n=0 platí. Předpokládejme, že výrok platí pro n, potom
x0+1x1+1⋱+1xn+1xn+1=Kn+1(x0,…,xn−1,xn+1xn+1)Kn(x1,…,xn−1,xn+1xn+1)=Kn−1(x0,…,xn−2)+(xn+1xn+1)Kn(x0,…,xn−1)Kn−2(x1,…,xn−2)+(xn+1xn+1)Kn−1(x1,…,xn−1)=něco=xn+1Kn+1(x0,…,xn)+Kn(x0,…,xn−1)xn+1Kn(x1,…,xn)+Kn−1(x1,…,xn−1)=Kn+2(x0,…,xn+1)Kn+1(x1,…,xn+1).
Věta Pro každé n∈ℕ platí Kn(x0,…,xn−1)=Kn(xn−1,…,x0).
Důkaz Polynom Kn můžeme kombinatoricky interpretovat jako součet všech možných členů, které můžeme získát z členu x0⋯xn−1 škrtáním sousedních dvojic xixi+1. Z toho je symetrie jasná.
Věta Tuhle větu jsem si nestihl opsat :(
Věta Pro každé n∈ℕ se Kn(1,…,1) rovná n-tému Fibonacciho číslu.
Důkaz Plyne přímo z rekurentního předpisu.
Definice Nechť ξ∈ℝ∖ℚ má řetězový zlomek ξ=[a0;a1,…]. Potom n-tý sblížený zlomek je pnqn, kde
pn≔Kn+1(a0,…,an),qn≔Kn(a1,…,an).
Věta Nechť ξ∈ℝ∖ℚ má částečný řetězový zlomek ξ=[a0;a1,…,an,ξn+1]. Potom
ξ=pn−1+ξn+1pnqn−1+ξn+1qn.
Důkaz
ξ=a0+1a1+1⋱+1an+1ξn+1=⋯
Lemma Nechť ξ∈ℝ∖ℚ. Potom
pn−1qn−pnqn−1=(−1)n.
Důkaz Platí rekurentní vztah
pn=pn−2+anpn−1,qn=qn−2+anqn−1.
Zapíšeme si ho pomocí matice:
(pnpn−1qnqn−1)=(pn−1pn−2qn−1qn−2)(an110).
Postupným dosazováním dostaneme
(pnpn−1qnqn−1)=(p1p0q1q0)∏j=2n(aj110)=∏j=0n(aj110).
Z toho
pnqn−1−qnpn−1=det(pnpn−1qnqn−1)=∏j=0ndet(aj110)=(−1)n.
Věta Nechť ξ∈ℝ∖ℚ má částečný řetězový zlomek ξ=[a0;a1,…,an,ξn+1]. Potom
ξ−pnqn=(−1)nqn(qn−1+ξn+1qn).
Důkaz
ξ−pnqn=pn−1+ξn+1pnqn−1+ξn+1qn−pnqn=pn−1qn−pnqn−1+ξn+1pnqn−ξn+1pnqnqn(qn−1+ξn+1qn)=pn−1qn−pnqn−1qn(qn−1+ξn+1qn).
Důsledek
limn→∞pnqn=ξ.
Důsledek
p2nq2n<ξ<p2n+1q2n+1.
Důsledek
|ξ−pnqn|<1qnqn+1.
Důkaz
|ξ−pnqn|=1qn(qn−1+ξn+1qn)<1qn(qn−1+an+1qn)=1qnqn+1.
Poznámka Navíc můžeme odhadnout
|ξ−pnqn|<1qn2,
čímž dostáváme alternativní důkaz Dirichletovy věty.
Důsledek
|ξ−pnqn|>1qn+1qn+2.
Důkaz
|ξ−pnqn|=1qn(qn−1+ξn+1qn)>1qn(qn−1+(an+1+1)qn)=1qn(qn+1+qn)=1qnqn+1>1qn+1qn+2.
Poznámka Z toho plyne, že aproximace se v každém kroku zlepšuje.
Důsledek
|ξqn+1−pn+1|<1qn+1.
Důkaz
|ξqn+1−pn+1|<1qn+2<|ξqn−pn|=qn|ξ−pnqn|<1qn+1.
Poznámka Z toho později uvidíme, že řetězové zlomky jsou v určitém smyslu nejlepší aproximace.
Lemma Nechť ξ∈ℝ∖ℚ má řetězový zlomek ξ=[a0;a1,…] a pq∈ℚ není sblížený zlomek pro ξ. Je-li qn−1<q<qn, potom
|ξ⋅q−p|>|ξ⋅qn−1−pn−1|+|ξ⋅qn−pn|.
Důkaz Uvažujme soustavu rovnic
μ⋅pn−1+ν⋅pn=pμ⋅qn−1+ν⋅qn=q.
Vhodným přenásobením dostaneme μ⋅(pn−1⋅qn−qn−1⋅pn)=p⋅qn−q⋅pn. Z dříve předvedeného postupu s determinantem víme, že výraz v závorce je (−1)n, takže μ∈ℤ∖{0}. Analogicky odvodíme ν∈Z∖{0}. Zároveň z obou vzniklých rovností je vidět, že μ⋅ν<0. Potom
ξ⋅q−p=ξ⋅(μ⋅qn−1+ν⋅qn)−(μ⋅pn−1+ν⋅pn)=μ⋅(ξ⋅qn−1−pn−1)+ν⋅(ξ⋅qn−pn).
TBD
Důsledek Pro každý zlomek pq,q≤qn,pq≠pnqn platí
|ξ−pq|>|ξ−pnqn|.
Důkaz
|ξ−pq|>qnq⋅|ξ−pnqn|≥|ξ−pnqn|.
Definice Nechť ξ∈ℝ∖ℚ. Zlomek rs je nejlepší aproximace ξ, pokud pro každé pq∈ℚ,q≤s,pq≠rs platí
|ξ⋅q−p|>|ξ⋅s−r|.
Věta Nejlepší aproximace ξ∈ℝ∖ℚ jsou právě jeho sblížené zlomky.
Důkaz Nejprve dokážeme, že pnqn je nejlepší aproximace. Vezmeme m∈ℕ takové, že qm−1<q≤qm≤qn. Potom podle lemmatu
|ξ⋅q−p|>|ξ⋅qm−pm|≥|ξ⋅qn−pn|.
Naopak chceme dokázat, že jakákoli nejlepší aproximace je sblížený zlomek. Najdeme n∈ℕ takové, že qn−1<s≤qn. Kdyby rs nebyl sblížený zlomek, potom z lemmatu
|ξ⋅s−r|>|ξ⋅qn−1−pn−1|.
To je spor s tím, že rs je nejlepší aproximace.
Věta Jeden ze dvou po sobě jdoucích zlomků čísla ξ∈ℝ∖ℚ splňuje
|ξ−pq|<12⋅q2.
Důkaz Předpokládejme pro spor, že
|ξ−pnqn|≥12⋅qn2,|ξ−pn−1qn−1|≥12⋅qn−12.
Potom
1qn⋅qn−1=|pnqn−pn−1qn−1|=|pn−qn−ξ|+|ξ−pn−1qn−1|≥12⋅qn2+12⋅qn−12=qn−12+qn22qn2qn−12.
Roznásobením dostaneme 2⋅qn⋅qn−1≥qn−12+qn2, což je blbost.
Věta Nechť ξ∈ℝ∖ℚ. Pokud zlomek pq∈ℚ splňuje |ξ−pq|<12⋅q2, potom je to sblížený zlomek ke ξ.
Důkaz Najdeme n∈ℕ takové, že qn−1<q≤qn. Pokud pq≠pnqn, potom z lemmatu máme |ξ⋅q−p|>|ξ⋅qn−1−pn−1|. Potom
1q⋅qn−1≤|pq−pn−1qn−1|≤|pq−ξ|+|pn−1qn−1−ξ|<12⋅q2+12⋅q⋅qn−1
2⋅q<qn−1+q
q<qn−1
To je spor.
Věta Hurwitzova Pro každé ξ∈ℝ∖ℚ existuje nekonečně mnoho zlomků pq∈ℚ takových, že
|ξ−pq|<15⋅q.
Zároveň tvrzení neplatí pro žádnou konstantu větší než 5.
Důkaz Dokážeme, že jeden ze tří po sobě jdoucích sblížených zlomků tvrzení splňuje. Předpokládejme pro spor, že neplatí pro pn−1qn−1, pnqn ani pn+1qn+1. Potom
1qn⋅qn−1=|pnqn−pn−1qn−1|=|ξ−pnqn|+|ξ−pn−1qn−1|≥15qn−12+15⋅qn2.
Přenásobením dostaneme
5⋅qnqn−1≥(qnqn−1)2+1
Řešením jako kvadratické nerovnice dostáváme, že qnqn−1∈(1,1+52). Stejným způsobem můžeme odvodit qn+1qn∈(1,1+52). Z toho
an+1=qn+1qn−qn−1qn<1+52−21+5=1.
To je spor. TBD
Poznámka Pro zlatý řez platí 1+52=[1;1,1,1,…].

Liouvillova čísla

Věta Liouvillova Pro každé algebraické číslo α stupně d≥2 existuje c>0 takové, že pro každé pq∈ℚ je
|α−pq|≥cqd.
Důkaz Nechť f∈ℚ[x] je minimální polynom pro α. Vezměme g≔r⋅f, kde r∈ℤ je nejmenší takové, aby g∈ℤ[x]. Potom
0≠g(pq)=∑i=0dai(pq)d=q−d∑i=0daipiqd−i.
Z toho plyne
1qd=|g(pq)|=|g(pq)−g(α)|=|g′(δ)|⋅|α−pq|,
kde δ z Lagrangeovy věty o přírůstku leží mezi a a pq. Předpokládejme bez újmy na obesnosti, že pq∈[α−1,α+1] (jinak stačí vzít c≥1). Označme
H≔maxδ∈[α−1,α+1]|q′(δ)|,c≔min{1,1H}.
Potom
|α−pq|≥1qd⋅|g′(δ)|≥1qd⋅H≥cqd.
Věta Číslo
α≔∑n=1∞10−n!
je transcendentní.
Důkaz Jistě α∉ℚ, protože má neperiodický desetinný rozvoj. Označme
pNqN≔∑n=1N10−n!.
Potom
α−pNqN=∑n=N+1∞10−n!<∑n=(N+1)!∞10−n=109⋅(N+1)!.
Kdyby α bylo algebraické, potom by podle Liouvillovy věty platilo
c10N!⋅d≤|α−pNqN|<109⋅(N+1)!,
10(N+1)!−d⋅N!<109c.
Ovšem
(N+1)!−dN!=N!⋅(N+1−d)→N→∞∞.
To je spor.
Poznámka Analogicky by se dalo dokázat, že pro každou posloupnost (an)∈{0,1}ℕ obsahující nekonečně mnoho jedniček je číslo
α≔∑n=1∞an⋅10−n
transcendentní. Z toho plyne, že transcendentních čísel je nespočetně mnoho.
Věta Nechť pro α∈ℝ∖ℚ existuje prostá posloupnost (pnqn) taková, že pro každé n∈ℕ platí
|α−pnqn|<1qnn.
Potom α je transcendentní.
Důkaz Kdyby α bylo algebraické stupně d≥2, potom podle Liouvillovy věty
cqdd≤|α−pnqn|>1qnn.
Z toho
1c>qnn−d→n→∞∞.
To je spor.
Definice Čísla splňující podmínku v předchozí větě se nazývají Liouvillova.
Poznámka Existují i transcendentní čísla, která nejsou Liouvillova, například π,𝕖 nebo Champernowneova konstanta:
α≔0.123456789101112131415…
Věta Každé reálné číslo α je součet dvou Liouvillových čísel.
Důkaz Nechť bez újmy na obecnosti α∈(0,1). Uvažujme jeho desetinný rozvoj, přičemž případě, že exsitují dva, vezmeme ten s devítkami:
α=∑j=1∞bj10−j,bj∈{0,…,9}.
Definujme
(aj)≔(1,0,0,1,1,1,1,1,1,0,…,0⏟4!×,1,…,1⏟5!×,…),
L1≔∑i=1∞ajbj10−j,
L2≔∑i=1∞(1−aj)bj10−j.
Zjevně α=L1+L2. Dokážeme, že L1 je Liouvillovo, pro L2 je důkaz analogický. Pro k≔∑j=12n+1j! vezměme
pnqn≔∑i=1kajbj10−j.
Potom
L1−pnqn<10−k−(2n+2)!<10−k⋅n.
Budeme odhadovat
n⋅∑j=12n+1j!=n⋅∑j=12nj!+n⋅(2n+1)!<2n⋅(2n+1)!<(2n+2)!<∑j=12n+1j!+(2n+2)!.
Věta Rothova Nechť α∈ℝ∖ℚ je algebraické číslo. Potom pro každé ε>0 existuje c>0 takové, že pro všechna pq∈ℚ je
|α−pq|≥cq2+ε.
Důkaz Ne.

Řetězové zlomky kvadratických čísel

Lemma Každé kvadratické číslo ξ jde zapsat ve tvaru
ξ=A+dB,
kde A,B∈ℤ,d∈ℕ,d∉ℕ,B|(A2−d).
Důkaz Nechť ξ=pq+rsm∈ℚ(m). Potom
ξ=ps2q+mq4r2s2q2s2.
Věta Lagrangeova Řetězový zlomek iracionálního čísla ξ je periodický, právě když ξ je kvadratické číslo.
Důkaz
(⇒)
Nejprve uvažujme čistě periodický řetězový zlomek ξ=[α0;α1,…,αl−1¯]. Potom ξl=ξ, tedy
ξ=ξl⋅pl−1+pl−2ξl⋅ql−1+ql−2=ξ⋅pl−1+pl−2ξ⋅ql−1+ql−2,
z čehož dostáváme kvadratickou rovnost
ql−1⋅ξ2+(ql−2−pl−1)⋅ξ−pl−2=0.
Pokud nyní uvažujeme ξ s nečistě periodickým rozvojem, který má na začátku k číslic navíc, potom
ξ=ξkpk−1+pk−2ξkqk−1+qk−2.
Jelikož ξk je kvadratické číslo, ξ je také kvadratické číslo.
(⇐)
Nejprve dokážeme indukcí, že
ξn=An+dBn,A0=A,B0=B,An+1=An−anBn,Bn+1=d−An+12Bn.
To plyne víceméně přímo z dosazení:
ξn+1=1xn−an=Bn−An+1+d=An+1+d−An+12+dBn=An+1+dBn+1.
Nyní ukážeme, že posloupnosti An,Bn jsou omezené. Z výrazu ξ=ξn+1pn+pn−1ξn+1qn+qn−1 si vyjádříme
ξ(ξn+1qn+qn−1)=ξn+1pn+pn−1,
ξn+1(ξqn−pn)=pn−1−ξqn−1,
ξn+1=−ξqn−1−pn−1ξqn−pn=−qn−1qnξ−pn−1qn−1ξ−pnqn.
Aplikací izomorfismu dostáváme
σ(ξn+1)=−qn−1qnσ(ξ)−pn−1qn−1σ(ξ)−pnqn.
Jelikož σ(ξ)≠ξ a zlomky pn−1qn−1,pnqn konvergují ke ξ, limita zlomku vpravo je 1. Jelikož zároveň qn−1qn<0, máme σ(ξn+1)<0 pro dostatečně velká n. Z toho plyne
0<ξn+1−σ(ξn+1)=An+1+dBn+1−An+1−dBn+1=2dBn+1.
Tím víme, že Bn+1>0. Zároveň si ze vztahu pro Bn+1 můžeme vyjádřit
An+12+BnBn+1=d.
Jelikož d je fixní a oba výrazy vlevo jsou kladné, musí být omezené. Tuďíz existuje jen konečně mnoho možností pro hodnoty An,Bn a podle 🐦holubníkového principu🐦 se musí někdy opakovat.
Věta Řetězový zlomek kvadratického čísla ξ je čistě periodický, právě když ξ>1 a jeho algebraický doplněk ξ′∈(−1,0).
Důkaz
(⇒)
Nechť ξ=[a0;a1,…,al−1¯]. Potom speciálně
ξ=ξlpl−1+pl−2ξlql−1+ql−2.
Z toho
ξ2ql−1+ξ(ql−2−pl−1)−pl−2=0.
Označme
f(x)≔x2ql−1+x(ql−2−pl−1)−pl−2.
Potom f(ξ)=0, takže i f(ξ′)=0. Zároveň
f(−1)=(ql−1−ql−2)+(pl−1−pl−2)>0,
f(0)=−pl−2<0.
Z grafu kvadratické funkce potom plynou nerovnosti pro ξ′.
(⇐)
Nechť ξ je kvadratické číslo splňující předpoklady. Dokážeme indukcí, že také pro všechna n∈ℕ platí ξn>1,ξn′∈(−1,0).
ξn+1=1ξn−an>1;ξn+1′=σ(ξn+1)=1ξn′−an∈(−1,0).
Tuto skutečnost můžeme zapsat jako
−1<ξn′=an+1ξn+1′<0
neboli
−1−1ξn+1′<an<−1ξn+1′.
Z toho plyne
an=⌊1ξn+1′⌋.
Podle předchozí věty existují n<m taková, že ξn+1=ξm+1. Dokážeme, že také ξn=ξm.
ξn=an+1ξn+1=⌊−1ξn+1′⌋+1ξn+1=⌊−1ξm+1′⌋+1ξm+1=am+1ξm+1=ξm.
Iterací dostaneme ξ0=ξm−n, takže řetězový zlomek je čistě periodický.
Příklad Pro dané d∈ℕ, které není čtverec, zvolme ξ≔⌊d⌋+d>1. Potom ξ′=⌊d⌋−d∈(0,1). Takže existuje l∈ℕ takové, že
ξ=[2⌊d⌋;a1,a2,…,al−1¯].
Z toho
d=ξ−⌊d⌋=[⌊d⌋;a1,a2,…,al−1,2⌊d⌋¯].
Například
41=[6;2,2,12¯].

Pellova rovnice

Nechť d∈ℕ,d∉ℚ,B∈ℤ. Máme najít taková x,y∈ℤ, že

x2−d⋅y2=B.
Věta Nechť |B|<d. Pokud x⟂y jsou řešení Pellovy rovnice, potom xy=pnqn, kde pnqn je sblížený zlomek pro d.
Důkaz Uvažujme nejprve B>0. Z Pellovy rovnice máme
0<(x−dy)(x+dy)=B.
Přeuspořádáním dostaneme
0<x−dy=Bx+dy,
0<xy−d=By2(xy+d)<d2y2d=12y2.
Již víme, že platí-li |ξ−pq|<12q2, potom pq je sblížený zlomek pro ξ. Z toho plyne tvrzení věty. Pro B<0 si rovnici vydělíme −d:
y2−−x2d=−Bd>0.
Jelikož −Bd<1d, tím jsme to převedli na předchozí případ, takže yx je sblížený zlomek pro 1d. Dokážeme, že je také sblížený pro d. Máme
d=[a0;a1,…,al−1,2a0¯],
1d=[0;a0,a1,…,al−1,2a0¯].
Sblížené zlomky pro d splňují rekurentní vztah
pn+1=an+1pn+pn−1,p0=a0,p1=1+a0a1,
qn+1=an+1qn+qn−1,q0=1,q1=a1.
Sblížené zlomky pro 1d splňují rekurentní vztah
p~n+1=anp~n+p~n−1,p~0=0,p~1=1,p~2=a1,
q~n+1=anq~n+q~n−1,q~0=1,q~1=a0,q~n=1+a0a+1.
Z toho
yx=p~n+1q~n+1=qnpn.
Příklad Pro d=41 si vypíšeme:
nanpnqnpn2−41qn2
0661−5
121325
22325−1
312397625
42826129−5
5220493201
612254143969−5
Takže víme, že rovnice x2−41y2=B má nesoudělná řešení pro B=±1,±5 a jak za chvíli uvidíme, pro jiná B s |B|≤6 nesoudělná řešení nemá. Ovšem může mít soudělná řešení. Například vezmeme-li nějaké řešení pro B=1, vynásobením dvěma dostaneme řešení pro B=4.
Věta Nechť (Bn) je posloupnost z důkazu Lagrangeovy věty příslušná ke ξ=d. Potom
pn2−d⋅qn2=(−1)n+1Bn+1.
Důkaz Máme vzorec
ξ=ξn+1pn+pn−1ξn+1qn+qn−1.
Aplikujeme-li ho speciálně na ξ=d, dostáváme
d=An+1+dBn+1pn+pn−1An+1+dBn+1qn+qn−1.
Roznásobením dostáváme
An+1pn+dpn+pn−1Bn+1=dAn+1qn+dqn+dqn−1Bn+1.
Porovnáme racionální a iracionální složky:
An+1pn+pn−1Bn+1=dqn,An+1qn+qn−1Bn+1=pn.
Vynásobíme první rovnost qn a druhou pn a odečteme je:
pn2−dqn2=Bn+1(qn−1pn−pn−1qn)=(−1)n+1Bn+1.
Důsledek Nechť l je perioda řetězového rozvoje pro d. Potom posloupnost pn2−d⋅qn2 je čistě periodická s periodou l, pokud l je liché, nebo 2l, pokud l je sudé.
Věta Nechť l je perioda řetězového rozvoje pro d. Potom
Důkaz Můžeme snadno ověřit, že posloupnost Bn je stejná pro d+⌊d⌋ jako pro d. Jsou-li ξn iterace k d+⌊d⌋, potom ξn>1,ξn′∈(−1,0), takže
0<ξn−ξn′=An+dBn=An−dBn=2dBn.
Z toho Bn>0, takže nemůže být Bn=−1. Zbývá dokázat ekvivalenci Bn=1⟺l|n:
(⇐)
Nechť n=k⋅l. Potom
An+dBn=ξk⋅l=ξ0=⌊d⌋+d∴Bn=1.
(⇒)
Nechť Bn=1, takže
ξn=An+dBn=An+d.
Ze vztahu ξn′∈(−1,0) plyne −1<An−d<0 neboli d−1<An<d. Z toho An=⌊d⌋, tudíž ξn=⌊d⌋+d=ξ0.
Důsledek Nechť d∈ℕ,d∉ℕ. Potom řešení x,y∈ℤ Pellovy rovnice x2−d⋅y2=−1 existuje, právě když perioda l řetězového zlomku pro d je lichá. Zároveň řešení Pellovy rovnice x2−d⋅y2=1 existuje a platí:
Věta Nechť d∈ℕ,d∉ℕ. Pak existuje řešení x0,y0∈ℤ rovnice x2−d⋅y2=1 takové, že každé řešení splňuje
x+d⋅y=±(x0+d⋅y0)n.
Důkaz Dokážeme, že
M≔{x+dy|x,y∈ℤ,x2−d⋅y2=1,x+d⋅y>0}.
je grupa vzhledem k násobení.
(x+d⋅y)⋅(x~+d⋅y~)=xx~+dyy~+d⋅(xy~+x~y),
1=(x2−d⋅y2)⋅(x~2−d⋅y~2)=(xx~+dyy2)2−d(xy~+x~y)2,
1x+d⋅y=x−d⋅y.
Už víme, že existuje nějaké řešení X,Y. Množine
N≔{z∈M|1<z≤X+d⋅Y}
je konečná. Označme x0+y0⋅d≔minN. TBD
Věta Existuje-li řešení rovnice x2−d⋅y2=B, potom jich existuje nekonečně mnoho.
Důkaz Nechť x~,y~ je jedno řešení a x0,y0 je „základní“ řešení rovnice x2−d⋅y2=1 z předchozí věty. Označme
x+d⋅y≔±(x~+y~⋅d)⋅(x0+y0⋅d)n.
TBD

Součet dvou čtverců

Uvažujme množinu

M≔{a2+b2|a,b∈ℤ}.
Pozorování Pro každé k∈ℕ je k2∈M.
Pozorování Je-li k∈ℕ,n∈M, potom k2⋅n∈M.
Pozorování Je-li n∈ℕ,n≡3(mod4), potom n∉M.
Věta Je-li n,n′∈M, potom n⋅n′∈M.
Důkaz Nechť n=a2+b2,n′=a′2+b′2. Potom
n⋅n′=(a⋅a′)2+(a⋅b′)2+(b⋅a′)2+(b⋅b′)2=(a⋅a′+b⋅b′)2+(a⋅b′−b⋅a′)2.
Poznámka Díky tomuto nás primárně zajímá, jaká prvočísla patří do M.
Definice Nechť n∈ℕ. Číslo y∈ℤn je kvadratický zbytek modulo n, pokud existuje x∈ℤn takové, že y=x2. Množinu všech kvadratických zbytků modulo n značíme ℛn.
Příklad ℛ2=ℛ3=ℛ4={0,1}.
Věta Pro každé n∈ℕ je #ℛn≤1+⌊n2⌋. Navíc je-li n∈ℙ, potom nastává rovnost.
Důkaz nerovnosti Je-li y=x2, potom také y=(−x)2. Každé y∈ℛn kromě 0 a n2 se tedy dá zapsat dvěma různými způsoby, což omezuje počet y, která se vůbec dají zapsat.
Důkaz rovnosti Nechť x1,x2∈ℤn splňují x12=x22. Potom 0=x12−x22=(x1−x2)⋅(x1+x2). Je-li n∈ℙ, potom ℤn je obor integrity, takže musí být x1=±x2.
Věta Je-li p∈ℙ, potom −1∈ℛp, právě když p=2 nebo p≡1(mod4).
Důkaz Pro p=2 zřejmé, takže předpokládejme, že p je liché. Na ℤp+ zavedeme ekvivalenci, kde x∼y, pokud y=±x nebo y=±x−1. Každá třída ekvivalence má velikost 2 nebo 4. Speciálně [1]∼={±1}. Pokud −1 je kvadratický zbytek, tedy −1=x2, potom existuje ještě jedna třída velikosti 2, a sice {±x}. Jinak už musí být všechny velikosti 4.
Věta Každé p∈ℙ,p≡1(mod4) se dá vyjádřit právě jedním způsobem jako součet dvou čtverců (až na pořadí).
Důkaz existence Nechť p=4k+1. Uvažujme zlomky pj pro j∈2k^. Všechny tyto zlomky jsou v základním tvaru a ostře větší než 2. Nechť pro dané konkrétní j je řetězový zlomek
pj=[a0;…,al].
Zjevně a0,al≥2. Podle vzorečku s kontinuálními polynomy máme
p=Kl+1(a0,…,al),j=Kl(a1,…,al).
Ze symetrie plyne
p=Kl+1(al,…,a0).
Pro nějaké i tedy platí
[al;…,a0]=Kl+1(al,…,a0)Kl(al−1,…,a0)=pi>2.
Z toho vidíme, že mezi našimi zlomky má každý svého kamaráda vzniklého obrácením řetězového zlomku. Navíc konkrétně p1=[p] je svůj vlastní kamarád. Jelikož zlomků je sudý počet, musí ještě nějaký další být svůj vlastní kamarád, tedy existuje 2≤j0≤2k takové, že řetězový zlomek pro pj0 je palindrom:
pj0=[b0;…,bt]=[bt;…,b0].
Dokážeme, že t je liché. Kdyby bylo sudé, tedy t=2s, potom
p=Kt+1(b0,…,bt)=K2s+1(b0,…,bs−1,bs,bs−1,…,b0).
Podle vzorečků pro kontinuální polynomy máme
p=Ks(b0,…,bs−1)⋅Ks+1(bs,…,b0)+Ks−1(b0,…,bs−2)⋅Ks(bs−1,…,b0)=Ks(b0,…,bs−1)⋅(Ks+1(b0,…,bs)+Ks−1(b0,…,bs−2)).
Jelikož b0≥2, toto je spor s předpokladem, že p je prvočíslo. Musí tedy být t=2s+1 neboli
p=Kt+1(b0,…,bt)=K2s+2(b0,…,bs−1,bs,bs,bs−1,…,b0).
Použijeme-li opět vzorečky, dostáváme
p=Ks+1(b0,…,bs)⋅Ks+1(bs,…,b0)+Ks(b0,…,bs−1)⋅Ks(bs−1,…,b0)=(Ks+1(b0,…,bs))2+(Ks(b0,…,bs−1))2.
Příklad Nechť p≔13. Rozepíšeme si
131=[13],132=[6;2],133=[4;3],134=[3;4],135=[2;1,1,2],136=[2;6].
Z toho vidíme, že
13=(K2(2,1))2+(K1(2))2=32+22.
Důkaz jednoznačnosti Předpokládejme pro spor, že p=a2+b2=c2+d2,a>b,c>d,a≠c. Vezměme řetězový zlomek
ab=[b0;…,bt]=Kt+1(b0,…,bt)Kt(b1,…,bt).
Jelikož p je prvočíslo, a⟂b a zlomek je v základním tvaru, takže můžeme porovnat:
a=Kn+1(b0,…,bt),b=Kn(b1,…,bt),
p=a2+b2=Kn+1(bt,…,b0)⋅Kn+1(b0,…,bt)+Kn(bt,…,b1)⋅Kn(b1,…,bt)=K2t+2(bt,…,b0,b0,…,bt)=K2t(bt,…,b0,b0,…,bt−2)+bt⋅K2t+1(bt,…,b0,b0,…,bt−1).
Označíme-li x≔K2t+1(bt,…,b0,b0,…,bt−1), potom z této rovnosti plyne p≥1+2x, tedy
2≤x≤p−12.
Zároveň označíme-li
p2k+1q2k+1≔[bt;…,b0,b0,…,bt],
z rovnosti s determinantem máme
−1=(−1)2t+1=pn−1⋅qn−qn−1⋅pn=K2t+1(bt,…,b0,b0,…,bt−1)⋅K2t+1(bt−1,…,b0,b0,…,bt)−K2t+2(bt,…,b0,b0,…,bt)⋅K2t(bt−1,…,b0,b0,…,bt−1)=x2−p⋅K2t(bt−1,…,b0,b0,…,bt−1).
Z toho vidíme, že x2≡−1(modp). Analogicky vezmeme-li řetězový zlomek
cd=[d0;…,ds]
a označíme y≔K2t+1(dt,…,d0,d0,…,dt−1), bude platit 2≤y≤p−12 a y2≡−1(modp). Z poznatků o kvadratických zbytcích máme x=y. Zároveň si můžeme rozepsat
px=K2t+2(bt,…,b0,b0,…,bt)K2t+1(bt−1,…,b0,b0,…,bt)=[b1;…,b0,b0,…,bt],
py=K2s+2(ds,…,d0,d0,…,ds)K2s+1(ds−1,…,d0,d0,…,ds)=[d1;…,d0,d0,…,ds].
Jelikož řetězový zlomek je určen jednoznačně, z rovnosti obou výrazů plyne t=s a bj=dj. Z toho už máme a=c a b=d.
Věta Číslo n∈ℕ se dá vyjádřit jako součet dvou čtverců, právě když každé prvočíslo kongruentní s 3 modulo 4 se v prvočíselném rozkladu n vyskytuje v sudé mocnině.
Důkaz
(⇐)
Stačí využít známá tvrzení o součtech dvou čtverců.
(⇒)
Předpokládejme pro spor, že n=a2+b2 a existuje p∈ℙ,p≡3(mod4) takové, že p2j−1|n a p2j∤n. Uvažujme nejmenší takové n. Dokážeme, že p|a,b. Kdyby p∤a, potom v ℤp existuje a−1. Potom z a2+b2=n vynásobením dostaneme (a⋅a−1)2+(b⋅a−1)≡0(modp). To by znamenalo, že −1 je kvadratický zbytek modulo p, což nejde. Analogicky pro b. Musí tedy být a=a~⋅p,b=b~⋅p. Z toho np2=a~2+b~2, což porušuje minimalitu.
Příklad
585=32⋅5⋅13=32⋅(12+22)⋅(32+22)=32⋅((1⋅3+2⋅2)2+(1⋅2−2⋅3)2)=32⋅(72+42)=212+122.
Také bychom mohli zvolit znaménka obráceně a dostali bychom
585=32⋅5⋅13=32⋅(12+22)⋅(32+22)=32⋅((1⋅3−2⋅2)2+(1⋅2+2⋅3)2)=32⋅(12+82)=32+242.
Z toho vidíme, že pro složená čísla nemusí být zápis jednoznačný.

Pythagorejské trojice

Pro jaká x,y,z∈ℕ platí x2+y2=z2? Jistě můžeme bez újmy na obecnosti předpokládat, že z⟂x⟂y⟂z. Zároveň x,y musí mít různou paritu, protože kdyby byla obě lichá, potom x2+y2≡2(mod4). Takže bez újmy na obecnosti x je sudé a y je liché.

Definice Pythagorejská trojice je trojice po dvou nesoudělných čísel x,y,z∈ℕ taková, že x je sudé, y je liché a platí x2+y2=z2.
Věta Nechť x,y,z∈ℕ. Potom x,y,z tvoří pythagorejskou trojici, právě když existují nesoudělná m,n∈ℕ,m≥n různé parity taková, že x=2mn,y=m2−n2,z=m2+n2.
Důkaz
(⇐)
Snadno ověříme, že platí x2+y2=z2, x je sudé a y je liché. Zbývá dokázat, že jsou nesoudělná. Kdyby d|x,y,z, potom i d|2m2,2n2. Jelikož y je liché, d musí být taky liché, takže d|nsd(m,n)=1.
(⇒)
Z rovnosti x2+y2=z2 plyne x2=(z−y)⋅(z+y). Jelikož x je sudé a y,z jsou lichá, můžeme psát
(x2)2=z−y2⋅z+y2.
Činitelé na pravé straně jsou nesoudělní, takže podle základni věty aritmetiky to musí být čtverce:
z+y2=m2,z−y2=n2.
Snadno ověříme, že tato m,n splňují podmínky věty.

Algebraická celá čísla

Definice Číslo α∈ℂ je algebraické celé, pokud existuje monický polynom f∈ℤ[x] s kořenem α. Množinu všech algebraických celých čísel značíme 𝔹.
Poznámka Je-li číslo algebraické celé, potom je algebraické.
Příklad Číslo 2 je algebraické celé, protože je kořenem polynomu x2−2.
Věta Racionální číslo je algebraické celé, právě když je celé. Jinými slovy, 𝔹∩ℚ=ℤ.
Důkaz Inkluze ⊃ je zřejmá. Dokážeme ⊂. Nechť f(pq)=0, kde p,q∈ℤ,q≥2 a f(x)=∑j=0najxj∈ℤ[x]. Takže
0=∑j=0naj⋅(pq)j.
Vynásobením qn dostaneme
0=∑j=0naj⋅pj⋅qn−j=an⋅pn+∑j=0n−1aj⋅pj⋅qn−j.
Jelikož sčítanec vpravo je dělitelný q, musí být i q|an, takže an≠1.
Poznámka Toto je vlastně speciální případ věty o racionálních kořenech.
Poznámka Množinu ℤ můžeme nazývat racionální celá čísla, abychom ji odlišili od algebraických celých čísel.

Předchozí věta vlastně říká, že racionální číslo je algebraické, právě když jeho minimální polynom je celočíselný. Tato myšlenka platí i obecně.

Lemma Gaussovo Nechť F,G,H∈ℤ[x],F=G⋅H. Dělí-li p∈ℙ všechny koeficienty f, potom dělí všechny koeficienty g nebo všechny koeficienty h.
Důkaz Uvažujeme-li F,G,H jako prvky ℤp[x], máme F=0. Jelikož ℤp[x] je obor integrity, musí být G=0∨H=0.
Věta Nechť α∈𝔸. Potom α∈𝔹, právě když minimální polynom α je celočíselný.
Důkaz Implikace doleva je triviální. Dokážeme implikaci doprava. Nechť f je monický celočíselný polynom s kořenem α a g je minimální polynom pro α. Potom jistě existuje monický h∈ℚ[x] takový, že f=g⋅h. Vezměme nejmenší r,s∈ℕ taková, že r⋅g∈ℤ[x] a s⋅h∈ℤ[x]. Předpokládejme pro spor, že r⋅s≠1. Nechť p je libovolný prvočíselný dělitel r⋅s. Potom p dělí všechny koeficienty r⋅s⋅f=(r⋅g)⋅(s⋅h), takže podle Gaussova lemmatu dělí všechny koeficienty r⋅g nebo s⋅h, což je spor s tím, že r,s jsme volili minimální takové, aby vznikly celočíselné polynomy.
Definice Polynom je primitivní, pokud největší společný dělitel jeho koeficientů je 1.