P-adic valuation ja Lifting The Exponent lemma

$\newcommand{\syt}{\mathop{\rm syt}}$

Tässä postauksessa käsitellään $v_p$-notaatiota (tunnetaan englanniksi nimellä $p$-adic valuation) ja sen hyötyjä. Lisäksi esitetään Lifting The Exponent lemma (LTE) sekä sen todistus.

Tämän postauksen ajan muuttuja $p$ on varattu aina alkuluvuille.

Määritelmä

Olkoon $m \neq 0$ kokonaisluku. Olkoon $k$ se kokonaisluku, jolla $p^k \mid m$, mutta $p^{k+1} \nmid m$ (toisin sanoen alkuluvun $p$ eksponentti luvun $m$ alkutekijähajotelmassa). Sanomme, että $v_p(m) = k$.

Notaatio on usein myös jatkettu rationaaliluvuille: kirjoitamme $v_p(\frac{a}{b}) = v_p(a) - v_p(b)$. Tällöin $v_p$ saa myös negatiivisia arvoja, toisin kuin kokonaislukuarvoilla. Emme tule tarvitsemaan tässä postauksessa laajennettua määritelmää, joten sivuutamme niiden tarkemman tutkimisen. Lukija voi miettiä, miten tulokset yleistyvät rationaaliluvuille.

Usein määritellään $v_p(0) = \infty$. Käytämme tätä määritelmää.

$v_p$ ei siis ole mitään tämän ihmeellisempää. Yksi notaation tärkeimmistä piirteistä onkin vain alkutekijöiden eksponenteista puhumisen helpottaminen (vastaavasti, modulotkin ovat loppukädessä vain hyvin käytännöllinen notaatio jaollisuudelle).

Seuraavat faktat ovat suoraa seurausta määritelmästä:

Olkoot $a$ ja $b$ kokonaislukuja. Nyt,

1. $v_p(ab) = v_p(a) + v_p(b)$.
2. $a \mid b$ jos ja vain jos $v_p(a) \le v_p(b)$ kaikilla $p$.
3. $a = \pm b$ jos ja vain jos $v_p(a) = v_p(b)$ kaikilla $p$.
4. Jos $a \mid b$, $b \neq 0$, niin $v_p(\frac{a}{b}) = v_p(a) - v_p(b)$ (tämä pätee oikeastaan kaikilla rationaaliluvuilla $a, b \neq 0$).

Neliöluvun ja korkeampien potenssien käsite on helppo muotoilla $v_p$-notaatiolla: kokonaisluku $a$ on $n$:nnes potenssi jos ja vain jos $n \mid v_p(a)$ kaikilla $p$.

Lopuksi mainittakoon seuraava lemma:

Lemma 1

Olkoot $a$ ja $b$ kokonaislukuja.

$$v_p(a \pm b) \ge \min(v_p(a), v_p(b))$$

(Siis väite pätee yhteen- ja vähennyslaskulle)

Aito epäyhtälö vaatii $v_p(a) = v_p(b)$.

Huomautus

On hyvä huomata, että aito epäyhtälö todella voi päteä, esimerksiksi arvoilla $a = 1$, $b = p^{100} - 1$.

Todistus

Olkoon $c = \min(v_p(a), v_p(b))$. Nyt $p^c$ jakaa sekä luvun $a$ että luvun $b$, joten $p^c$ jakaa luvun $a \pm b$. Tämä todistaa väitteen $v_p(a \pm b) \ge \min(v_p(a), v_p(b))$. Jos taas $v_p(a) \neq v_p(b)$, luku $p^{c+1}$ jakaa täsmälleen toisen luvuista $a$ ja $b$, jolloin se ei jaa lukua $a \pm b$. Tällöin on $v_p(a \pm b) = c$.

Lemmaa 1 voi yleistää vastaavasti monelle summattavalle:

Lemma 1 (yleistys)

Olkoot $a_1, a_2, \ldots , a_n$ kokonaislukuja. Pätee

$$v_p(a_1 \pm a_2 \pm \ldots \pm a_n) \ge \min(v_p(a_1), v_p(a_2), \ldots , v_p(a_n))$$

Lisäksi aito epäyhtälö vaatii, että on olemassa vähintään kaksi eri indeksiä $i$ ja $j$, joilla $v_p(a_i) = v_p(a_j) = \min(v_p(a_1), \ldots , v_p(a_n))$.

Todistus on analoginen edellä esitetyn kanssa.

Esimerkkitehtävä (Baltian tie, 2007, T20)

Olkoot $a$ ja $b$ positiivisia kokonaislukuja, joille $b < a$, ja luku $a^3 + b^3 + ab$ on jaollinen luvulla $ab(a-b)$. Osoita, että $ab$ on kokonaisluvun kuutio.

Ratkaisu

Kirjoitetaan $a^3 + b^3 + ab = f(a, b)$ ja $ab(a-b) = g(a, b)$.

Valitaan mielivaltainen $p$. Määritellään $v_p(a) = x$ ja $v_p(b) = y$. Haluamme osoittaa, että $3 \mid x + y$. Jos $x = y = 0$, tämä pätee, joten oletetaan $\max(x, y) > 0$. Annettu jaollisuusehto antaa $v_p(f(a, b)) \ge v_p(g(a, b))$. Suunnitelmana on osoittaa $v_p(f(a, b)) < v_p(g(a, b))$, jos $3 \nmid x + y$.

Symmetrian nojalla voimme olettaa, että $x \ge y$.

Nyt, $v_p(a^3) = 3x$, $v_p(b^3) = 3y$ ja $v_p(ab) = x + y$. Lemman 1 soveltamisessa on yksi este: emme tiedä onko $x + y = 3y$ vai ei. Mutta jos $x + y = 3y$, olemme todistaneet $3 \mid x + y$. Enää tulee siis poissulkea tapaus $x + y \neq 3y$.

Tiedämme, että $3x > 3y$. Lemman 1 yleistyksen nojalla

$$v_p(g(a, b)) = \min(x + y, 3y)$$

Toisaalta, $v_p(f(a, b)) = x + 2y$ käyttäen lemmaa 1. Halumme siis enää osoittaa, että $\min(x + y, 3y) < x + 2y$. Tämä on kuitenkin helppoa: $3y < x + 2y$, ja $x + y \ge x + 2y$ vaatisi $y = 0$, jolloin $0 = \min(x + y, 3y) < x + 2y$. Olemme siis valmiit.

Huomautus

Kokemuksieni mukaan vastaavaa menetelmää voi käyttää melko usein, jos on annettuna ehto muotoa $f(a_1, a_2, \ldots , a_n) \mid g(a_1, a_2, \ldots a_n)$, missä $f$ ja $g$ ovat $n$:n muuttujan kokonaislukukertoimisia polynomeja, joilla $f(0, 0, \ldots , 0) = g(0, 0, \ldots , 0) = 0$. Vastaava menettely ei kuitenkaan aina toimi suoraan, esim. jos on annettu ehto $a - b \mid a^2$. En heti keksi esimerkkiä, missä tällainen käsittely ei auttaisi, jos vaadimme lisäksi $\deg(f) \ge \deg(g)$.

Valmennuksen sivuilta löytyy Esa Vesalaisen keräämä ja kääntämä 30 lukuteorian tehtävän kokoelma Yu Hong-Bingin teoksesta Problems of Number Theory in Mathematical Competitions.

Esimerkkitehtävä (yllä olevan monisteen T13)

Olkoot $m$ ja $n$ yhteistekijättömiä positiivisia kokonaislukuja. Osoita, että $m$ jakaa binomikertoimen ${m + n - 1 \choose n}$

Ratkaisu

Tähän tehtävään löytyy elegantti ratkaisu, joka on kuvailtu monisteen vihjeissä. Seuraavaksi esitettävä ratkaisu on naiivimpi, jopa brutaali, mutta on hyvä demonstroimaan notaation kätevyyttä.

Kuten edellä totesimme, $a \mid b$ tarkoittaa, että $v_p(a) \le v_p(b)$ kaikilla $p$. Haluamme siis osoittaa, että

$$v_p(m) \le v_p\Big({n+m-1 \choose n}\Big)$$

kaikilla $p$. Binomikertoimen $v_p$:n laskeminen onnistuu seuraavalla lemmalla:

Lemma 2

$v_p(k!) = \Big\lfloor \frac{k}{p} \Big\rfloor + \Big\lfloor \frac{k}{p^2} \Big\rfloor + \Big \lfloor \frac{k}{p^3} \Big \rfloor + \cdots$

Todistus

Lasketaan välillä $[1, k]$ olevien lukujen määrä, jotka ovat jaollisia $p$:llä. Tämä on $\Big\lfloor \frac{k}{p} \Big\rfloor$. $k!$ voi kuitenkin olla jaollinen vielä suuremmalla $p$:n potenssilla: emme nimittäin ole huomioineet vielä niitä lukuja, jotka ovat jaollisia luvulla $p^2$. Siis tulokseen pitää vielä lisätä $\Big \lfloor \frac{k}{p^2} \Big \rfloor$. Tämän jälkeen pitää vielä laskea luvulla $p^3$ jaollisten lukujen määrä, jne.

Toinen, aavistuksen formaalimpi tapa, on induktio. Lukija voi itse miettiä todistuksen tätä kautta.

Nyt,

$$v_p\Big( {n+m-1 \choose n}\Big) = v_p((n+m-1)!) - v_p(n!) - v_p((m-1)!)$$

Haluamme siis osoittaa, että $v_p(m) + v_p(n!) + v_p((m-1)!) \le v_p((n+m-1)!)$. Voimme nyt muotoilla tämän epäyhtälön lemman 2 avulla. Jos $v_p(m) = 0$, olemme valmiit, sillä

$$\Big \lfloor \frac{n}{p^i} \Big \rfloor + \Big \lfloor \frac{m-1}{p^i} \Big \rfloor \le \Big \lfloor \frac{n + m - 1}{p^i} \Big \rfloor$$

kaikilla eksponenteilla $i$.

Jos $v_p(m) > 0$, tulee meidän löytää (vähintään) $v_p(m)$ kappaletta eksponentteja $i$, joilla yllä olevassa epäyhtälössä ei päde yhtäsuuruus. Jos asiaa ajattelee hetken, huomaa eksponenteiksi käyvän $i = 1, 2, \ldots v_p(m)$. Todistetaan tämä.

Pidetään $1 \le i \le v_p(m)$ vakiona. Kirjoitetaan $k = p^i$, ja jakoyhtälön avulla $n = kt + r$, missä $t \in \mathbb{Z}$ ja $0 \le r < k$. Huomataan, että $r \neq 0$, sillä muuten $p$ jakaisi sekä luvun $n$ että luvun $m$, mikä on ristiriidassa annetun ehdon $\syt(m, n) = 1$ kanssa. Merkitään vielä $m = sk$. Nyt,

$$\Big \lfloor \frac{n + m - 1}{k} \Big \rfloor = t + s$$

Mutta,

$$\Big \lfloor \frac{n}{p} \Big \rfloor + \Big \lfloor \frac{m - 1}{p} \Big \rfloor = t + s - 1$$

Tämä on mitä halusimme! Olemme siis valmiit. Ratkaisu ei ollut nätti, mutta se toimi.

$v_p$-notaatio mahdollistaa seuraavan mukavan lemman näppärän ilmaisun ja soveltamisen.

Lifting The Exponent lemma (LTE)

Olkoon annettu kokonaisluvut $p, x, y, n$, missä $n > 0$. Oletetaan, että $p \mid x - y$, ja $p \nmid xy$. Jos $p > 2$, pätee

$$v_p(x^n - y^n) = v_p(x - y) + v_p(n)$$

Jos $p = 2$, ja $n$ on parillinen:

$$v_2(x^n - y^n) = v_2(x - y) + v_2(x + y) + v_2(n) - 1$$

Jos $p = 2$, ja $n$ on pariton:

$$v_2(x^n - y^n) = v_2(x - y)$$

Huomautus

Jos $n$ on pariton, saamme sijoituksella $z = -y$ vastaavat väitteet yhteenlaskulle.

LTE:n todistus esitetään postauksen lopussa

Esimerkkitehtävä (klassikko, myös T27 em. lukuteoriamonisteesta)

Olkoon $p$ alkuluku. Osoita, että $2^p + 3^p$ ei ole minkään kokonaisluvun $n$:nnes potenssi, missä $n \ge 2$.

Ratkaisu

Yksinkertaiset modulotarkastelut voisivat todistaa, että luku ei voi olla $n$:nnes potenssi jollain vakiolla $n$ (esim. $n = 2$ vastaa neliönjäännöksiä). Kaikkia $n$ ei kuitenkaan saa tällä tavalla, ainakaan helposti. Täytyy siis keksiä jotain muuta.

Totesimme aiemmin, että luku $m$ on $n$:nnes potenssi jos ja vain jos $n \mid v_q(m)$ kaikilla $q$. Jos jokaista $p$ kohden löytäisimme alkuluvun $q$, jolla $v_q(2^p + 3^p) = 1$, todistaisimme väitteen. LTE:n kannalta $q = 5$ olisi hyvä kandidaatti. Jotta voimme käyttää LTE:tä summalle $a^n + b^n$ erotuksen sijasta, tulee eksponentin olla pariton, joten tapaus $p = 2$ tulee tutkita erikseen. Väite pätee tapauksessa $p = 2$, joten tutkitaan nyt tapaus $p > 2$:

$$v_5(2^p + 3^p) = v_5(2^p - (-3)^p) = v_5(2 - (-3)) + v_5(p) = 1 + v_5(p)$$

Jos $p \neq 5$, olemme valmiit. Mutta jos $p = 5$, saamme $2^5 + 3^5 = 275 = 25 \cdot 11$, joten myös tässä tapauksessa väite pätee. Olemme valmiit.

Huomautus

Tehtävän voi toki ratkaista ilman LTE:tä vain tutkimalla modulo $25$. Tämä kuitenkin vaatii enemmän laskemista.

Harjoitustehtäviä

Edellä mainitusta 30 lukuteorian tehtävän kokoelmasta tehtävät 3, 9, 31 sopivat mainiosti postauksen teemaan.

Valmennustehtävät, lokakuu 2014, V2

Olkoot $x$ ja $y$ erisuuria positiivisia kokonaislukuja. Osoita, että

$$\frac{x^2 + 4xy + y^2}{x^3 - y^3}$$

ei ole kokonaisluku.

Baltian tie 2015, T17

Määritä kaikki positiiviset kokonaisluvut $n$, joilla luku $n^{n-1} - 1$ on jaollinen luvulla $2^{2015}$, mutta ei luvulla $2^{2016}$.

IMO 2018, T5

Olkoon $a_1, a_2, \dots$ päättymätön jono positiiviisia kokonaislukuja. Oletetaan, että on olemassa kokonaisluku $N > 1$, jolle jokaista $n \ge N$ kohti luku

$$\frac{a_1}{a_2} + \frac{a_2}{a_3} + \cdots + \frac{a_{n-1}}{a_n} + \frac{a_n}{a_1}$$

on kokonaisluku. Osoita, että on olemassa sellainen positiivinen kokonaisluku M, että $a_m = a_{m+1}$ kaikilla $m \ge M$.

Kirjoittajan ratkaisu lyhyine motivaatioineen löytyy lukuisien muiden ratkaisujen ohella linkistä: IMO 2018 T5 (postaus numero 11).

LTE:n todistus

Keskitytään ensin tapaukseen $p \neq 2$.

Todistuksessa on seuraavat kaksi pääpointtia:

1. Jos $a \equiv b \pmod{p}$, ja $p \nmid nab$, niin $v_p(a^n - b^n) = v_p(a - b)$.

2. Jos $p \nmid a$, niin $v_p((a+b)^p - a^p) = v_p(b) + 1$

Todistetaan nämä väitteet, ja osoitetaan sitten LTE. Lukija voi myös itse yrittää todistamista ennen etenemistä.

Osan 1 todistus

$$\frac{a^n - b^n}{a-b} = a^{n-1} + a^{n-2}b + \ldots + b^{n-1} \equiv na^{n-1} \pmod{p}$$

Oletusten nojalla tämä on jaoton $p$:llä. Tämä todistaa väitteen.

Osan 2 todistus

Huomataan ensinnäkin, että jos $v_p(b) = 0$, niin väite pätee, sillä $x^p \equiv x \pmod{p}$ kaikilla $x$ Fermat’n pienen lauseen nojalla.

Oletetaan nyt, että $v_p(b) > 0$. Binomilauseen nojalla

$$(a+b)^p - a^p = pa^{p-1}b + \frac{p(p-1)}{2}a^{p-2}b^2 + \ldots + b^p$$

Tutkitaan jokaisen summattavan termin $v_p$:tä. Jokainen termi on muotoa

$${p \choose k}a^{p-k}b^{k}$$

missä $k = 1, 2, \ldots p$. Tämän termin $v_p$ on $1 + kv_p(b)$, paitsi tapauksessa $k = p$, jolloin se on vain $pv_p(b)$. Sillä $v_p(b) > 0$ ja $p > 2$, pienin näistä arvoista on $1 + v_p(b)$. Siis lemman 1 yleistystä soveltamalla saamme väitteen.

LTE:n todistus on nyt suoraviivainen. Tehdään samat oletukset kuin LTE:ssä, ja kirjoitetaan $n = p^km$, missä $p \nmid m$. Osan 1 avulla saamme

$$v_p(a^n - b^n) = v_p((a^{p^k})^m - (b^{p^k})^m) = v_p(a^{p^k} - b^{p^k})$$

Nyt vain käytetään toistuvasti osaa 2. Tämä ei ole järin kiinnostavaa, mutta kirjoitetaan kokonaisuuden vuoksi. Ehkä aavistuksen formaalimmin (ja helpommin) tämä voidaan kirjoittaa induktiolla: todistetaan väite nyt induktiolla $k$:n suhteen. Oletetaan siis, että

$$v_p(a^{p^{k-1}} - b^{p^{k-1}}) = v_p(a - b) + k-1$$

Nyt, osaa 2 ja induktio-oletusta käyttämällä saamme

$$v_p(a^{p^k} - b^{p^k}) = v_p((a^{p^{k-1}})^p - (b^{p^{k-1}})^p) = v_p(a^{p^{k-1}} - b^{p^{k-1}}) + 1$$ $$= v_p(a-b) + k - 1 + 1 = v_p(a-b) + k$$

Huomataan, että induktion pohjatapaus tuli todistettua osassa 2. Olemme valmiit.

Tapauksen $p = 2$ todistus on miltei identtinen: osan 1 todistus ei missään kohtaa käyttänyt ehtoa $p > 2$. Käytännössä meidän siis tulee tehdä enää vain sama asia kuin edellä tehtiin osan 2 jälkeen. Emme kuitenkaan voi käyttää väitettä 2, mutta tämä ei haittaa, sillä emme oikeastaan tarvitsekaan sitä.

Tapauksessa $n$ on pariton olemme valmiit: osan 1 nojalla $v_2(a^n - b^n) = v_2(a-b)$. Oletetaan siis, että $n$ on parillinen.

Osoitetaan nyt induktiolla, että

$$v_2(a^{2^k} - b^{2^k}) = v_2(a-b) + v_2(a+b) + k - 1$$

kaikilla $k \ge 1$. Tämä todistaa väitteen LTE:lle tapauksessa $p = 2$, $n$ parillinen.

$k = 1$ on selvä. Oletetaan, että väite pätee arvolla $k-1$, ja osoitetaan, että se pätee arvolla $k \ge 2$. Käytämme kahden neliön erotuksen tulomuotoesitystä.

$$v_2(a^{2^k} - b^{2^k}) = v_2(a^{2^{k-1}} - b^{2^{k-1}}) + v_2(a^{2^{k-1}} + b^{2^{k-1}})$$

Sillä $k \ge 2$, $2^{k-1}$ on parillinen. Siis oikeanpuolinen luku on kahden neliön summa, joten se ei voi olla jaollinen neljällä (ovathan $a$ ja $b$ parittomia). Täten se on jaollinen kahdella, muttei neljällä. Nyt vain käytämme induktio-oletusta

$$= v_2(a-b) + v_2(a+b) + k-2 + 1 = v_2(a-b) + v_2(a+b) + k-1$$

Todistus LTE:lle on valmis. Kuvittele, kuinka kankea todistus olisi ollut ilman $v_p$-notaatiota (tai postauksen tulokset ylipäätään)!