deelbaarheid

[drc.]

Ik heb op dit forum al eens de "truc" gezien om te bepalen of een getal deelbaar is door 9;
tel de cijfers bij elkaar op en als het resultaat deelbaar is door 9, dan is het oorspronkelijke getal dat ook.

Voorbeeld: 567 is deelbaar door 9, ook genoteerd als 9|567 omdat 9|5+6+7=18.

Nu kwam ik laatst ook een methode tegen om te bepalen of een getal deelbaar is door 7.
Trek het laatste getal (de eenheid) van de overgebleven cijfers.

Bijvoorbeeld: 406. Het laatste cijfer, de eenheid, is 6. Trek dat 2 keer af van de rest; 40.
40-2*6=28. 7|28 dus 7|406

Stel

\(a_2=4,\; a_1=0,\;a_0=6\)

, dan geldt

\(406=a_2 \cdot 10^2 + a_1 \cdot 10^1 + a_0 \cdot 10^0\)

Dat kan ook worden geformuleerd als

\(\sum_{k=0}^{2} a_k \cdot 10^k\)

Op die manier kunnen de methode om deelbaarheid door 7 te testen ook zo formuleren:

\(7|\sum_{k=0}^{n} a_k \cdot 10^k\)

als

\(7|\left(\sum_{k=1}^{n} a_k \cdot 10^{k-1}\right) - 2 \cdot a_0\)

Of ook

\(7|\frac{\left(\sum_{k=0}^{n} a_k \cdot 10^{k}\right)-a_0}{10} - 2 \cdot a_0\)

Ik vroeg me af of er een algemene methode is, ook om te kijken of een getal bijv. deelbaar is door 17. en ik kwam tot het volgende:

Stel dat je wilt aantonen dat een getal deelbaar is door

\(m\in \mathbb{N}\)

\(0 \leq a_k < 10\)

\(m|\sum_{k=0}^{n} a_k \cdot 10^k\)

als

\(m|\sum_{k=1}^{n} a_k \cdot 10^{k-1}-(9-m) \cdot a_0\)

Voorbeeld:
Is 1586 deelbaar door 13?
13|158-(9-13)*6=182 dus 13|1586

Ik bekijk dit zelf nog wat verder; ook voor andere getalstelsels.

Voor nu denk ik:
Als

\(m|\sum_{k=1}^{n} a_k \cdot g^{k-1}-(g-m-1) \cdot a_0\)

dan

\(m|\sum_{k=0}^{n} a_k \cdot g^k\)

met

\(0 \leq a_k < g\)

Voor een g-tallig getallenstelsel.

[drc.]

Ok, ik heb alleen geen tegenvoorbeelden gevonden voor m=7 en m=13 in het 10-tallig getallenstelsel.

Voor m = 9 en m = 11 vind ik nu:

\(0 \leq a_k < 10\)

\(m|\sum_{k=0}^{n} a_k \cdot 10^k\)

als

\(m|\sum_{k=1}^{n} a_k \cdot 10^{k-1}+(10-m) \cdot a_0\)

Dat sluit meer aan bij de eerder genoemde methode voor deelbaarheid door 9 bij een methode voor deelbaarheid door 11.

Een programma voor VBA Excel:
Met commentaar (commentaar achter de apostrof (')):

Code: Selecteer alles

Sub deelbaarheid()
' declaratie
Dim k As Long, d As Long, t As Boolean, b As String
' initialisatie
' b wordt een boodschap in een messagebox die vertelt of voor de gekozen waarden voor d uit de
' vermoedelijke formule deelbaarheid volgt. Nu is die boodschap leeg.
b = ""
' Test de formule voor deelbaarheid door 13. Met bijv. een extra for-loop kan deelbaarheid voor
' verschil-lende waarden testen.
d = 13
' waar of onwaar. Als er een tegenvoorbeeld is gevonden, wordt t onwaar (False) anders blijft
' het waar.
t = True
    ' voor alle gehele getallen tussen 1 en 10000 (bijv.)    
        For k = 1 To 10000
        ' Plaats d * k, hier 13 * k
        Cells(k, 1) = d * k
        ' Plaats cijfers van de cel in dezelfde rij in kolom 1 behalve het eenheidcijfer in cel 2.
        ' Trek daar (9-d) * "de eenheid" vanaf. Je kan vereenvoudigen voor d=13, maar dat deed ik
        ' niet voor eventueel bijv. de extra for-loop.
        Cells(k, 2) = "=" & Mid(CStr(d * k), 1, Len(CStr(d * k)) - 1) _
        & "-(9-" & d & ")*(" & Mid(CStr(d * k), Len(CStr(d * k)), 1) & ")"
        ' als de getallen in kolom 2 niet deelbaar zijn door d, hier 13, dan is t "False". Dan is er
        ' minstens 1 tegenvoorbeeld in de geteste waarden voor k.
        If Cells(k, 2) Mod d <> 0 Then
            t = False
        End If
    Next k
        ' Geef een Msgbox met de waarden voor t (True of False) met de bijbehorende waarden voor d;
        ' waarvoor is getest.
        b = b & d & ": " & t & " "
MsgBox b
End Sub

Zonder het commentaar.

Code: Selecteer alles

Sub deelbaarheid()
Dim k As Long, d As Long, t As Boolean, b As String
b = ""
d = 13
t = True
    For k = 1 To 10000
        Cells(k, 1) = d * k
        Cells(k, 2) = "=" & Mid(CStr(d * k), 1, Len(CStr(d * k)) - 1) _
        & "-(9-" & d & ")*(" & Mid(CStr(d * k), Len(CStr(d * k)), 1) & ")"
        If Cells(k, 2) Mod d <> 0 Then
            t = False
        End If
    Next k
        b = b & d & ": " & t & " "
MsgBox b
End Sub

De werking van het programma is onafhankelijk van het commentaar als het commentaar achter een apostrof staat.

Het programma toont niet het omgekeerde;
13 \not| 38
13 \not| 3 - (9-13)*8 dit laatste wordt niet gecontroleerd. Het kan zijn dat
13 | 3 - (9-13)*8. Controle moet nu uitwijzen of dat zo is.

[Sjoerd Job]

Even een volledige andere aanpak:

Om te testen of

\(2^k5^l m | n\)

, volstaat het natuurlijk te testen dat

\(2^k | n\)

,

\(5^l | n\)

en

\(m | n\)

.

De testen voor 2 en 5 kan je doen door naar de laatste zoveel cijfers te kijken.
De andere testen zijn recursief van aard (maar in VB is er natuurlijk wel een makkelijkere test, maar ja).

Als

\(\gcd(m,10) = 1\)

, is er een getal

\(k\)

zodat

\(10k \equiv 1 \pmod{m}\)

. (Bij

\(m = 7\)

krijg je

\(k = 5\)

.).
Dan geldt natuurlijk de volgende equivalentie: schrijf

\(n = 10b + a\)

. Dan

\(10b + a \equiv 10b + 10k a \equiv 10(b+ka) \pmod{m}\)

. Je krijgt dus

\(m | n \Leftrightarrow m | b+ka\)

als test.

De waarden voor

\(k\)

in termen van

\(m\)

zijn niet al te moeilijk te vinden, denk ik. Desnoods via het extended gcd algoritme!

[drc.]

Mooie methode!
Ik doorloop hem een keer met een voorbeeld.
19|437?
Vind k zodat

\(10k \equiv 1 \bmod m=19\)

k = 2;

\(10*2 \equiv 1 \bmod 19\)

437 = 43*10+7 dus b = 43 en a = 7

\(19|437 \leftrightarrow 19|b\, +\, ak\, =\, 43\,+\,7 \cdot 2\,=\,57\)

. De laatste is waar dus 19|437

Ik heb nog verder gekeken naar mijn methode.
voor m = 17 en m=3 krijg ik:

\(0 \leq a_k < 10\)

\(m|\sum_{k=0}^{n} a_k \cdot 10^k\)

als

\(m|\sum_{k=1}^{n} a_k \cdot 10^{k-1} - 5 * a_0\)

Voorbeeld: 17|4913 als 17|491-5*3=476. 17|47-5*6=17 dus 17|4913.

Voor m = 17 vond ik eerst:

\(m|\sum_{k=1}^{n} a_k \cdot 10^{k-1} + 12 * a_0\)

maar dat klopt niet voor m=3.

Tot nu waren de "paren" m telkens opgeteld 20. (9+11), (7+13), (3+17).

Of ook, voor m = 3 en m = 17

\(0 \leq a_k < 10\)

\(m|\sum_{k=0}^{n} a_k \cdot 10^k\)

als

\(m|\left( \sum_{k=1}^{n} a_k \cdot 10^{k-1}\right) - (5-m) * a_0\)

Voorbeeld: 17|289 als 17|28-(5-17)*9=136


(Latex-weergave werkt nu niet optimaal bij mij).

[op=op]

Trucje om te bepalen of een getal deelbaar is door 999999000001.

Neem b.v. het getal X = 1534293465706534295.

Zet achter dit getal X 6 nullen en tel de uitkomst op bij X.
Resultaat: 1534295000000000001534295.
Je ziet twee gelijke getallen gescheiden door nullen.
Dus X is deelbaar door 999999000001.

Ander voorbeeld:
Neem X = 21355546478748521272834295.
Zet er 6 nullen achter en tel er X bij op.
Resultaat 21355567834295000021355567834295.
Het getal is dus deelbaar door 999999000001.

[CCM.Mank]

Klopt niet.
Bijvoorbeeld met 11
11*57 = 627
62 + 2*7 = 76
duidelijk geen 11-voud.