Warum sind 999 & 111111 etwas Besonderes bei Teilbarkeitstests mit Dezimalziffernsummen? (Auswerfen von Neunen und Elfen)

Nicht ganz richtig, da$9\times 0 = 0$und die Ziffern addieren sich nicht zu$9$; aber ansonsten richtig.

Der Grund, warum es funktioniert, ist, dass wir Zahlen in Basis schreiben$10$, und wenn Sie teilen$10$von$9$, der Rest ist$1$. Nehmen Sie eine Nummer, sagen Sie,$184631$(Ich habe es gerade erfunden). Denken Sie daran, was das wirklich bedeutet:

Aber da jedes Vielfache von$9$ ist ein Vielfaches von$9$, wirst du immer bekommen$9$.

Beachten Sie, dass Sie ein ähnliches Phänomen mit haben$3$(ein Teiler von$9$), da die Ziffern eines Vielfachen von addiert werden$3$ergibt immer eines der einstelligen Vielfachen von$3$:$3$,$6$, oder$9$.

Wenn wir in Basis geschrieben haben$8$, statt Basis$10$, Dann$7$hätte die Eigenschaft: wenn Sie eine Zahl in Basis schreiben$8$und fügen Sie die Ziffern (in Basis 8) hinzu, bis Sie auf eine einzelne Ziffer dazwischen kommen$1$Und$7$, dann die Vielfachen von$7$wird immer nachgebend enden$7$, aus genau demselben Grund. Und wenn wir in Basis geschrieben haben$16$, Dann$15$(oder besser gesagt F) hätte die Eigenschaft. Im Allgemeinen, wenn Sie in Basis schreiben$b$, Dann$b-1$hat das Eigentum.

Dies ist ein Spezialfall des Streichens von Neunen , was wiederum ein Spezialfall der modularen Arithmetik ist . Es ist das, was hinter vielen Teilbarkeitstests steckt (z$2$,$3$,$5$,$9$, Und$11$).

Koda. Das erinnert mich an eine Anekdote, die mir ein Professor erzählte: Einmal kam ein Student zu ihm und erzählte ihm, er habe einen sehr einfachen Weg gefunden, die Teilbarkeit einer beliebigen Zahl zu testen$N$nach beliebiger Zahl$b$: schreiben$N$in der Basis$b$, und sehen Sie, ob die letzte Ziffer ist$0$. Ich denke, genauso könnte man schreiben$N$in der Basis$b+1$, und fügen Sie die Ziffern hinzu, um zu sehen, ob Sie erhalten$b$Am Ende.

Es handelt sich um einen Sonderfall des Streichens von Neunen, was bei Betrachtung über modulare Arithmetik offensichtlich ist:

$\rm\quad mod\,\ 9\!:\, \ \color{#c00}{10\equiv 1}\ \Rightarrow\ P(\color{#c00}{10})\equiv P(\color{#c00}1)\ \,$für alle$\rm\color{#0a0}{polynomials}$ $\rm\,P(x)\,$mit ganzzahligen Koeffizienten

durch die$\rm\color{#0a0}{Polynomial}$Kongruenzregel .

Aber Radix-Notation hat$\rm\color{#0a0}{polynomial}$formen, z$\rm\ N = 567 = P(10)\,$für$\rm\, P(x) = 5\, x^2 + 6\,x + 7.\,$Somit impliziert das obigeMod$\,9\!:\ \rm N = P(10)\equiv P(1) =$die Summe$\rm\,S_N$der Dezimalstellen von$\rm\,N,\,$daher$\rm \bmod 9\!:\,\ 567 \equiv 5\!+\!6\!+\!7\equiv 18\equiv 1\!+\!8\equiv 9,\,$So$\,9\mid 567,\,$dh$\,9\,$teilt$\,567$.

OP ist Sonderfall$\rm\ N\equiv 0\pmod{\! 9}\ $so oben bleibt es$\equiv 0\ $wenn wir kartieren$\rm N$zu seiner Quersumme$\rm\,S_N.\,$Diese Karte ist streng abnehmend für$\rm\:N > 9,\,$so Iteration erreicht es schließlich einige$\rm\: N' \le 9.\ $Aber$\rm\ N'\equiv 0\pmod{\!9}\,$So$\rm\: N' = 9\,$ $\rm (N'\!\neq0\,$von$\rm\,N>0\,$hat also eine Ziffer ungleich Null$\rm\,S_N>0)$.

Wenn die modulare Arithmetik nicht vertraut ist, können wir stattdessen Teilbarkeitsregeln verwenden oder wie folgt vorgehen:

Faktorsatz $\rm\,\Rightarrow\, X\!-\!1\mid P(X)\!-\!P(1)\ $So$\rm\ X = 10\ \Rightarrow\ 9\mid P(10)\!-\!P(1)\ $dh$\rm\; 9\mid N\! -\! S_N$

Das analoge Ergebnis gilt für jede Basis$\rm\:b,\,$dh wir können werfen$\rm\:b\!-\!1$'s in der gleichen Weise, da

$\rm\quad \bmod\, \color{}{b\!-\!1\!}:\,\ \color{#c00}{b\equiv 1}\,\Rightarrow\, N=P(\color{#c00}b) \equiv P(\color{#c00}1)= \text{sum of radix $\rm\,b\,$ digits of }\, N$

Somit$\,\rm \bbox[5px,border:1px solid #c00]{\text{the divisor $\,9\,$ is 'special' in radix $\,10\,$ because }\, \color{#c00}{10\,\equiv\, 1}\,\pmod{\! 9}}$

Ebenso werfen wir$11$ist vorbei$\!\rm\bmod 11\!:\ \color{#c00}{10\equiv -1}\,\Rightarrow\, P(\color{#c00}{10})\equiv P(\color{#c00}{-1})\equiv p_0 -p_1 + p_2 -p_3 +\cdots$

Somit$\,\rm \bbox[5px,border:1px solid #c00]{\text{the divisor $11$ is 'special' in radix $\,10\,$ because } \color{#c00}{10\equiv -1}\pmod{\!\! 11}}$

Ebenso können wir werfen$\,1001 = 7\cdot 11\cdot 13\,$indem man die alternierende Ziffernsumme in Basis nimmt$\,10^3,\,$ergibt einen kombinierten Teilbarkeitstest für$\,7,11,13\,$. Über solche modularen Reduktionen erhalten wir unzählige Teilbarkeitstests, siehe zB hier zum Austreiben$\,91$'S.

Es verdient bekannter zu werden, dass wir zur Überprüfung der rationalen Arithmetik auch Neunen streichen können - solange die Brüche Teilerfremde im Nenner sind$3$, siehe zB Hilton; Pedersen,$1981,\,$ Casting out nines revisited (diese Ergebnisse sind sehr alt). Analoge Bemerkungen gelten für jeden Ring, der hat$\ \mathbb Z/9\ $als Bild - so wie man Paritätsargumente in jedem Ring anwenden kann, der hat$\ \mathbb Z/2\ $als Bild, zB der Ring aller rationalen Zahlen mit ungeradem Nenner oder der Ring der Gaußschen ganzen Zahlen$\,\mathbb Z[i],\,$wo das Bild$\, \mathbb Z[i]/(2,i\!-\!1) \cong \mathbb Z/2\ $ergibt die natürliche Paritätsdefinition:$\, a+b\:i\ $ist gerade$\iff a\equiv b\pmod{\! 2},\,$dh wenn$\, a+b\:i\ $Karten zu$\:0\:$über den obigen Isomorphismus, der abbildet$\, 2\to 0,\ i\to 1\:$. Siehe hier für eine weitere Diskussion der Parität in Ringen von algebraischen ganzen Zahlen, einschließlich Beispielen von Zahlenringen ohne Paritätsstruktur und mit mehr als einer Paritätsstruktur. Siehe auch diesen Beitrag zum „Auswerfen von Befehlen“ in zyklischen Gruppen, und siehe diesen Thread für einen ausführlichen Vergleich verschiedener elementarer induktiver Beweise zum Auswerfen von Neunen.

Dies sind elementare prototypische Beispiele für die Problemlösung durch modulare Reduktion - einem der Grundpfeiler der abstrakten Algebra. Daher sollte man diese einfachen Beispiele unbedingt verstehen, bevor man zu fortgeschritteneren Manifestationen der modularen Reduktion übergeht.

In acht nehmen Solche Streichregeln werden oft zur Verwendung bei der Überprüfung von Arithmetik befürwortet. Aber denken Sie daran, dass solche Prüfungen nicht alle arithmetischen Fehler aufdecken werden, dh es kann viele "Falsch-Positive" geben, da die Prüfung nur verifiziert, dass Ausdrücke modulo einer kleinen Zahl entsprechen, zB ganze Zahlen mod$10$bedeutet nur, dass sie die gleichen Endziffern haben. Um dem abzuhelfen, können wir Prüfungen modulo genügend vieler teilerfremder Moduli durchführen (siehe CRT = Chinese Remainder Theorem ). Dies ist ein Beispiel für verschiedene "Lifting"-Techniken, die in modularen Berechnungsmethoden verwendet werden - über die Sie in den meisten Lehrbüchern zur Computeralgebra nachlesen können, z. B. Knuth, TAOCP, vol. 2, Seminumerical Algorithms , oder von zur Gathen: Modern Computer Algebra .

Ich nehme an, es gibt viele Möglichkeiten, dies zu sagen - was für mich Sinn machte, als ich zum ersten Mal mit dieser Tatsache konfrontiert wurde, war, dass die Zahl "$abcd$" Ist$1000a+100b+10c+d=(999a+99b+9c)+a+b+c+d$. Der erste Term ist durch klar teilbar$9$also wenn die Ziffernsumme dann "$abcd$"ist auch...

Dies folgt aus dem Teilbarkeitstest für$9$und aus der Tatsache, dass die Summe der Ziffern einer natürlichen Zahl mit mehr als einer Ziffer streng kleiner ist als die Zahl selbst, dh wenn$n$eine natürliche Zahl mit mehr als einer Ziffer ist und wenn$s(n)$bezeichnet dann die Quersumme der natürlichen Zahl$s(n)<n$. Ihre Beobachtung kann verstärkt werden, indem Sie feststellen, dass, wenn wir die Ziffern wiederholt addieren, die letzte Zahl, die uns bleibt, der Rest ist, wenn wir durch dividieren$9$.

Diese Eigenschaft beruht darauf, dass$9$ist eins minus$10$Das ist die Basis des Zahlensystems, mit dem Sie arbeiten, deshalb jede Macht$10$wird gleich$1$modulo$9$.

$9$ist auch speziell für Konten beim Auffinden von Buchhalterfehlern von Zahlendrehern.

$124+256+345=725$

$124+265+345=734$

$734-725=9$

Die „Besonderheit“ von$9$ergibt sich daraus, dass$10 \equiv 1 \pmod{9}$.

In unserem Zahlensystem zur Basis 10, in dem eine ganze Zahl ausgedrückt werden kann als

Alles, was wir tun müssen, ist, die Summe zu bewerten$d_{k} + d_{k-1} + \ldots + d_{1} + d_{0}$und überprüfe, ob es durch teilbar ist$9$um festzustellen, ob die angegebene ganze Zahl teilbar ist$9$.

Beachten Sie schließlich, dass es einen ähnlichen Test mit analoger Begründung auch gibt, um festzustellen, ob eine bestimmte ganze Zahl durch teilbar ist$3$, als$10 \equiv 1 \pmod{3}$.