Alternerende veelvouden

Het antwoord is alle positieve gehele getallen $n$ waarvoor $20 \not \mid n$. We bewijzen eerst dat indien $20 \mid n$, $n$ geen alternerend veelvoud heeft: inderdaad, duidelijk zal $n$ eindigen op nul en moet het voorlaatste cijfer even zijn. Nu gaan we in kleine gevallen verder, waarbij we eerst volgend lemma zullen bewijzen:

Lemma: Indien $ggd(n,10)=1$, bestaat er voor iedere natuurlijke $k$ een veelvoud van $n$ dat de vorm $1000...01000...01000......01$ aanneemt (een juist veelvoud), met $k$ nullen tussen twee opeenvolgende enen (en zoveel enen als je wilt).

Bewijs: Beschouw de verzameling $A=\{ \sum_{i=0}^x 10^{kx} | 0 \le x \le n , n \in \mathbb{Z} \}$. Deze bevat $n+1$ elementen van de gewenste vorm. Nu geldt wegens het DHP dat er twee elementen $a,b$ in $A$ zijn met dezelfde rest modulo $n$. Dus $n \mid |a-b|$. Maar $|a-b|$ is, op een paar nullen achteraan na, ook van de gewenste vorm. Aangezien $ggd(n,10)=1$ mogen we die laatste nullen wegnemen en komen we op die manier aan een veelvoud van $n$ van de gewenste vorm.

Een eenvoudig gevolg van het lemma is dat alle $n$ met $ggd(n,10)=1$ voldoen: immers, we kunnen $k=1$ nemen in het lemma. (1)

(2) Stel nu dat $n=2^r$. We tonen per inductie aan dat zo'n alternerend veelvoud $a_r a_{r-1}...a_1$ (waar we dit niet als vermenigvuldiging maar als decimale schrijfwijze moeten opvatten) bestaat.

Inductiebegin: Indien $r=1$ nemen we $a_1=2$.

Inductiehypothese: Het getal $a_r a_{r-1} ... a_1$ is alternerend (met $a_1$ even) en deelbaar door $2^r$ maar niet door $2^{r+1}$ indien $r$ oneven is en anders wel deelbaar door $2^{r+1}.$

Inductiestap: Zij $A=a_r a_{r-1}...a_1$.

Stel eerst $r$ oneven. Merk op dat altijd geldt dat $(2l+1) 10^r+A \equiv 2^{r+1} 5^r l+2^{r}+2^{r}\equiv 0 \pmod {2^{r+1}}$ wegens de inductiehypothese. Nu willen we ook dat $(2l+1) 10^r +A \equiv 0 \pmod {2^{r+2}}$. Stel dat $10^r +A \equiv 0 \pmod {2^{r+2}}$, dan zijn we klaar. Anders zal $10^r +A \equiv 2^{r+1} \pmod {2^{r+2}}$ zodat $l=1$ wel zal voldoen. Nu nemen we $a_{r+1}=2l+1$ en daarmee is dit geval afgewerkt.

Het geval $r$ even verloopt volledig analoog. Daarmee is dit deel van het bewijs afgerond.

Opmerking: We staan hier en in het volgende deel toe dat het eerste cijfer nul is; dit heeft natuurlijk geen effect op het bewijs zelf.

(3) Stel $n=5^r$. We tonen per inductie aan dat er een alternerend veelvoud $a_r a_{r-1} ... a_1$ (in decimale schrijfwijze) bestaat met het laatste cijfer 5 zodanig dat $5^r$ er een deler van is.

Inductiebegin: Indien $r=1$ nemen we $a_1=5$.

Inductiehypothese: Het getal $a_r a_{r-1}... a_1$ voldoet voor $r$.

Inductiestap: Laat $A=a_r a_{r-1}... a_1$. Merk op dat er een $b$ bestaat met $0 \le b \le 4$ zodanig dat $A \equiv b 5^r \pmod{5^{r+1}}$. Nu bestaat er ook een $c$ met $ 0< c \le 4$ zodanig dat $10^r \equiv c 5^{r} \pmod {5^{r+1}}$. Merk nu op dat $a_{r+1}$ zal voldoen als en slechts als $a_{r+1} c+b \equiv 0 \pmod 5$. Deze vergelijking heeft altijd een oplossing omdat $5 \not \mid c$, zodanig dat er twee mogelijkheden voor $a_{r+1}$ zijn met $0 \le a_{r+1} \le 9$ met verschil $5$; de ene is dus even en de andere oneven. We moeten maar met de juiste aanvullen. Daarmee is ook dit deel van het bewijs afgerond.

(4) Stel nu dat $n=5^r y$ of $n=2^r y$ met $ggd(y,10)=1$. Neem resp. een veelvoud $A$ van $5^r$ en $2^r$ dat begint met een oneven cijfer. (kan wegens (2) en (3)) Voor $5^r$ nemen we vervolgens een juist veelvoud $B$ van $y$ met aantal nullen gelijk aan het aantal cijfers van $A$; het is duidelijk dat $AB$ dan voldoet. In het geval van $2^r$ is het analoog, maar het aantal nullen van het juiste veelvoud is één minder dan het aantal cijfers van $A$.

(5) Stel ten slotte dat $n=10*5^r*y$ met $ggd(y,10)=1$. Omdat het alternerend veelvoud van $5^r y$ uit het vorige deel eindigde op een oneven cijfer, mogen we gewoon een nul toevoegen en blijft het alternerend.

Uit de stappen (1) tot en met (5) volgt nu dat indien $20 \not \mid n$ er zeker een alternerend veelvoud is. Q.E.D.