Lemma ze Thue
V modulární aritmetice , Thue lemma zjistí, že některý celé číslo modulo m mohou být reprezentovány pomocí „ modulární frakce “, jehož čitatel a jmenovatel jsou, v absolutní hodnotě , zvýšená o druhou odmocninou z m . První ukázka, kterou připisuje Axel Thue , využívá princip zásuvek . Nanáší se na celé číslo m modulo která -1 je čtverec (zejména na prvočíslo m shodné s 1 modulo 4 ) a celé číslo tak, že se 2 + 1 ≡ 0 mod m , tento lemma poskytuje expresi m jako součet dvou čtverců mezi nimi .
Státy
Nechť m > 1 a jen dvě celá čísla .
Pro všechny reality X a Y takové0<Y≤m<XY{\ displaystyle 0 <Y \ leq m <XY},jsou celá čísla x a y tak, ženaX≡y(modm),1≤X<Xa|y|<Y.{\ displaystyle ax \ equiv y {\ pmod {m}}, \ quad 1 \ leq x <X \ quad {\ text {a}} \ quad | y | <Y.}
Shoup dokazuje toto tvrzení v konkrétním případě, kdy X a Y jsou celá čísla, pak jej aplikuje na X = Y = 1 + ⌊ √ m ⌋ , pro m není čtvercový .
LeVeque upřednostňuje použít následující variantu na X = √ m : pro každé skutečné X takové, že existují celá čísla x a y taková, že . Tato varianta je odvozena z výše uvedeného tvrzení, aplikovaná na reálné dostatečně blízké .
1<X<m{\ displaystyle 1 <X <m}naX≡y(modm),1≤X<Xa|y|≤m/X{\ displaystyle ax \ equiv y {\ pmod {m}}, \ quad 1 \ leq x <X \ quad {\ text {et}} \ quad | y | \ leq m / X}Y>m/X{\ displaystyle Y> m / X}m/X{\ displaystyle m / X}
Poznámka
Obecně platí, že řešení
( x , y ), které toto lemma zaručuje, není jedinečné a samotné
racionální x ⁄ y není: například pokud
m = a 2 + 1 a
X = Y = a + 1 ≥ 2 , máme dvě řešení
( x , y ) = (1, a ), ( a , –1) .
Podle jiných hypotéz - nekompatibilních s hypotézami Thueova lemmatu - je však možné řešení jedinečné.
Brauerova a Reynoldsova věta
Thue lemma je celkové nahrazením dvě neznámé podle y neznámých a lineární shodnost homogenním systémem r shodností spojených s matricí s celočíselnými koeficienty s r řadách a to sloupce:
X,y{\ displaystyle x, y}X1,...,Xs{\ displaystyle x_ {1}, \ dots, x_ {s}} naX≡y(modm){\ displaystyle ax \ equiv y {\ pmod {m}}} NA=(nai,j){\ displaystyle A = (a_ {i, j})}
Pokud tedy, pro všechny pozitivní reality , jako je
r<s{\ displaystyle r <s}λ1,...,λs{\ displaystyle \ lambda _ {1}, \ tečky, \ lambda _ {s}}λ1...λs>mr{\ displaystyle \ lambda _ {1} \ tečky \ lambda _ {s}> m ^ {r}},
existují celá čísla jako např
X1,...,Xs{\ displaystyle x_ {1}, \ dots, x_ {s}}∑j=1snai,jXj≡0(modm)(i=1,...,r),|Xj|<λj(j=1,...,s)a(X1,...,Xs)≠(0,...,0){\ displaystyle \ sum _ {j = 1} ^ {s} a_ {i, j} x_ {j} \ ekviv 0 {\ pmod {m}} \ quad (i = 1, \ dots, r), \ quad | x_ {j} | <\ lambda _ {j} \ quad (j = 1, \ dots, s) \ quad {\ text {and}} \ quad (x_ {1}, \ dots, x_ {s}) \ neq (0, \ tečky, 0)}.
Demonstrace
-
Důkaz Brauerovy a Reynoldsovy věty.
Označme nejmenší číslo striktně nižší než , to znamená, že je celý díl přebytku o . Takže mámeμj{\ displaystyle \ mu _ {j}}λj{\ displaystyle \ lambda _ {j}}1+μj{\ displaystyle 1+ \ mu _ {j}}λj{\ displaystyle \ lambda _ {j}}0≤μj<λj≤1+μj.{\ displaystyle 0 \ leq \ mu _ {j} <\ lambda _ {j} \ leq 1+ \ mu _ {j}.}Počet z celé číslo s - tic tak, že ověřuje:l{\ displaystyle l} X=(X1,...,Xs){\ displaystyle x = (x_ {1}, \ tečky, x_ {s})}0≤Xj≤μj(j=1,...,s){\ displaystyle 0 \ leq x_ {j} \ leq \ mu _ {j} \ quad (j = 1, \ tečky, s)}l=∏j=1s(1+μj)≥∏j=1sλj>mr.{\ displaystyle l = \ prod _ {j = 1} ^ {s} (1+ \ mu _ {j}) \ geq \ prod _ {j = 1} ^ {s} \ lambda _ {j}> m ^ {r}.}Je striktně vyšší než počet možných hodnot r n-tic obrázků v aplikace . V důsledku toho (podle principu zásuvek) existují dva odlišné s -uplety se stejným obrázkem. Jejich rozdílem je inzerované řešení .(Z/mZ)r{\ displaystyle (\ mathbb {Z} / m \ mathbb {Z}) ^ {r}}X↦NAX{\ displaystyle x \ mapsto sekera}X{\ displaystyle x}
-
Důkaz Thueova lemmatu.
Aplikujme Brauerovu a Reynoldsovu větu na konkrétní případ , všimněme si neznámého a jeho horní hranice . Předpoklady a (proto ) zajistit existenci dvojice celých čísel taková, že , a . Protože více bylo tedy není nula (jinak by to také bylo, protože by to bylo shodné s modem ). A konečně, i když je to nutné nahradit jeho opakem, je pozitivní.s=2,r=1,NA=(na,-1){\ displaystyle s = 2, r = 1, A = (a, -1)}(X,y){\ displaystyle (x, y)}(X1,X2){\ displaystyle (x_ {1}, x_ {2})}(X,Y){\ displaystyle (X, Y)}(λ1,λ2){\ displaystyle (\ lambda _ {1}, \ lambda _ {2})}Y>0{\ displaystyle Y> 0}XY>m{\ displaystyle XY> m}X>0{\ displaystyle X> 0}(X,y)≠(0,0){\ displaystyle (x, y) \ neq (0,0)}naX≡y(modm){\ displaystyle ax \ equiv y {\ pmod {m}}}|X|<X{\ displaystyle | x | <X}|y|<Y{\ displaystyle | y | <Y}Y≤m{\ displaystyle Y \ leq m}|y|<m{\ displaystyle | y | <m}X{\ displaystyle x}y{\ displaystyle}0{\ displaystyle 0}m{\ displaystyle m}(X,y){\ displaystyle (x, y)}X{\ displaystyle x}
Aplikace na součty dvou čtverců
Thueovo lemma umožňuje například dokázat následující tvrzení, užitečné v teorému o dvou čtvercích :
Pokud pak jsou mezi nimi celá čísla taková, že a .-1≡na2(modm){\ displaystyle -1 \ equiv a ^ {2} {\ pmod {m}}}u,proti>0{\ displaystyle u, v> 0}nau≡proti(modm){\ displaystyle au \ equiv v {\ pmod {m}}}m=u2+proti2{\ displaystyle m = u ^ {2} + v ^ {2}}
Demonstrace
Aplikováním Thueova lemmatu na výběr nebo nebo (v závislosti na znaménku ) získáme a .
X=Y=m+1{\ displaystyle X = Y = {\ sqrt {m + 1}}}(u,proti)=(X,y){\ displaystyle (u, v) = (x, y)}(-y,X){\ displaystyle (-y, x)}y{\ displaystyle}1≤u,proti≤m{\ displaystyle 1 \ leq u, v \ leq {\ sqrt {m}}}nau≡proti(modm){\ displaystyle au \ equiv v {\ pmod {m}}}
Pak si všimneme, že nebo je přísně menší než , i když je to čtverec . Ve skutečnosti, pokud pro celé číslo (nutně liché), snadno to ukážeme .
u{\ displaystyle u}proti{\ displaystyle v}m{\ displaystyle {\ sqrt {m}}}m{\ displaystyle m}na2≡-1(modne2){\ displaystyle a ^ {2} \ equiv -1 {\ pmod {n ^ {2}}}}ne>1{\ displaystyle n> 1}nane≢ne(modne2){\ displaystyle a \ not \ equiv n {\ pmod {n ^ {2}}}}
Dedukujeme to (od a ).
u2+proti2=m{\ displaystyle u ^ {2} + v ^ {2} = m}0<u2+proti2<2m{\ displaystyle 0 <u ^ {2} + v ^ {2} <2m}u2+proti2≡0(modm){\ displaystyle u ^ {2} + v ^ {2} \ equiv 0 {\ pmod {m}}}
Konečně, a jsou mezi sebou nejlepší, protože pokud se rozdělí, a pak proto .
u{\ displaystyle u}proti{\ displaystyle v}d{\ displaystyle d}u{\ displaystyle u}proti{\ displaystyle v}md∣(na2+1)u2+(proti-nau)(proti+nau)=u2+proti2=m{\ displaystyle md \ mid (a ^ {2} +1) u ^ {2} + (v-au) (v + au) = u ^ {2} + v ^ {2} = m}d∣1{\ displaystyle d \ mid 1}
Naopak, pokud se a prime k sobě navzájem (tedy penetrovat m ), pak -1 je čtverec modulo m o celé číslo je definováno modulo m u .
m=u2+proti2{\ displaystyle m = u ^ {2} + v ^ {2}}u{\ displaystyle u}proti{\ displaystyle v}na{\ displaystyle a}nau≡proti(modm){\ displaystyle au \ equiv v {\ pmod {m}}}
Reference
-
V roce 1917 nebo 1902:
-
(ne) A. Thue, „Et bevis for at lignigen A 3 + B 3 = С 3 er remulig i hele fra nul forsk jellige tal A, B og С“, Archiv. pro matematiku. og Naturvid , sv. 34, n o 15, 1917, v souladu s (v) Alfred Brauer a RL Reynolds, " byl věta Aubry-Thue " , Canad. J. Math. , sv. 3,1951, str. 367-374 ( DOI 10.4153 / CJM-1951-042-6 )a (ne) William J. LeVeque (en) , Základy teorie čísel , Dover ,2014( 1 st ed. 1977) ( číst on-line ) , str. 180 ;
-
(ne) A. Thue , „ Et par antydninger til en taltheoretisk metode “ , Kra. Vidensk. Selsk. Forh. , sv. 7,1902, str. 57-75Podle k Pete L. Clark, „ Thue lemma a binárním formátu ,“2010( DOI 10.1.1.151.636 ) .
-
(in) Carl Löndahl, „ Přednáška o součtech čtverců “ ,2011.
-
LeVeque 2014 , s. 182, náhled v Knihách Google .
-
(in) Victor Shoup , Výpočetní úvod do teorie čísel a algebry , UPC ,2005( číst online ) , s. 43věta 2.33.
-
Shoup 2005 , str. 43, věta 2.34.
-
Ve verzi LeVeque 2014 , s. 180 tohoto lemmatu je nepostradatelná hypotéza nahrazena a další hypotéza LeVeque nestačí k zajištění dodatečné podmínky, kterou uvádí ve svém závěru.X>1{\ displaystyle X> 1}X>0{\ displaystyle X> 0}na≢0(modm){\ displaystyle a \ not \ equiv 0 {\ pmod {m}}}y≠0{\ displaystyle y \ neq 0}
-
Shoup 2005 , str. 90.
-
Brauer a Reynolds 1951 , přepsáno v LeVeque 2014 , s. 179, náhled v Knihách Google .
-
Pokud předpokládáme více , máme dokonceλi≤m{\ displaystyle \ lambda _ {i} \ leq m}(X1,...,Xs)≢(0,...,0)(modm).{\ displaystyle (x_ {1}, \ dots, x_ {s}) \ not \ equiv (0, \ dots, 0) {\ pmod {m}}.}
Související články
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">