Warum scheinen alle "Teilbarkeitstricks" lineare Kombinationen zu verwenden, und gibt es welche, die dies nicht tun?

Wenn ich „Teilbarkeitstrick“ sage, meine ich „einen rekursiven Algorithmus, der zeigen soll, dass nach mehreren Iterationen, wenn die endgültige Ausgabe ein Vielfaches der gewünschten Zahl ist, das Original auch ein Vielfaches derselben Zahl war“. Hier ist ein Beispiel für einen Teilbarkeitstrick für 17.

Umschreiben N als 10 Q + R , mit R < 10 . Dann auswerten | Q − 5 R | . Wiederholen Sie diesen Vorgang, bis Sie mit einer leicht faktorisierbaren Zahl übrig bleiben.

Hier ist ein anderes.

Umschreiben N als 100 Q + R , mit R < 100 . Dann auswerten | R − 2 Q | . Wiederholen Sie diesen Vorgang, bis Sie mit einer leicht faktorisierbaren Zahl übrig bleiben.

Um zu zeigen, dass beide funktionieren (oder zumindest für eine bestimmte Nummer funktionieren), probieren wir beide an 31382 .

METHODE EINS: 31382 → 3128 → 272 → 17 , ergo 17   |   31382 .

METHODE ZWEI: 31382 → 544 → 34 , ergo 17   |   31382 .

Diese Teilbarkeitstricks basieren darauf, die Zahl in Zifferngruppen zu zerlegen und eine lineare Operation darauf anzuwenden. Wenn wir jedoch versuchen, eine nichtlineare Funktion zu verwenden , scheinen die Dinge zusammenzubrechen. Zum Beispiel, wie Methode man hier darauf zurückgreift 17   |   51 und die zweite stützt sich auf 17   |   119 , lassen Sie uns versuchen, etwas mit zu tun 17   |   34 . Nämlich:

Umschreiben N als 10 Q + R , mit R < 10 . Dann auswerten | 6 Q 2 − 5 R | . Wiederholen Sie diesen Vorgang, bis Sie mit einer leicht faktorisierbaren Zahl übrig bleiben.

Damit können wir es versuchen 34 und siehe, ja, 6 ( 9 ) − 5 ( 4 ) = 34 , So 17   |   34 . Aber das schlägt bei den meisten Zahlen fehl. Für 51 , wir haben 51 → 145 , und es weicht von dort ab (beachten Sie auch das 17 ⧸ |   145 ). Sogar mit 17 , was offensichtlich ein Vielfaches von ist 17 , wir haben 17 → 29 .

Was trennt hier sozusagen die Spreu vom Weizen? Warum scheint es, wenn wir die Ziffern des Vielfachen einer Primzahl aufschlüsseln und eine lineare Beziehung um sie herum herstellen, für alle anderen Vielfachen der Primzahl zu gelten, aber das Gleiche gilt beispielsweise nicht für eine Quadratzahl? Beziehung?

Das mag daran liegen, dass sie „Tricks“ genannt werden. Tricks sind normalerweise Dinge, die Menschen leicht in ihrem Kopf machen können. Und im Allgemeinen sind die Operationen, die wir in unserem Kopf ausführen können, eher linear. Am Ende kann es sich also um einen Selektionsbias handeln.
Ich habe eine Anmerkung hinzugefügt, die die Genese der linearen Operationen in der rekursiven Form der Teilbarkeitstests erklärt.

Antworten (3)

Nein, Teilbarkeitstests sind nicht auf lineare Formen beschränkt . Wie hier & hier erklärt die Regel zum Auswerfen von Neunen: 9 ∣ 10 A + B ⟺ 9 ∣ A + B erstreckt sich zu einem höheren Grad als 9 ∣ P ( 10 ) ⟺ 9 ∣ P ( 1 ) [von Mod 9 :   P ( 10 ) ≡ P ( 1 ) ] , für jedes Polynom P ( X ) mit ganzzahligen Koefs (durch P C R unter). Wenn N = P ( 10 ) Dann P ( 1 ) ist die Summe der Dezimalstellen von N . Ähnlich 11 ∣ 10 A + B ⟺ 11 ∣ A − B erstreckt sich auf 11 ∣ P ( 10 ) ⟺ 11 ∣ P ( − 1 ) = alternierende Ziffernsumme.

Die gängigen Tests, auf die Sie sich beziehen, entsprechen umgekehrten Formen der obigen Teilbarkeitstests, z Mod 17 :   10 A + B ≡ 0 ⟺ 10 ( A + B / 10 ) ≡ 0 ⟺ A − 5 B ≡ 0 von 1 / 10 ≡ − 5 , dh es entsteht durch Skalierung durch 10 − 1 ≡ − 5 . Ebenso, wenn Grad ⁡ P = k dann Skalierung durch ( − 5 ) k ≡ 10 − k ändert alle Befugnisse von 10 In P ( 10 ) in Potenzen von − 5 , wodurch die Koefs effektiv umgekehrt werden , z. B. für ein Quadrat

      Mod 17 :     0 ≡ A 10 2 + B 10 + C ⏞ P ( 10 ) ⟺ ×   ( − 5 ) 2   0 ≡ C ( − 5 ) 2 + B ( − 5 ) + A ⏞ P ~ ( − 5 )

daher 17 ∣ P ( 10 ) ⟺ 17 ∣ P ~ ( − 5 ) = umgekehrtes Poly in Radix − 5 , von 10 ( − 5 ) ≡ 17 1 , z.B

17 ∣ 901     B j     17 ∣ 109 − 5 = 1 ( − 5 ) 2 + 0 ( − 5 ) + 9 = 34

Solche Radix Reziprozität Teilbarkeit durch D Tests existieren für alle Radikale R 1 , R 2 reziprok sein Mod D , dh wann R 1 R 2 ≡ 1 , zB für binär R 2 :   10 ( 2 ) ≡ 19 1 Und 10 ( − 2 ) ≡ 21 1 , So

19 ∣ 912     B j     19 ∣ 219 2 =   2 ( 2 ) 2   +   1 ( 2 )   +   9 = 19 21 ∣ 924     B j     21 ∣ 429 − 2 = 4 ( − 2 ) 2 + 2 ( − 2 ) + 9 = 21

Dies ist nur eines von zahlreichen Beispielen für Teilbarkeitsschlüsse höheren Grades, die in der Zahlentheorie und Algebra allgegenwärtig sind. Solche Schlüsse werden offensichtlich, sobald man Kongruenzen und modulare Arithmetik beherrscht (siehe insb. P C R = Polynomielle Kongruenzregel , dh A ≡ B ⇒ P ( A ) ≡ P ( B ) ) .

Siehe hier für mehr über umgekehrte (reziproke) Polynome und hier für eine ähnliche Anwendung solcher.

Notiz Der Grund, warum diese Teilbarkeitstests als Iterationen linearer Operationen ausgedrückt werden können, liegt darin, dass auf diese Weise Polynome erzeugt werden können (verschachtelte Horner-Form), z

A 0 + A 1 X + A 2 X 2 + A 3 X 3 = A 0 + X ( A 1 + X ( A 2 + X ( A 3 ) ) )

dh Polynome können durch iterierende lineare Operationen erzeugt werden F N + 1 = C N + 1 + X F N , also jede Polynomoperation (z. B. Auswertung Mod D ) kann durch rekursives Huckepack auf diesem induktiven Erzeugungsprozess durchgeführt werden (siehe strukturelle Induktion ).

Auf diese Weise rekursive Auswertung Mod D eines Polynoms (Darstellung einer ganzen Zahl in Basisschreibweise) führt zu einem universellen Test auf Teilbarkeit durch D , das funktioniert durch wiederholtes Modifizieren führender Ziffernblöcke Mod D (wie handschriftliche Division, aber ohne Quotienten). Ihre Tests können als umgekehrte Form eines solchen Tests angesehen werden. Die Vorwärtsform hat gegenüber der umgekehrten Form den Vorteil, dass sie den genauen Rest liefert, sodass sie für viel mehr als nur Teilbarkeitstests verwendet werden kann.

Lassen Sie uns den universellen Vorwärtstest zum Berechnen verwenden 43211 Mod 7. Der Algorithmus besteht darin, die ersten beiden führenden Ziffern wiederholt zu ersetzen   D N   D N − 1   von ( 3 D N + D N − 1 ) Mod 7 , seit 10 D N + D N − 1 ≡ 3 D N + D N − 1 ( Mod 7 )

Mod 7 :   4   3   2   1   1 | | ≡ 1   2   1   1 B j     3 ⋅ 4 + 3 ⏞ 3   D N + D N − 1 ≡   1 ≡ 5   1   1 B j       3 ⋅ 1 + 2   ≡   5 ≡ 2   1 B j       3 ⋅ 5 + 1   ≡   2 ≡ 0 B j       3 ⋅ 2 + 1   ≡   0  

Somit   43211 ≡ 0 ( Mod 7 ) , In der Tat   43211 = 7 ⋅ 6173. Im Allgemeinen ist die modulare Arithmetik einfacher, wenn wir Residuen kleinster Größe verwenden , z ± { 0 , 1 , 2 , 3 }   ( M Ö D   7 ) , indem Sie negative Ziffern zulassen , zB hier . Beachten Sie das für den Modul 11 oder 9 das obige Verfahren reduziert sich auf die bekannten Teilbarkeitstests durch 11 oder 9 (auch bekannt als "Neunen auswerfen" für Modulus 9 ).

Wir können "Teilbarkeitstricks" erfinden, die diese Eigenschaft nicht haben. Zum Beispiel:

„Um zu testen, ob N ist teilbar durch 3 , schreiben N als 10 Q + R . Dann berechnen Q 3 + R 3 und sehen Sie, ob dies durch teilbar ist 3 ."

Das funktioniert wegen des kleinen Satzes von Fermat: für alle ganzen Zahlen A und Primzahlen P , A P ≡ A ( Mod P ) . Insbesondere, Q 3 ≡ Q ( Mod 3 ) Und R 3 ≡ R ( Mod 3 ) , So Q 3 + R 3 ≡ Q + R ≡ 10 Q + R ( Mod 3 ) .

Das ist kein guter Trick! Nicht, weil es nicht funktioniert, sondern weil es überprüft wird Q 3 + R 3 für die Teilbarkeit durch 3 ist wahrscheinlich schwieriger als zu überprüfen N War.

In sehr speziellen Fällen können wir uns diese Art von Trick jedoch zunutze machen. Zum Beispiel, wenn Sie versuchen herauszufinden, ob 10000256 ist teilbar durch 7 , es könnte helfen, das zu erkennen 10000256 = 10 7 + 2 ⋅ 2 7 , ist also deckungsgleich mit 10 + 2 ⋅ 2 = 14 modulo 7 .

Ich würde nicht sagen, dass es generell stimmt, dass diese linearen Reduktionen die Teilbarkeit bewahren; Es werden spezifische Entscheidungen getroffen, damit dies funktioniert. Für die erste Beziehung, wo N = 10 Q + R :

Q − 5 R = Q − 5 ( N − 10 Q ) = 51 Q − 5 N ≡ − 5 N (Mod. 17) .
So Q − 5 R ist teilbar durch 17 iff N ist teilbar durch 17 . Der Schlüssel ist das Verschwinden des zusätzlichen Begriffs (in diesem Fall 51 Q ) beim Arbeiten modulo 17 . Dies kann bei einem Ausdruck, der quadratisch in ist, nicht passieren Q und linear ein R ... R ist linear ein Q Und N , also nichts neues Q 2 Begriff, um denjenigen abzubrechen, mit dem Sie beginnen. Abgesehen davon, dass diese Art der Methode nur hilfreich ist , wenn die Werte kleiner werden ... ausgehend von N = 10 Q + R Zu | 6 Q 2 − 5 R | , zum Beispiel, hat diese Garantie nicht.

Warum scheinen alle "Teilbarkeitstricks" lineare Kombinationen zu verwenden, und gibt es welche, die dies nicht tun?
AntwortenHierDatenschutz-Bestimmungen1y, 0v