Thue lemma

A moduláris aritmetika , Thue lemma megállapítja, hogy bármely egész szám modulo $m$ leírható egy „ moduláris frakció ”, amelynek a számláló és a nevező is, a abszolút érték , emelkedett a négyzetgyök a $m$ . Az első bemutató, amelyet Axel Thue-nak tulajdonítottak, a fiókok elvét használja . Felvittük egy egész szám, $m$ modulo, amely -1 egy négyzet (különösen egy prímszám $m$ kongruens 1 modulo 4 ), és hogy egy egész szám $egy$ olyan, hogy $a 2 + 1 \equiv 0 mod m$ , ez a lemma ad expresszióját $m$ , mint két négyzet összege számít közéjük .

Államok

Hadd $m > 1$ , és $a$ két egész szám .

Minden valós számok $X$ és $Y$ olyan, hogy ${\ displaystyle 0 <Y \ leq m <XY}$ ,vannak olyan $x$ és $y$ egész számok , amelyek ${\ displaystyle ax \ equiv y {\ pmod {m}}, \ quad 1 \ leq x <X \ quad {\ text {és}} \ quad | y | <Y.}$

Shoup igazolja ezt az állítást abban az esetben, ha $X$ és $Y$ egész szám, majd $X = Y = 1 + ⌊ \sqrt m ⌋$ $-ra$ alkalmazza, $m esetén$ nem négyzet .

LeVeque a következő változatot részesíti előnyben $X = \sqrt m esetén$ : bármely valós $X esetén$ úgy , hogy $x$ és $y$ egész számok vannak , amelyek . Ezt a változatot a fenti állításból vezetjük le, egy valóshoz kellően közelihez alkalmazva . ${\ 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}$

jegyzet Általában az a megoldás

( x , y ),

amelynek létezését ez a lemma garantálja, nem egyedi, és maga az ésszerű

x ⁄ y

sem: például ha

m = a 2 + 1

és

X = Y = a + 1 \geq 2

, két megoldásunk van

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

. Más hipotézisek szerint - azonban nem kompatibilisek Thue lemmáival - a lehetséges megoldás egyedülálló.

Brauer és Reynolds tétel

Thue lemma generalizált helyett a két ismeretlen által s ismeretlenek , és a lineáris kongruencia a homogén rendszer r congruences társított mátrixot egész együtthatós a r sorok és s oszlopok: $x, y$ ${\ displaystyle x_ {1}, \ pontok, x_ {s}}$ ${\ displaystyle ax \ equiv y {\ pmod {m}}}$ ${\ displaystyle A = (a_ {i, j})}$

Ha akkor, akkor minden olyan pozitív valóság esetében, mint pl ${\ displaystyle r <s}$ ${\ displaystyle \ lambda _ {1}, \ dots, \ lambda _ {s}}$ ${\ displaystyle \ lambda _ {1} \ dots \ lambda _ {s}> m ^ {r}}$ , vannak olyan egész számok , mint ${\ displaystyle x_ {1}, \ pontok, 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 {és}} \ quad (x_ {1}, \ dots, x_ {s}) \ neq (0, \ pont, 0)}$ .

Tüntetések

Brauer és Reynolds tételének igazolása.
Jelöljük a legkisebb egész szám szigorúan kisebb, mint , hogy azt jelenti, hogy az egész része meghaladja a . Így van ${\ displaystyle \ mu _ {j}}$ $\ lambda _ {j}$ ${\ displaystyle 1+ \ mu _ {j}}$ $\ lambda _ {j}$ ${\ displaystyle 0 \ leq \ mu _ {j} <\ lambda _ {j} \ leq 1+ \ mu _ {j}.}$ A szám a egész szám s - tuple úgy, hogy ellenőrzi: $l$ ${\ displaystyle x = (x_ {1}, \ pontok, x_ {s})}$ ${\ displaystyle 0 \ leq x_ {j} \ leq \ mu _ {j} \ quad (j = 1, \ pontok, s)}$ ${\ displaystyle l = \ prod _ {j = 1} ^ {s} (1+ \ mu _ {j}) \ geq \ prod _ {j = 1} ^ {s} \ lambda _ {j}> m ^ {r}.}$ Ez szigorúan nagyobb, mint a számos lehetséges értékei r sorok képek által . Következésképpen (a fiókok elve szerint) két különálló s- iplet van, amelyeknek ugyanaz a képe. Különbségük a meghirdetett megoldás . ${\ displaystyle (\ mathbb {Z} / m \ mathbb {Z}) ^ {r}}$ ${\ displaystyle x \ mapsto Ax}$ $x$
Bizonyíték Thue lemmájára.
Alkalmazzuk Brauer és Reynolds tételét az adott esetre , megjegyezve az ismeretlent és annak felső határát . A hipotézisek és (ezért ) biztosítja, hogy létezik egy pár egész számok olyan, hogy , és a . Mivel a több volt ezért nem nulla (különben az is lenne, mivel egybevágna a moddal ). Végül, még ha szükséges is az ellenkezőjére cserélni , pozitív. ${\ 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$

Alkalmazás két négyzet összegére

Thue lemma lehetővé teszi például a következő állítás bizonyítását, amely hasznos a két négyzet tételben :

Ha akkor egész számok vannak köztük, akkor és . ${\ displaystyle -1 \ equiv a ^ {2} {\ pmod {m}}}$ ${\ displaystyle u, v> 0}$ ${\ displaystyle au \ equiv v {\ pmod {m}}}$ ${\ displaystyle m = u ^ {2} + v ^ {2}}$

Demonstráció

Ha Thue lemmáját alkalmazzuk, majd kiválasztjuk a ( vagy a jeltől függően ), megkapjuk és . ${\ 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}}}$

Ezután észre, hogy vagy szigorúan kisebb, mint akkor is, ha egy négyzet . Valóban, ha egy egész számra (szükségszerűen páratlan), akkor ezt könnyen megmutatjuk . $u$ $v$ ${\ displaystyle {\ sqrt {m}}}$ $m$ ${\ displaystyle a ^ {2} \ equiv -1 {\ pmod {n ^ {2}}}}$ $n> 1$ ${\ displaystyle an \ not \ equiv n {\ pmod {n ^ {2}}}}$

Erre következtetünk (mivel és ). ${\ displaystyle u ^ {2} + v ^ {2} = m}$ ${\ displaystyle 0 <u ^ {2} + v ^ {2} <2m}$ ${\ displaystyle u ^ {2} + v ^ {2} \ equiv 0 {\ pmod {m}}}$

Végül, és legyenek elsődlegesek egymás között, mert ha megoszt , akkor tehát . $u$ $v$ $d$ $u$ $v$ ${\ displaystyle md \ mid (a ^ {2} +1) u ^ {2} + (v-au) (v + au) = u ^ {2} + v ^ {2} = m}$ ${\ displaystyle d \ közepén 1}$

Ezzel szemben, ha a és prím legyen (tehát prím $m$ ), akkor $-1$ a négyzet modulo $m$ egész szám meghatározott modulo $m$ által . ${\ displaystyle m = u ^ {2} + v ^ {2}}$ $u$ $v$ $nál nél$ ${\ displaystyle au \ equiv v {\ pmod {m}}}$

Hivatkozások

1917-ben vagy 1902-ben:
- (nem) A. Thue, „Et bevis for at lignigen A 3 + B 3 = С 3 er remigig i hele fra nul forsk jellige tal A, B og С”, Archiv. a Math számára. og Naturvid , vol. 34, n o 15, 1917 szerint (a) Alfred Brauer , és RL Reynolds, " volt tétele Aubry-Thue " , Canad. J. Math. , vol. 3,1951, P. 367-374 ( DOI 10.4153 / CJM-1951-042-6 )és (in) William J. LeVeque (en) , A számelmélet alapjai , Dover ,2014( 1 st szerk. 1977) ( olvasható online ) , p. 180 ;
- (nem) A. Thue , „ Et par antydninger til en taltheoretisk metode ” , Kra. Vidensk. Selsk. Forh. , vol. 7,1902, P. 57-75Szerint a Pete L. Clark, „ Thue lemma és bináris formában ”2010( DOI 10.1.1.151.636 ) .
(a) Carl Löndahl, " Előadás összegeket négyzetek " ,2011.
LeVeque 2014 , p. 182., előnézet a Google Könyvekben .
(a) Victor Shoup , A Computational Bevezetés a számelmélet és az algebra , UPC ,2005( online olvasható ) , p. 43, 2.33. tétel.
Shoup 2005 , p. 43. tétel, 2.34.
A LeVeque 2014 verziójában , p. E lemma 180-ban az elengedhetetlen hipotézis helyébe a következő lép lép , és a LeVeque további hipotézise nem elegendő ahhoz, hogy garantálja azt a kiegészítő feltételt, amelyet következtetésében megfogalmaz. ${\ displaystyle X> 1}$ $X> 0$ ${\ displaystyle a \ not \ equiv 0 {\ pmod {m}}}$ $y \ neq 0$
Shoup 2005 , p. 90.
Brauer és Reynolds 1951 , átírva a LeVeque 2014-ben , p. 179., előnézet a Google Könyvekben .
Ha többet feltételezünk , akkor még ${\ displaystyle \ lambda _ {i} \ leq m}$ ${\ displaystyle (x_ {1}, \ dots, x_ {s}) \ not \ equiv (0, \ dots, 0) {\ pmod {m}}.}$

Kapcsolódó cikkek