Beste Antwort
Sagen Sie, 2 ^ 32 + 1 ist teilbar durch m.
Also, 2 ^ 32 = -1 (mod m)
(2 ^ 32) ^ 3 = (- 1) ^ 3 ( mod m)
2 ^ 96 = -1 (mod m)
2 ^ 96 + 1 = 0 (mod m)
Also die richtige Antwort ist 2 ^ 96 + 1
Antwort
Sie tun es nicht. Schauen Sie zum Beispiel, was passiert, wenn x = 12. Sie erhalten x ^ 2 = 144 = 24 \ cdot 6, aber x ist nicht durch 24 teilbar.
Ich könnte hier aufhören, aber das wäre nicht lehrreich , außer zu sagen, dass Sie falsch liegen. Das ist nicht besonders hilfreich.
Schließlich kann ich das beweisen, wenn k | x ^ 2 (lesen Sie, dass „k x ^ 2 teilt“), dann k | x für viele k, einschließlich 21, 22, 23, 26, 29 und 30, aber nicht für 20, 24, 25, 27 oder 28. Was ist der Unterschied? Hier werden die Dinge interessant und lehrreich.
Was wissen wir über x? Wir wissen durch den Fundamentalsatz der Arithmetik, dass x eindeutig als Produkt von Primzahlen dargestellt werden kann: x = 2 ^ {a\_2} 3 ^ {a\_3} 5 ^ {a\_5} \ cdots. Jeder (oder alle, für x = 1) dieser a\_p-Werte könnte 0 sein, und tatsächlich ist nur eine endliche Anzahl von ihnen ungleich Null.
Das bedeutet, dass x ^ 2 = 2 ^ { 2a\_2} 3 ^ {2a\_3} 5 ^ {2a\_5} \ cdots. Alle Exponenten sind jetzt gerade.
Was wissen wir über k? Nach demselben Satz wissen wir, dass k = 2 ^ {k\_2} 3 ^ {k\_3} 5 ^ {k\_5} \ cdots.
Wie hängt dies mit der Teilbarkeit zusammen? Wenn k | x ^ 2 bedeutet, dass k\_2 \ leq 2a\_2, k\_3 \ leq 2a\_3, \ dots, k\_p \ leq 2a\_p, \ dots. Wenn jedoch k | x, das heißt, k\_2 \ leq a\_2, k\_3 \ leq a\_3, \ dots, k\_p \ leq a\_p.
Also müssen wir wirklich alles tun, um zu beweisen, ob x ^ 2 durch k teilbar ist, dann x ist teilbar durch k zeigt, dass wenn k\_p \ leq 2a\_p, dann k\_p \ leq a\_p. Da k\_p, a\_p eine beliebige nichtnegative ganze Zahl sein kann, können wir uns das einfachere Problem ansehen: Unter welchen Bedingungen haben wir b \ leq 2c, was b \ leq c impliziert?
Grundsätzlich versuchen wir, Werte zu finden von b, wobei der Ausdruck c \ leq 2c für kein c gilt. Da es kein c gibt, funktioniert b = 0. Für b = 1 müssen wir c = 0 haben, und so ist 1 \ not \ leq 2c = 0, also funktioniert b = 1.
Aber für b> 1 ist dies nicht der Fall Arbeit. Sie können immer c = b-1
Um dies auf unser Problem zurückzuführen, bedeutet dies, dass wir k | sagen können x ^ 2 \ impliziert k | x nur, wenn die Exponenten der Primzahlen in k entweder 0 oder 1 sind. Diese Werte von k werden als „quadratfrei“ bezeichnet, da Sie sie nicht durch eine quadratische Zahl teilen können.
Sie können also k anzeigen | x ^ 2 \ impliziert k | x wenn k quadratfrei ist.
Für die Zahlen, die ich oben betrachtet habe, ist 20 durch das Quadrat 4 teilbar, 24 ist durch das Quadrat 4 teilbar, 25 ist quadratisch, 27 ist durch das Quadrat 9 teilbar , 28 ist durch das Quadrat 4 teilbar. Die anderen Zahlen 21, 22, 23, 26, 29, 30 sind alle quadratfrei, was Sie überprüfen können, wenn Sie möchten.