Home › Archief › Nationale en Regionale Olympiades › Nederland › NWO › 2007 › Deelbaar door 13

Deelbaar door 13

Tags:

Opgave - NWO 2007 vraag 3

Bestaat er een getal van de vorm $444\cdots4443$ dat deelbaar is door $13$?

Oplossing

Ingediend door mathgirl

Aangezien $44\ldots443=300\ldots00 + 11\ldots11\cdot 13$ zou dat impliceren dat en $13|300\ldots00$, maar dat kan niet aangezien $300\ldots00=3.2^n.5^n$. $\Box$

:)

Ingediend door C|Debry

Definieer $A_n= \underbrace{444\ldots 4}_{n}3$ en $B_n= \underbrace{111\ldots 1}_{n}$. Dan is $A_n = 3+40B_n\equiv B_n-10\ (\text{mod } 13)$, zodat $A_{n+1}-10A_n\equiv B_{n+1}-10B_n+90\equiv 91\equiv 0\ (\textrm{mod }13)$, i.e. $A_{n+1}\equiv 10A_n\ (\text{mod }13)$. Aangezien $\text{ggd}(10,13) = 1$, zal dus$$13 | A_{n}\ \Leftrightarrow\ 13 | A_{n-1}\ \Leftrightarrow\ \ldots\ \Leftrightarrow\ 13 | A_1 = 43,$$waaruit volgt dat $13$ nooit $A_n$ deelt.

Ingediend door MD

We gaan eens met inductie bewijzen dat $44...43$ ($n$ cijfers $4$) nooit deelbaar is door $13$.
Inductiebasis: voor $n=1$ geldt: $43$ is niet deelbaar door $13$. Klopt dus!
Inductiestap: stel nu dat we het bewezen hebben voor $n=k>=1$. Het voldoet dan om aan te tonen dat dit ook zo is voor $n=k+1$.
$44...43$ ($k+1$ cijfers $4$) = $10*44...43$ ($k$ cijfers 4) $+ 13$. Aangezien $13$ deelbaar is door $13$ (logisch) is $44...43$ ($k+1$ cijfers $4$) enkel en alleen deelbaar door $13$ als $10*44...43$ ($k$ cijfers $4$) dat ook is. Maar volgens onze inductiestap is $44...43$ ($k$ cijfers 4) niet deelbaar door $13$ en tenslotte $10$ ook niet. Bijgevolg is $44...43$ ($k+1$ cijfers $4$) niet deelbaar door $13$. Conclusie: er bestaat geen getal van de vorm $44...43$ die deelbaar is door $13$. QED