Kiinatehtävä, osa 3

Tässä postauksessa käsitellään seuraavan tehtävän ratkaisu:

Kiinan IMO-joukkueen valintakoe 2, 2015, tehtävä 6

Osoita, että on olemassa äärettömän monta $n \in \mathbb{Z_+}$ joilla $n^2 + 1$ ei ole jaollinen millään alkuluvun neliöllä (engl. squarefree)

Ratkaisu

On luonnollista tutkia, milloin väite ei päde, eli milloin pätee $n^2 + 1 \equiv 0 \pmod{p^2}$ jollain alkuluvulla $p$. Tämä tietysti vaatii, että $n^2 + 1 \equiv 0 \pmod{p}$, eli $p \equiv 1 \pmod{4}$. Tämä ei kuitenkaan vielä anna riittävästi tietoa: ensinnäkin, onko jokaisella $p \equiv 1 \pmod{4}$ olemassa ratkaisu kongruenssiyhtälölle $x^2 + 1 \equiv 0 \pmod{p^2}$, ja toisekseen, kuinka monta (keskenään epäkongruenttia) ratkaisua yhtälöllä on? Nämä kysymykset ovat helppoja vastata:

Lemma 1

Kongruenssiyhtälöllä $x^2 + 1 \equiv 0 \pmod{p^2}$ on täsmälleen kaksi keskenään epäkongruenttia ratkaisua kaikilla alkuluvuilla $p \equiv 1 \pmod{4}$

Todistus

Kirjoitetaan $x = pk + y$, missä $0 \le k < p$ ja $0 \le y < p$ ovat muuttujia. Yhtälö muuttuu muotoon

$2pk + y^2 + 1 \equiv 0 \pmod{p^2}$

Saamme luotua kaksi ratkaisua: valitaan $y$ niin, että $y^2 \equiv -1 \pmod{p}$ (tämä on mahdollista). Kirjoitetaan $pt = y^2 + 1$ Nyt tulee enää valita $k$ niin, että $2pk + pt \equiv 0 \pmod{p^2}$, eli $k \equiv \frac{-t}{2} \pmod{p}$. Sillä $y$:lle on kaksi eri vaihtoehtoa, myös $x$:lle on kaksi eri vaihtoehtoa.

Todistetaan sitten, että useampaa ratkaisua ei ole. Olkoon $f(x) = x^2$. Oletetaan, että $f(a) \equiv f(b) \equiv -1 \pmod{p^2}$. Pyritään todistamaan, että $a \equiv \pm b \pmod{p^2}$. Lemman tulos seuraa tästä.

Pätee $0 \equiv f(a) - f(b) \equiv a^2 - b^2 \equiv (a-b)(a+b) \pmod{p^2}$

Jos $p^2 \mid a - b$, väite pätee, samoin jos $p^2 \mid a + b$. Voiko päteä $p \mid a - b$ ja $p \mid a + b$? Ei, sillä tästä seuraisi $p \mid 2a$, eli $p \mid a$. Mutta oletimme $f(a) \equiv -1 \pmod{p^2}$, joten tämä on ristiriita.

Huomautus Tarvitsemme lemmasta vain osuutta “enintään kaksi ratkaisua”.

Tehtävänannon väite seuraa nyt helpolla seula-argumentilla: jos valitsemme satunnaisen positiivisen kokonaisluvun $n$ kuinka suurella todennäköisyydellä $n^2 + 1$ on jaollinen jollain alkuluvun neliöllä? Emme voi kuitenkaan sanoa, että valitaan satunnainen positiivinen kokonaisluku: tulee valita jokin äärellisen kokoinen väli, jolta $n$ valitaan (aiemmin netissä on ollut ratkaisu, jossa näin ei tehdä. Ratkaisu polynomille $n^2 + 1$ ei juurikaan muutu, mutta postauksessa oli myös esitetty yleistys muillekin polynomeille. Todistus yleiselle tapaukselle oli virheellinen juurikin tästä syystä). Olkoon $N$ mielivaltaisen suuri luku, ja valitaan $n$ satunnaisesti väliltä $[1, N]$.

Kuinka monta $x \in [1, N]$ on olemassa, joilla $x^2 + 1 \equiv 0 \pmod{p^2}$, kun $p$ on annettu vakio? Lemman nojalla tämä on enintään $2\lceil \frac{N}{p^2} \rceil$. Täten niiden $n$ määrä, joilla $n^2 + 1 \equiv 0 \pmod{p^2}$ jollain $p$, kun $1 \le n \le N$, on enintään

$$\sum 2 \Big\lceil \frac{N}{p^2} \Big\rceil \le 2 \sum \frac{N}{p^2} + 1$$

missä summa käy läpi ne $p$, joilla $p \equiv 1 \pmod{4}$. Lisäksi summassa täytyy käydä vain ne $p$ läpi, joilla $N^2 + 1 \le p^2$, koska jos $p^2$ olisi suurempi kuin tämä, yhtälöllä $x^2 + 1 \equiv 0 \pmod{p^2}$ ei voi olla ratkaisua $1 \le x \le N$. Summa voidaan asettaa käymään läpi alkuluvut $p$, joilla $p \le N+1$.

Täten niiden $n$ määrä, joilla $n^2 + 1$ on neliövapaa, on

$$N - 2\sum\frac{N}{p^2} + 1 = N(1 - 2\sum \frac{1}{p^2}) - 2\sum1$$

Alkulukulauseen nojalla summa $2 \sum 1$ on kokoluokkaa $\frac{N+1}{\ln(N+1)}$ (tätä voi myös arvioida alaspäin vaikkapa arvoksi $\frac{N}{3}$), jos summa kävisi läpi kaikki alkuluvut väliltä $[1, N]$. Lisäksi summaa $\frac{1}{p^2}$ voidaan arvioida olevan alle $\frac{1}{4}$ seuraavasti, käyttäen faktaa $p \ge 5$ kaikilla summattavilla $p$:

$$\sum \frac{1}{p^2} \le \sum \frac{1}{p^2 - p} = \sum \frac{1}{p-1} - \frac{1}{p} \le (\frac{1}{4} - \frac{1}{5}) + (\frac{1}{5} - \frac{1}{6}) + \ldots = \frac{1}{4}$$

Täten

$$N(1 - 2\sum \frac{1}{p^2}) - 2\sum 1 \approx 0.5N - \frac{N+1}{\ln(N+1)} > 0.1N$$

kun $N$ on suuri.

Tämä todistaa väitteen.

Huomautus

Samaan tapaan voi todistaa väitteen kaikille toisen asteen polynomeille $P$ polynomin $n^2 + 1$ sijasta, joilla ei ole olemassa sellaista $p$, jolla $P(n) \equiv 0 \pmod{p^2}$ kaikilla $n$. Tämä on jätetty harjoitustehtäväksi postauksessa Henselin lemma.

Yleinen tapaus on kuitenkin avoin ongelma, vaikkakin tapaus $\deg(P) = 3$ on myös todistettu. Netistä löytää lisää hakusanalla “square-free values of polynomials”.