Zij $p(n)$ het aantal kwadraten $\mod{2^n}$. We bewijzen een aantal lemma's, die ons uiteindelijk zullen brengen tot het eindresultaat.
Deze lemma's gelden voor $n\ge 3$.
Lemma 1. Het volstaat om de kwadraten van de getallen $0,1,2,\dots,2^{n-2}$ te beschouwen.
Immers, we hebben dat $(2^n-x)^2\equiv x^2\mod{2^n}$ en ook dat $(2^{n-1}-x)^2\equiv x^2\mod{2^n}$. Ieder kwadraat in $\{0,1,\dots,2^n-1\}$ kan dus gereduceerd worden tot een kwadraat van $\{0,1,\dots,2^{n-2}-1\}$.
Lemma 2. Als $x$ en $y$ verschillende oneven getallen zijn en $1\le x,y \le 2^{n-2}-1$, dan is $x^2\not\equiv y^2\mod{2^n}$.
Deze vergelijking valt namelijk om te vormen tot $2^n\mid (x-y)(x+y)$ en aangezien $\text{ggd}(x-y,x+y)$ deelbaar is door $2$ maar niet door $4$ (want hij deelt $2x$ en $2y$), zal één van de factoren $x-y$ of $x+y$ deelbaar zijn door $2$ en de andere noodzakelijkerwijs deelbaar door $2^{n-1}$. Maar $x+y\le 2^{n-1}-2$ zodat $x+y$ nooit deelbaar is door $2^{n-1}$. En als $2^{n-1}\mid x-y$ dan is ook duidelijk dat $x=y$ moet gelden. Hiermee is dus bewezen dat $1^2,3^2,\dots, (2^{n-2}-1)^2$ allemaal verschillend zijn $\mod{2^n}$ en dat dit ook zeker wegens lemma 1 de enige oneven volkomen kwadraten zijn.
Besluit 1. Er zijn $2^{n-3}$ oneven volkomen kwadraten $\mod{2^n}$
Lemma 3. Er zijn $p(n-2)$ even volkomen kwadraten $\mod{2^n}$.
Immers, als $x=2m$ en $y=2n$, dan is $x^2\equiv y^2 \mod{2^n}$ als en slechts als $m^2\equiv n^2 \mod{2^{n-2}}$. Daaruit volgt het resultaat onmiddelijk.
We verkrijgen dus de recursie $p(n)=2^{n-3}+p(n-2)$ en we weten al dat $p(1)=2$ en $p(2)=2$. Het is nu niet moeilijk om met inductie te bewijzen dat
$p(n)=\frac{5+2^{n-1}}{3}$ als $n$ oneven
$p(n)=\frac{1+2^{n-1}}{3}$ als $n$ even
Mensen die kicken om alles in één formule te steken kunnen dan kijken naar het volgende besluit:
Antwoord. Er zijn $\frac{2^{n-1}+3+2.(-1)^{n-1}}{3}$ kwadraten $\mod{2^n}$
Oplossing
Zij $p(n)$ het aantal kwadraten $\mod{2^n}$. We bewijzen een aantal lemma's, die ons uiteindelijk zullen brengen tot het eindresultaat.
Deze lemma's gelden voor $n\ge 3$.
Lemma 1. Het volstaat om de kwadraten van de getallen $0,1,2,\dots,2^{n-2}$ te beschouwen.
Immers, we hebben dat $(2^n-x)^2\equiv x^2\mod{2^n}$ en ook dat $(2^{n-1}-x)^2\equiv x^2\mod{2^n}$. Ieder kwadraat in $\{0,1,\dots,2^n-1\}$ kan dus gereduceerd worden tot een kwadraat van $\{0,1,\dots,2^{n-2}-1\}$.
Lemma 2. Als $x$ en $y$ verschillende oneven getallen zijn en $1\le x,y \le 2^{n-2}-1$, dan is $x^2\not\equiv y^2\mod{2^n}$.
Deze vergelijking valt namelijk om te vormen tot $2^n\mid (x-y)(x+y)$ en aangezien $\text{ggd}(x-y,x+y)$ deelbaar is door $2$ maar niet door $4$ (want hij deelt $2x$ en $2y$), zal één van de factoren $x-y$ of $x+y$ deelbaar zijn door $2$ en de andere noodzakelijkerwijs deelbaar door $2^{n-1}$. Maar $x+y\le 2^{n-1}-2$ zodat $x+y$ nooit deelbaar is door $2^{n-1}$. En als $2^{n-1}\mid x-y$ dan is ook duidelijk dat $x=y$ moet gelden. Hiermee is dus bewezen dat $1^2,3^2,\dots, (2^{n-2}-1)^2$ allemaal verschillend zijn $\mod{2^n}$ en dat dit ook zeker wegens lemma 1 de enige oneven volkomen kwadraten zijn.
Besluit 1. Er zijn $2^{n-3}$ oneven volkomen kwadraten $\mod{2^n}$
Lemma 3. Er zijn $p(n-2)$ even volkomen kwadraten $\mod{2^n}$.
Immers, als $x=2m$ en $y=2n$, dan is $x^2\equiv y^2 \mod{2^n}$ als en slechts als $m^2\equiv n^2 \mod{2^{n-2}}$. Daaruit volgt het resultaat onmiddelijk.
We verkrijgen dus de recursie $p(n)=2^{n-3}+p(n-2)$ en we weten al dat $p(1)=2$ en $p(2)=2$. Het is nu niet moeilijk om met inductie te bewijzen dat
$p(n)=\frac{5+2^{n-1}}{3}$ als $n$ oneven
$p(n)=\frac{1+2^{n-1}}{3}$ als $n$ even
Mensen die kicken om alles in één formule te steken kunnen dan kijken naar het volgende besluit:
Antwoord. Er zijn $\frac{2^{n-1}+3+2.(-1)^{n-1}}{3}$ kwadraten $\mod{2^n}$