Lemma of Thue

I modulær aritmetikk , Thue s LEMMA fastslår at et hvilket som helst heltall modulo $m$ kan representeres ved en “ modulær fraksjon ” hvis teller og nevner er, i absolutt verdi , økes ved kvadratroten av $m$ . Den første demonstrasjonen, tilskrevet Axel Thue , bruker prinsippet om skuffer . Påført et heltall $m$ modulo som –1 er et kvadrat (spesielt et primtall $m$ kongruent til 1 modulo 4 ) og et helt tall $a$ slik at $et 2 + 1 \equiv 0 mod m$ , gir dette lemma et uttrykk for $m$ som summen av to firkanter prime mellom dem .

Stater

La $m > 1$ og $en$ to heltall .

For alle Real $X$ og $Y$ slik at ${\ displaystyle 0 <Y \ leq m <XY}$ ,det er heltall $x$ og $y$ slik at ${\ displaystyle ax \ equiv y {\ pmod {m}}, \ quad 1 \ leq x <X \ quad {\ text {and}} \ quad | y | <Y.}$

Shoup beviser denne påstanden i det spesielle tilfellet der $X$ og $Y$ er heltall, og bruker den deretter på $X = Y = 1 + ⌊ \sqrt m ⌋$ , for $m$ ikke kvadratisk .

LeVeque foretrekker å bruke følgende variant på $X = \sqrt m$ : for enhver ekte $X$ slik at det er heltall $x$ og $y$ slik at . Denne varianten er trukket fra utsagnet ovenfor, brukt på en virkelig tilnærmet nær . ${\ displaystyle 1 <X <m}$ ${\ displaystyle ax \ equiv y {\ pmod {m}}, \ quad 1 \ leq x <X \ quad {\ text {et}} \ quad | y | \ leq m / X}$ ${\ displaystyle Y> m / X}$ ${\ displaystyle m / X}$

Merk Generelt er oppløsningen

( x , y )

som denne lemma garanterer at det eksisterer ikke er unik, og rasjonell

x / y

i seg selv er ikke: for eksempel hvis

m = et 2 + 1

X = Y = a + 1 \geq 2

, har vi to løsninger

( x , y ) = (1, a ), ( a , -1)

. Under andre hypoteser - uforenlig med Thues lemma - er den mulige løsningen unik.

Brauer og Reynolds teorem

Thues lemma generaliseres ved å erstatte de to ukjente med s ukjente og lineær kongruens med det homogene systemet med r kongruenser assosiert med en matrise med heltallskoeffisienter med r rader og s kolonner: $x, y$ ${\ displaystyle x_ {1}, \ prikker, x_ {s}}$ ${\ displaystyle ax \ equiv y {\ pmod {m}}}$ ${\ displaystyle A = (a_ {i, j})}$

Hvis da, for alle positive realer som ${\ displaystyle r <s}$ ${\ displaystyle \ lambda _ {1}, \ prikker, \ lambda _ {s}}$ ${\ displaystyle \ lambda _ {1} \ dots \ lambda _ {s}> m ^ {r}}$ , det er heltall som ${\ displaystyle x_ {1}, \ prikker, x_ {s}}$ ${\ displaystyle \ sum _ {j = 1} ^ {s} a_ {i, j} x_ {j} \ equiv 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, \ prikker, 0)}$ .

Demonstrasjoner

Bevis på Brauer og Reynolds teorem.
La oss betegne det minste heltallet strengt mindre enn , det vil si at er heltall del i overkant av . Så det har vi gjort ${\ displaystyle \ mu _ {j}}$ $\ lambda _ {j}$ ${\ displaystyle 1+ \ mu _ {j}}$ $\ lambda _ {j}$ ${\ displaystyle 0 \ leq \ mu _ {j} <\ lambda _ {j} \ leq 1+ \ mu _ {j}.}$ Antallet av heltall s - tuppeler slik at verifiserer: $l$ ${\ displaystyle x = (x_ {1}, \ prikker, x_ {s})}$ ${\ displaystyle 0 \ leq x_ {j} \ leq \ mu _ {j} \ quad (j = 1, \ dots, s)}$ ${\ displaystyle l = \ prod _ {j = 1} ^ {s} (1+ \ mu _ {j}) \ geq \ prod _ {j = 1} ^ {s} \ lambda _ {j}> m ^ {r}.}$ Det er strengt tatt er større enn antall mulige verdier for r tuppeler bilder i ved . Følgelig (i henhold til prinsippet i skuffene) er det to forskjellige s -upletter som har samme bilde. Forskjellen deres er den annonserte løsningen . ${\ displaystyle (\ mathbb {Z} / m \ mathbb {Z}) ^ {r}}$ ${\ displaystyle x \ mapsto Axe}$ $x$
Bevis på Thues lemma.
La oss bruke Brauer og Reynolds 'teorem på det spesielle tilfellet , og merke oss det ukjente og dets øvre grense . Hypotesene og (derfor ) sikre eksistensen av et par heltall slik at , og . Som mer var derfor ikke er null (ellers ville det være for, siden det ville være kongruent til mod ). Til slutt, selv om det er nødvendig for å erstatte det med det motsatte, er det positivt. ${\ displaystyle s = 2, r = 1, A = (a, -1)}$ $(x, y)$ ${\ displaystyle (x_ {1}, x_ {2})}$ $(X, Y)$ ${\ displaystyle (\ lambda _ {1}, \ lambda _ {2})}$ ${\ displaystyle Y> 0}$ ${\ displaystyle XY> m}$ $X> 0$ $(x, y) \ neq (0,0)$ ${\ displaystyle ax \ equiv y {\ pmod {m}}}$ ${\ displaystyle | x | <X}$ ${\ displaystyle | y | <Y}$ ${\ displaystyle Y \ leq m}$ ${\ displaystyle | y | <m}$ $x$ $y$ ${\ displaystyle 0}$ $m$ $(x, y)$ $x$

Bruk på summen av to firkanter

Thues lemma tillater for eksempel å bevise følgende proposisjon, nyttig i to-firkantet teorem :

Hvis det da er heltall mellom dem slik at og . ${\ displaystyle -1 \ equiv a ^ {2} {\ pmod {m}}}$ ${\ displaystyle u, v> 0}$ ${\ displaystyle au \ equiv v {\ pmod {m}}}$ ${\ displaystyle m = u ^ {2} + v ^ {2}}$

Demonstrasjon

Ved å bruke Thues lemma til å velge eller (avhengig av tegnet på ), får vi og . ${\ displaystyle X = Y = {\ sqrt {m + 1}}}$ ${\ displaystyle (u, v) = (x, y)}$ ${\ displaystyle (-y, x)}$ $y$ ${\ displaystyle 1 \ leq u, v \ leq {\ sqrt {m}}}$ ${\ displaystyle au \ equiv v {\ pmod {m}}}$

Vi merker da at eller er strengt mindre enn , selv om det er en firkant . Faktisk, hvis for et heltall (nødvendigvis rart), viser vi det enkelt . $u$ $v$ ${\ displaystyle {\ sqrt {m}}}$ $m$ ${\ displaystyle a ^ {2} \ equiv -1 {\ pmod {n ^ {2}}}}$ $n> 1$ ${\ displaystyle an \ not \ equiv n {\ pmod {n ^ {2}}}}$

Vi utleder det (siden og ). ${\ displaystyle u ^ {2} + v ^ {2} = m}$ ${\ displaystyle 0 <u ^ {2} + v ^ {2} <2m}$ ${\ displaystyle u ^ {2} + v ^ {2} \ equiv 0 {\ pmod {m}}}$

Endelig, og er førsteklasses innbyrdes fordi hvis deler seg og da derfor . $u$ $v$ $d$ $u$ $v$ ${\ displaystyle md \ mid (a ^ {2} +1) u ^ {2} + (v-au) (v + au) = u ^ {2} + v ^ {2} = m}$ ${\ displaystyle d \ mid 1}$

Motsatt, hvis med og prime til hverandre (derfor prime med $m$ ) deretter $-1$ er firkantet modulo $m$ av det hele tall definert modulo $m$ av . ${\ displaystyle m = u ^ {2} + v ^ {2}}$ $u$ $v$ $på$ ${\ displaystyle au \ equiv v {\ pmod {m}}}$

Referanser

I 1917 eller 1902:
- (nei) 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. for matematikk. og Naturvid , vol. 34, nr . 15, 1917, ifølge (i) Alfred Brauer og RL Reynolds, " var teorem om Aubry-Thue " , Canad. J. Math. , vol. 3,1951, s. 367-374 ( DOI 10.4153 / CJM-1951-042-6 )og (i) William J. LeVeque (en) , Fundamentals of Number Theory , Dover ,2014( 1 st ed. 1977) ( lest på nettet ) , s. 180 ;
- (nei) A. Thue , “ Et par antydninger til en taltheoretisk metode ” , Kra. Vidensk. Selsk. Forh. , vol. 7,1902, s. 57-75Ifølge til Pete L. Clark, “ Thue sin Lemma og binærform ”,2010( DOI 10.1.1.151.636 ) .
(i) Carl Löndahl, " Foredrag om summer av firkanter " ,2011.
LeVeque 2014 , s. 182, forhåndsvisning på Google Bøker .
(in) Victor Shoup , en beregningsinnføring til tallteori og algebra , UPC ,2005( les online ) , s. 43, teorem 2.33.
Shoup 2005 , s. 43, setning 2.34.
I versjonen av LeVeque 2014 , s. 180 av dette lemmaet erstattes den uunnværlige hypotesen med , og LeVeques tilleggshypotese er ikke tilstrekkelig for å garantere tilleggsbetingelsen som han sier i sin konklusjon. ${\ displaystyle X> 1}$ $X> 0$ ${\ displaystyle a \ not \ equiv 0 {\ pmod {m}}}$ $y \ neq 0$
Shoup 2005 , s. 90.
Brauer og Reynolds 1951 , transkribert i LeVeque 2014 , s. 179, forhåndsvisning på Google Bøker .
Hvis vi antar mer , har vi selv ${\ displaystyle \ lambda _ {i} \ leq m}$ ${\ displaystyle (x_ {1}, \ dots, x_ {s}) \ not \ equiv (0, \ dots, 0) {\ pmod {m}}.}$

Relaterte artikler