Was ist die Mächtigkeit der Menge (siehe Bild)?
Im Bild ist dabei p eine Primzahl. Kann man die Mächtigkeit bestimmen oder gibt es eine Schranke hierfür? Was ich suche, nach einer Primzahl p, so dass die Mächtigkeit von H echt kleiner als p^2 ist. Gibt es so ein p? Hierbei ist x in der Menge {0,...p-1} Danke
1 Antwort
Unter den genannten Vorgaben berechnet man mit a x + b (mod p) zunächst p^2 Zahlen. Die daraus gebildete Menge hat weniger als p^2 Elemente, wenn es eine Lösung der linearen Kongruenz
a1 x + b1 = a2 x + b2 (mod p) für geeignete a1, a2, b1, b2 gibt.
Wir schreiben das als
(a1-a2) x = b2-b1 (mod p)
Wegen ggT(a1-a2, p) = 1 hat diese genau eine Lösung x mod p. Dieses x muss nicht gleich dem vorgegebenem x sein. Aber man kann x entsprechend vorgeben.
Ich denke sogar, dass unter den (p^2 über 2) möglichen linearen Kongruenzen alle x von 0 bis p-1 als Lösung vorkommen, kann es aber auf die Schnelle nicht beweisen.