Osaisiko joku kertoa, miten ratkaistaan Baltic way 2009 -matematiikkakilpailun tehtävä 7?
Ks.
http://bw09.no/
http://bw09.no/index.php?page=4
Ks.
http://bw09.no/
http://bw09.no/index.php?page=4
Baltic way 2009 tehtävä 7?
Klaara de Wappen
11355
0Äänestä
Muut lukivat myös
Odottaa vastausta
Näihin keskusteluihin ei ole vielä vastattu. Ole ensimmäinen.
Vastaukset 11
Vanhimmat
Ensiksi a^4 b^4 c^4=2(a^2b^2 b^2c^2 a^2c^2) (mod p).
Toisaalta a^4 b^4 c^4=(a^2 b^2 c^2)^2-2(a^2b^2 b^2c^2 a^2c^2), joten p|a^2 b^2 c^2 ja (2b c)^2=-3c^2 mod p. Koska -3 ei ole neliönjäännös mod p koska p=-1 mod 3. Siten p|c. Vastaavasti p|a ja p|b.
kongruenssi näyttää hiukan tuulesta temmatulta.
Voisiko Matikkanörtti hiukan perustella?
a^4 b^4 c^4=a^2(b c)^2 b^2(c a)^2 c^2(a b)^2=2(a^2b^2 b^2c^2 c^2a^2) 2abc(a b c)=2(a^2b^2 b^2c^2 c^2a^2) (mod p).
mutta vielä jäi epäselväksi, millä logiikalla tuon kongruenssin
(2b c)^2=-3c^2 mod p
nappasit?
Oliko sinulla siihen jokin suoraviivainen päättelytapa?
Äh. Mokasin. Ajattelin asiaa liian väsyneenä.
on ihan oikeassa.
Se, miten päättely etenee, ei kuitenkaan täysin selviä hänen esityksestään.
Väite voidaan perustella vaikkapa näin:
0 == a^2 b^2 c^2
== (-b-c) ^2 b^2 c^2
= (b c) ^2 b^2 c^2
= b^2 2bc c^2 b^2 c^2
= 2(b^2 bc c^2) (mod p)
b^2 bc c^2 == 0 (mod p)
Toisaalta
(2b c)^2 = - 3c^2
4b^2 4bc c^2 = -3c^2
4(b^2 bc c^2) = 0
b^2 bc c^2 = 0
Erityisesti tämä pätee kongruensseilla mod p.
Jäljelle jää siis osoittaa, että -3 == p-3 (mod p) ei ole neliönjäännös mod p.
Itseäni kiinnostaisi nyt tietää, voidaanko tämä todistaa ilman neliönjäännösten resiprookkilausetta(, joka tietääkseni ei kuulu ainakaan Suomessa lukion oppimäärään).
Ainahan resiprookkilauseen voi purkaa auki, jolloin siihen ei tule vedottua. Todistus onnistuu kyllä ilmankin. Todistuksen on esittänyt nimimerkki Mathias_DK osoitteessa http://www.artofproblemsolving.com/Forum/viewtopic.php?f=56&t=347798 . Tosin en hoksaa, mistä todistuksen rivit 2 ja 4 tulevat.
tuolta löytyi. Kiitos sinulle vinkistä.
Mutta kerropas tarkemmin, mitä kohtia tuossa todistuksessa et ymmärrä.
Rivinumerot kun vaihtelevat riippuen käytetystä fontista ja näytön asetuksista.
Kirjoitin palstalle kohdat, joissa on ongelmia. Siis kohdasta Then b^3=c^3 kohtaan or p|b,c. Ja miksi on voimassa a^4=-2b^4 mod p?
olisi päätellä vaikkapa näin:
b^3 == c^3 (mod p)
=> (b^3)^((p 1)/3) == (c^3)^((p 1)/3) (mod p)
b^(p 1) == c^(p 1) (mod p)
b*b^p == c*c^p (mod p)
b*b == c*c (mod p) (Fermat'n pieni lause)
b^2 == c^2 (mod p)
Tätä käyttäen saadaan kongruenssista
b^3 == c^3 (mod p)
kongruenssit
bc^2 == c^3 (mod p) ja
b^2c == b^3 (mod p)
Nyt
(b-c)^3 = b^3 – 3b^2c 3bc^2 - c^3 = (b^3 – c^3) – 3(b^2c – bc^2)
== 0 (mod p)
Siten
b == c (mod p)
Nyt
0 == (b c)^4 b^4 c^4 == (2b)^4 2b^4 = 18 b^4 (mod p), joten
b == 0 (mod p)
Vastaavasti saadaan
c == 0 (mod p)
Kongruenssi
a^4 == -2b^4 (mod p)
seuraa kongruenssista
a^4 b^4 c^4 == 0 (mod p)
sijoittamalla c^4 == b^4 (mod p)
Tällöin saadaan
a^4 2b^4 == 0 (mod p), josta edelleen
a^4 == -2b^4 (mod p)
voisi mennä seuraavasti:
Merkitsemällä kongruenssioperaattoria kahdella peräkkäisellä yhtäsuuruusmerkillä saamme pienellä pyörittelyllä:
0 == a^4 b^2 c^4
== a^4 b^4 (-a-b)^4
== a^4 b^4 (a b)^4
== a^4 b^4 (a^4 4a^3b 6a^2b^2 4ab^3 b^4)
= 2( a^4 2a^3b 3a^2b^2 2ab^3 b^4)
= 2(a^2 ab b^2)^2 (mod p)
a^2 ab b^2 == 0 (mod p)
Jos a == 0 (mod p), niin myös b == 0 (mod p) ja edelleen c == 0 (mod p)
(Vast. b ja c, huom. symmetria)
Oletetaan, että a,b ja c ovat alkuluvulla p jaottomia.
Nyt
a^2 ab b^2 = kp, missä k on kokonaisluku
Tästä saadaan
a^2 ab b^2 -kp = 0
b^2 ab (a^2-kp) = 0
Toisen asteen yhtälön ratkaisukaavan mukaan
b = (-a /- sqrt(4kp – 3a^2)) /2
Juurrettavan on oltava neliö, ts on olemassa sellainen kokonaisluku d, että
4kp- 3a^2 = d^2
Siis
d^2 == -3a^2 (mod p)
Kerrotaan puolittain luvun a käänteisluvun mod p (merk.) e neliöllä saamme
(de)^2 == -3 (mod p)
Luvun -3 == p-3 (mod p) pitäisi siis olla neliönjäännös mod p.
Mutta laskemalla Legendren symbolin Gaussin menetelmällä saamme
(-3/p) = (p/3) = (-1/3) = -1
sillä ehdosta 6|(p 1) seuraa, että 3|(p 1) ts. p == -1 (mod 3).
Luku -3 on siis epäneliö mod p.
Tämä on ristiriita.
(Legendren symbolin laskemisesta katso englanninkielisen Wikipedian artikkeli ”Quadratic reciprocity” ja sieltä kappale otsikolla ”Gauss's version in Legendre symbols”, http://en.wikipedia.org/wiki/Quadratic_reciprocity )