diophantische vergelijking

Opgave - BrMO 2 2006 vraag 2

Zij $x,y$ twee natuurlijke getallen zonder priemfactoren groter dan 5. Vind alle $x,y$ die voldoen aan
$$x^2-y^2=2^k$$
voor een zeker natuurlijk getal $k$.

Oplossing

Het is duidelijk dat $x > y$. Ontbinden geeft $(x-y)(x+y)=2^k.$

Stel $v_2(x)=a,v_2(y)=b.$
Als $a \not = b$ geldt dat $x^2+y^2>4^{min(a,b)}$ maar $v_2(x^2+y^2)=2 min(a,b).$

( of bewijs met oneindige afdaling: als beide even zijn, dan is de opl $(\frac{a}{2},\frac{b}{2})$ ook een oplossing, herhaal dit tot $1$ even en $1$ oneven is om een contradictie te hebben).

( Of bruteforce:
schrijf $x=2^n*a$ en $y=2^m*b$ met $a$ en $b$ getallen die uit priemfactoren 3 en 5 bestaan, of gelijk zijn aan 1. Stel dat $n \neq m$ dan is bijvoorveeld n>m, uitschrijven geeft: $2^m*(2^{n-m}a-b)*(2^{n-m}a+b)$ Maar dan zijn de tweede en de derde factor oneven, contradictie. Dus $m=n$ )

Zo komen we met de notatie van de bruteforce tot: $(a-b)(a+b)=2^{k-2n}.$
We hebben dus dat
$a-b=2^m,a+b=2^n$ voor zekere $m,n$ met $2a=2^m(2^{n-m}+1)$ (optellen beide vgl'en).
Omdat $a,b$ enkel de priemfactoren $3,5$ bevatten en $ggd(3,a+b)=ggd(5,a+b)=1$ geldt dat $a=3^s,b=5^t$ of omgekeerd.
Dit geeft $3^s=2^{m-1}(2^{n-m}+1)$ zodat $m=1$ en $n=2,4$ met Zsigmondy om het makkelijk te maken of $5^t=2^{m-1}(2^{n-m}+1)$ met $m=1,n=3$ opnieuw eig. triviaal te controleren.

We besluiten dat $a,b= (3,1),(5,3)$ want $a=3^2$ geeft geen oplossing.

Dit betekent dat $(x,y) \in \{ (3*2^k,2^k),(5*2^k,3*2^k)| k \in \mathbb{N}\}.$