NWO teamselectie 2008-4

Probleem 4 van de teamselectie van de Nederlandse Wiskundeolympiade 2008 luidt:

Zij \(n\) een geheel getal zo dat \(\sqrt{1+12n^2}\) een geheel getal is.
Bewijs dat \(2+2\sqrt{1+12n^2}\) het kwadraat van een geheel getal is.

Ik had deze destijds niet opgelost. Voor \(n=0\) is de wortel het gehele getal \(1\), en \(4\) is inderdaad een kwadraat, en voor \(n=2\) is de wortel \(7\) en \(16\) is weer een kwadraat. Meer gevallen zijn met de computer te controleren, hier in J:

((=>.)@:{:"1#])(,.[:(,.[:+:>:)[:%:[:>:[:12&**:)i.1e5
    0      1      4
    2      7     16
   28     97    196
  390   1351   2704
 5432  18817  37636
75658 262087 524176

Bewijs

Met wat algebra is het probleem te herformuleren als volgt:

Zij \((n,a)\in\mathbb{Z}_{\geq 0}^2\) een oplossing van \(12n^2=(a+1)(a-1)\).
Bewijs dat \(2(a+1)\) een kwadraat is.

Er moet dus bewezen worden dat elk priemgetal een even aantal keer voorkomt als factor van \(2(a+1)\). Drie gevallen:

• \(p=2:\) De factor \(p\) komt een even aantal keer voor in \(12n^2\), dus \((a+1)\) en \((a-1)\) zijn \(0\pmod 4\) en \(2\pmod 4\), of andersom. De een bevat dus één factor \(2\), en de ander de rest, een oneven aantal. Dus \(2(a+1)\) heeft juist een even aantal factoren \(2\).
• \(p=3:\) Als \((a+1)\) deelbaar door \(3\) is, dan is \(a=3h-1\) voor zekere \(h\) dus \(h(3h-2)=4n^2\), en \(h\) is dus even, \(h=2k\). Dan volgt \(k(3k-1)=n^2\). Omdat \(\text{ggd}(k,3k-1)=1\) moeten zowel \(k\) als \((3k-1)\) kwadraten zijn. Maar dat kan niet, want kwadraten zijn nooit \(-1\pmod 3\). Uit deze tegenspraak volgt dat \((a+1)\) geen factor \(3\) bevat, een even aantal dus.
• \(p>3:\) De factor \(p\) komt een even aantal keer voor in \(12n^2\) en kan niet in zowel \((a+1)\) als \((a-1)\) zitten. Dus zitten ze allemaal wel of allemaal niet in \((a+1)\).

Hiermee is de bewering bewezen. \(\square\)

Vergelijking van Pell

De vergelijking \(a^2-dn^2=1\) heet de vergelijking van Pell, hier met \(d=12\). De linkerkant is de zogenaamde norm \(N\) van het element \(a+n\sqrt d\) uit de ring \(\mathbb Z[\sqrt d]\). Er geldt \(N(xy)=N(x)N(y)\). Alle niet-triviale oplossingen van de vergelijking van Pell komen voort uit machten van \(a_1+n_1\sqrt{d}\) waar \((a_1,n_1)\) de zogenaamde fundamentele oplossing is. Dit volgt uit de eenheidsstelling van Dirichlet uit de algebraïsche getaltheorie. Er geldt dan \[ \begin{pmatrix} a_k \\ n_k \\ \end{pmatrix} = \begin{pmatrix} a_1 & dn_1 \\ n_1 & a_1 \end{pmatrix}^k \begin{pmatrix} 1 \\ 0 \end{pmatrix} \]

De grootste eigenwaarde van de matrix is \(a_1+\sqrt{a_1^2-1}\). In dit geval is de fundamentele oplossing \((7,2)\) dus \[ \begin{pmatrix} a_k \\ n_k \end{pmatrix} = \begin{pmatrix} 7 & 24 \\ 2 & 7 \end{pmatrix}^k \begin{pmatrix} 1 \\ 0 \end{pmatrix} \]

De grootste eigenwaarde is \(7+\sqrt{48}\approx 13.9\), wat overeenkomt met het quotiënt van opvolgende waarden van \(a\) (of \(n\)), bijvoorbeeld \(262087/18817\). Met deze recursie is ook in te zien dat \(a_k\equiv 1\pmod 3\) en dus dat \(2+2a_k\) nooit deelbaar is door \(3\).

Verwijzingen

• Andere oude NWO-opgaven
• Solving the Pell Equation
• Ireland & Rosen, A Classical Introduction to Modern Number Theory