x^2=x (mod 10^n)

23.01.2006, 11:53	Brox	Auf diesen Beitrag antworten »
x^2=x (mod 10^n) Ich hab eine Hausaufgabe bei der ich entscheiden soll ob es immer n-stellige Zahlen gibt mit x^2 = x (mod 10^n). Ein paar solche Zahlen sind: 5 25 625 9376 90625 Das es _belibige_ Zahlen x gibt die das erfüllen kann man hierdurch zeigen: ggT(2^n,5^n)=a2^n+b5^n setze x:=b5^n Dann folgt: x=1-a2^n x^2=x-ab10^n x^2=x (mod 10^n) Es bleibt aber zu zeigen, dass man auch immer n-stellige Zahlen nehmen kann. Zum bespiel ist für n=4, 1=15^4-392^4 und damit x=5^4=625 also (0625)^2=390625 - aber 0625 ist 3-stellig!
24.01.2006, 16:07	Brox	Auf diesen Beitrag antworten »
Ich bin nah dran aber mir fehlt einfach der letzte Schritt. x^2 = x (mod 10^n) <=> a^2 = a (mod 2^n) und b^2 = b (mod 5^n) wenn x=a (mod 2^n) und x=b (mod 5^n). Es stellt sich herraus, dass a = 0 oder a = 1 und b = 0 oder b = 1 gilt. Es gibt also für jedes n 4 simultane Kongruenzen zu lösen und für jede simultane Kongruenz können wir [x] eindeutig aus Z/10^n bestimmen. Weiter findet man raus, dass für a = 1 und b = 1 nur x = 1 in Frage kommt und für a = 0 und b = 0 nur x = 0. D.h wir haben nur noch zwei simultane Kongruenzen übrig! Wenn a = 1 und b = 0 folgt: (1,2,3,4,...,n) x = 5,25,625,625,90625,890625,2890625... und für a = 0 und b = 1 x = 6,76,376,9376,9376,109376 Wo es bei mir hapert ist hier: Wir sollen nicht zeigen, dass es für jedes n ein x mit x^2=x (mod 10^n) gibt (x=0 wäre die kurze Antwort) sondern, dass es für jedes n ein n-stelliges x mit x^2 = x (mod 10^n) gibt!! Wie man sieht ist für n=4 x=625 nur 3-stellig. Dann kann man aber x=9376 nehmen und hat ein 4-stelliges x. Die Behauptung ist also: Man kann für jedes n eine der zwei Möglichen - nicht trivialen - x auswählen, dass n-stellig ist! Ich weiß aber leider nicht wie ich das machen kann. Wie zeig ich 10^(n-1) <= x <= 10^n?
24.01.2006, 16:20	AD	Auf diesen Beitrag antworten »
Du hast also eine positive maximal n-stellige Zahl $\begin{eqnarray} x \end{eqnarray}$ mit $\begin{eqnarray} x(x-1)\equiv 0\mod 10^n \end{eqnarray}$ gefunden, gut. 1) Im Fall $\begin{eqnarray} x\geq 10^{n-1} \end{eqnarray}$ bist du fertig. 2) Im Fall $\begin{eqnarray} x<10^{n-1} \end{eqnarray}$ betrachtest du statt $\begin{eqnarray} x \end{eqnarray}$ einfach $\begin{eqnarray} x' := 10^n+1-x \end{eqnarray}$ . Dann ist nämlich $\begin{eqnarray} x'>9\cdot 10^{n-1} \end{eqnarray}$ , also garantiert n-stellig und es gilt $\begin{eqnarray} x'(x'-1) = (10^n+1-x)(10^n-x) \equiv (1-x)(-x) = x(x-1) \equiv 0\mod 10^n \end{eqnarray}$ Das Beispiel (625,9376) mit 625+9376=10001 hätte dich auch auf diese Idee bringen müssen...
24.01.2006, 17:44	AD	Auf diesen Beitrag antworten »
Erst drängeln und dann keine Reaktion? Na dann ist wohl alles klar.
24.01.2006, 17:56	Brox	Auf diesen Beitrag antworten »
Danke ^^

1

Verwandte Themen