kongruenz

hi,

wie kann man alle lösungen der folgenden kongruenz bestimmen:

x * y ≡ 0 mod 21

hat jemand eine idee?

SeppJ

Kann man da vielleicht was mit Primfaktorzerlegung machen? 21 hat ja schönerweise nur 2, das heißt alle Kombinationen wo x und y aus insgesamt gleich vielen 3 und 7 zusammengesetzt sind, sind Lösungen.

heißt das dann folgendes?

a * (3 * 7) ≡ 0 mod 21

wobei a ein Element natürlicher Zahlen ist
und x = 3 und y = 7

bsp.:

...
-2 * (3 *7) ≡ 0 mod 21
-1 * (3 *7) ≡ 0 mod 21
0 * (3 *7) ≡ 0 mod 21
1 * (3 *7) ≡ 0 mod 21
2 * (3 *7) ≡ 0 mod 21
...

Christoph

SeppJ schrieb:

Kann man da vielleicht was mit Primfaktorzerlegung machen? 21 hat ja schönerweise nur 2, das heißt alle Kombinationen wo x und y aus insgesamt gleich vielen 3 und 7 zusammengesetzt sind, sind Lösungen.

Es ist sogar noch kürzer: Sobald in x*y die 3 und die 7 jeweils mindestens einmal auftauchen, kommt 0 heraus. Das ist aber nur eine hinreichende Bedingung, keine notwendige. x und y sind keine natürlichen Zahlen mit eindeutiger Primfaktorzerlegung, sondern Repräsentanten modulo 21. Je nachdem, welchen Repräsentanten man wählt, bekommt man eine andere Primfaktorzerlegung, deswegen muss man etwas vorsichtig sein, damit zu argumentieren (ich schließe nicht aus, dass es geht, aber man muss vorsichtig sein).

Allgemein dürfte es sehr viele Lösungen für diese Kongruenz geben, vermute ich. Deswegen wär mein erster Ansatz: Computerprogramm schreiben, das alle Kombinationen von x und y ausprobiert. Ein schnellerer Algorithmus wird sich denke ich nur dann lohnen, wenn es verhältnismäßig sehr wenige Paare (x,y) gibt, die diese Gleichung erfüllen.

Ich hab gerade mal so ein Programm geschrieben in ghci (Link). Eine Ausgabe wie (21,0.1473922902494331) bedeutet dabei, dass etwa 14,7% aller möglichen Paare (x,y) die Gleichung
x * y = 0 (mod 21)
lösen.

Prelude> let ok n x y = x * y `mod` n == 0
Prelude> let pairs n = [(x,y) | x <- [0..n-1], y <- [0..n-1]]
Prelude> let ratio n = (fromIntegral $ length $ filter id $ map (uncurry (ok n)) (pairs n)) / fromIntegral (n * n)
Prelude> mapM_ (\n -> print (n, ratio n)) $ [1..30] ++ [40,50..100] ++ [200,300..1000] ++ [10000]
(1,1.0)
(2,0.75)
(3,0.5555555555555556)
(4,0.5)
(5,0.36)
(6,0.4166666666666667)
(7,0.2653061224489796)
(8,0.3125)
(9,0.25925925925925924)
(10,0.27)
(11,0.17355371900826447)
(12,0.2777777777777778)
(13,0.14792899408284024)
(14,0.1989795918367347)
(15,0.2)
(16,0.1875)
(17,0.11418685121107267)
(18,0.19444444444444445)
(19,0.10249307479224377)
(20,0.18)
(21,0.1473922902494331)
(22,0.13016528925619836)
(23,8.506616257088846e-2)
(24,0.1736111111111111)
(25,0.104)
(26,0.11094674556213018)
(27,0.1111111111111111)
(28,0.1326530612244898)
(29,6.777645659928656e-2)
(30,0.15)
(40,0.1125)
(50,7.8e-2)
(60,0.1)
(70,7.163265306122449e-2)
(80,6.75e-2)
(90,7.0e-2)
(100,5.2e-2)
(200,3.25e-2)
(300,2.8888888888888888e-2)
(400,1.95e-2)
(500,1.36e-2)
(600,1.8055555555555554e-2)
(700,1.3795918367346938e-2)
(800,1.1375e-2)
(900,1.3481481481481481e-2)
(1000,8.5e-3)
(10000,1.26e-3)
Prelude>

Der Anteil scheint mit steigendem n doch ein bisschen kleiner zu werden, ein geschickterer Algorithmus könnte sich also für große n lohnen.

volkard

Aber eine Zahl, die vom Repräsentatten 3 dargestellt wird, also egal*21+3 ist durch 3 teilbar und enthält den Primfaktor 3 mindestens einmal.
Ist sie doch hinreichend und notwendig?

Christoph

volkard schrieb:

Aber eine Zahl, die vom Repräsentatten 3 dargestellt wird, also egal*21+3 ist durch 3 teilbar und enthält den Primfaktor 3 mindestens einmal.
Ist sie doch hinreichend und notwendig?

Guter Punkt, da hab ich nicht richtig nachgedacht.

Für allgemeine Zahlen, nicht nur welche mit 2 Primfaktoren, konnte ich das aber gerade nicht in ein elegantes Programm gießen. Mein Ansatz war, dass man die Primfaktorzerlegung von n berechnet, dann diese Primfaktoren auf x und y verteilt in allen möglichen Kombinationen, dann alle Vielfachen bildet. Das sind dann alles Lösungen für die Gleichungen.
Dabei stellten sich mir zwei Fragen:

Vielfache bis zu welcher Grenze? Möglicherweise reicht es, Vielfache zu betrachten, die kleiner als n sind. Wäre auch für die Laufzeitkomplexität gut, wenn das so wäre.
Wie Duplikate verhindern? Zum einen kann es mehrmals denselben Primfaktor geben, aber Duplikate können auch bei verschiedenen Primfaktoren auftreten.

also gehen folgende zusammensetzungen?

21 = 1 * 21 = 21 = 3 * 7
42 = 2 * 21 = 21 + 21 = 3 * 7 + 3 * 7
63 = 3 * 21 = 21 + 21 + 21 = 3 * 7 + 3 * 7 + 3 * 7
84 = 4 * 21 = 21 + 21 + 21 + 21 = 3 * 7 + 3 * 7 + 3 * 7 + 3 * 7
...

z = n * (x * y)

n * (x * y) ≡ 0 mod 21 mit x=3, y=7

ist das dann die "formel", um so zu zeigen, dass dies *alle* lösungen der gegebenen kongruenz sind oder wie gebe ich das an?

ich gehe davon aus, dass das bei negativen n auch so funktioniert?

volkard

Ich schreib auch mal was.
Vermutung 1: Sobald in x*y die 3 und die 7 jeweils mindestens einmal auftauchen, kommt 0 heraus.

Oder anders: Wenn x oder y schon durch 21 teilbar sind, ist die jeweils andere Zahl beliebig. Ansonsten muß eine der Zahlen durch 3 und die andere durch 7 teilbar sein.

Test für x,y<10000

#include <iostream>
using namespace std;

bool testA(int x,int y){
	return (x*y)%21==0;
}

bool testB(int x,int y){
	if (x%21==0) return true;
	if (y%21==0) return true;
	if (x%3==0 && y%7==0) return true;
	if (x%7==0 && y%3==0) return true;
	return false;
}

int main(){
	for(int x=0;x<10000;++x){
		for(int y=0;y<10000;++y){
			if(testA(x,y)!=testB(x,y))
				cout<<"Fehler bei x="<<x<<", y="<<y<<'\n';
		}
	}
}

Jup, kein Fehler.

Härtere Vermutung: Repräsentanten-Rechnung reicht vollkommen aus.
Test

bool testB(int x,int y){
	return testA(x%21,y%21);
}

Jup, kein Fehler.

Wie bestimme ich bei folgender Kongruenz *alle* Lösungen?

x² ≡ 9 mod 16

Also die ersten x sind 3, 5, 11, 13, 19, ... wie bekomme ich den Rest raus?
Komischerweise sind das alles gefundene Primzahlen, zwar nicht alle, aber die gefundenen sind welche...?

otze

new_user__ schrieb:

Also die ersten x sind 3, 5, 11, 13, 19, ... wie bekomme ich den Rest raus?

Der Rest könnten ziemlich viele sein, weils dort mit Sicherheit Äquivalenzklassen gibt -> unendlich viele Lösungen. Übrigens wunderts nicht, dass du da vor allem Anfang fast nur primzahlenr aus kriegst. Denn Gerade zahlen können die Lösung nicht sein.

Um genau zu sein, liegen die Lösungen schonmal in der Äquivalenzklasse: (wenn x' eine Lösung ist):

dann ist:
x=x'+n*16 mod 16 n>=0
auch eine Lösung

Beweis, dass dies eine Lösung ist:
x^{2=(x'+n*16)*(x'+n*16)=x'}2+n*16*x' +n^2*16*16=x'2 (mod 16)

Also wenn 3 eine Lösung is, dann auch 19,35,51...