Thues lemma

Den här artikeln handlar om modulär aritmetik. För Thues sats om diofantiska approximationer, se Roths sats § Diskussion .

I modulär aritmetik , säger Thues lemma ungefär att varje modulärt heltal kan representeras av ett "modulärt bråktal" så att täljaren och nämnaren har absoluta värden som inte är större än kvadratroten av modulen.

Mer exakt, för varje par av heltal ( a , m ) med m > 1 , givet två positiva heltal X och Y så att X ≤ m < XY , finns det två heltal x och y så att

$ay\equiv x{\pmod {m}}$

och

$|x|<X,\quad 0<y<Y.$

Vanligtvis tar man X och Y lika med det minsta heltal större än kvadratroten ur m , men den allmänna formen är ibland användbar och gör unikhetssatsen (nedan) lättare att ange.

Det första kända beviset tillskrivs Axel Thue ( 1902 ) som använde ett duvhålsargument . Den kan användas för att bevisa Fermats teorem om summan av två kvadrater genom att ta m vara ett primtal p som är kongruent med 1 modulo 4 och ta a för att uppfylla en ² + 1 = 0 mod p . (Ett sådant " a " garanteras för " p " av Wilsons teorem .)

Unikhet

I allmänhet är lösningen vars existens hävdas av Thues lemma inte unik. Till exempel, när a = 1 finns det vanligtvis flera lösningar ( x , y ) = (1, 1), (2, 2), (3, 3), ... , förutsatt att X och Y inte är för små. Därför kan man bara hoppas på unikhet för det rationella talet x / y , till vilket a är kongruent modulo m om y och m är coprime . Ändå behöver detta rationella tal inte vara unikt; till exempel, om m = 5 , a = 2 och X = Y = 3 , har man de två lösningarna

$2a+1\equiv -a+2\equiv 0{\pmod {5}}$ .

Men för X och Y som är tillräckligt små, om det finns en lösning, är den unik. Mer exakt, med ovanstående notation, if

$2XY<m,$

och

$ay_{1}-x_{1}\equiv ay_{2}-x_{2}\equiv 0{\pmod {m} }$ ,

med

$\left|x_{1}\right|<X,\quad \left|y_{1}\right|<Y,$

och

$\left|x_{2}\right|<X,\quad \left|y_{2}\right|<Y,$

sedan

${\frac {x_{1}}{y_{1}}}={\frac {x_{2}}{y_{2}}}.$

Detta resultat är grunden för rationell rekonstruktion , vilket gör det möjligt att använda modulär aritmetik för att beräkna rationella tal för vilka man känner gränser för täljare och nämnare.

Beviset är ganska enkelt: genom att multiplicera varje kongruens med den andra y _i och subtrahera, får man

$y_{2}x_{1}-y_{1}x_{2}\equiv 0{\pmod {m}}.$

Hypoteserna antyder att varje term har ett absolut värde som är lägre än XY < m / 2 , och därmed att det absoluta värdet av deras skillnad är lägre än m . Detta innebär att ${\displaystyle y_{2}x_{1}-y_{1}x_{2}=0} ,$ därav resultatet.

Datorlösningar

Det ursprungliga beviset för Thues lemma är inte effektivt, i den meningen att det inte ger någon snabb metod för att beräkna lösningen. Den utökade euklidiska algoritmen tillåter oss att tillhandahålla ett bevis som leder till en effektiv algoritm som har samma beräkningskomplexitet som den euklidiska algoritmen .

Mer exakt, givet de två heltal m och a som förekommer i Thues lemma, beräknar den utökade euklidiska algoritmen tre sekvenser av heltal xi ) _och ( t i ₎ , ( ( y i ₎ så att

$t_{i}m+y_{i}a=x_{i}\quad {\text{for }}i=0,1,...,$

där x _i är icke-negativa och strikt minskande. Den önskade lösningen är, upp till tecknet, det första paret ( x _i , y _i ) så att x _i < X .

Se även

• Padé approximant , en liknande teori, för approximering av Taylor-serier med rationella funktioner

• Shoup, Victor (2005). En beräkningsintroduktion till talteori och algebra (PDF) . Cambridge University Press . Hämtad 26 februari 2016 .