Gleichung mit MOD

[silentAMD]

hi,
ich komme bei meiner facharbeit über codierungen nicht weiter... dafür müsste ich folgende gleichung lösen können, aber ich weiss nicht wie:

Code:

(x*b) MOD 29 = a

dabei ist x eine unbekannte!


PLEASE HELP!!

[ulrich.b]

Für x gibt es auf jeden Fall unendlich viele Lösungen ...

wenn zb. b = 29 und a = 0 dann gilt die gleichung für den gesamten natürlichen Zahlenbereich.

[silentAMD]

sorry hab vergessen zu erwähnen, dass a ungleich 0 ist und die definitionsmenge {0,1...28} ist

[omata]

Hallo silentAMD,

hier mal mein Versuch...

Code:

a mod b = a - (a / b)*b


(x*b) - (x*b / 29) = a

x*b*29    x*b
------ - ----- = a
  29      29

x*b*29 - x*b
------------ = a
     29

x*b * (29 - 1)
-------------- = a
      29


x*b*28 = 29*a

     29a
x = -----
     28b

Gruss
Thorsten

[DelphiProgrammierer]

Eine Anmerkung:

Code:

a mod b = a - (a div b)*b

[omata]

@DelphiProgrammierer: Du hast natürlich recht, danke. Habs oben korrigiert.

Gruss
Thorsten

[gammatester]

Zitat von silentAMD:

sorry hab vergessen zu erwähnen, dass a ungleich 0 ist und die definitionsmenge {0,1...28} ist

Da 29 eine Primzahl ist hat jedes a ein Inverses b=a^-1 mod 29. Eine einfache Formel ist hier (da a^28 = 1 mod 29 für alle a)

b=a^-1 = a^27 mod 29

Gruß Gammatester

[silentAMD]

vielen dank für die vielen antworten!

leider hat mir keine bei diesem problem geholfen... dafür aber bei einem anderen (x-b statt x*b)... wie kann ich die letzte antwort in delphi umsetzen?

[gammatester]

Zitat von silentAMD:

vielen dank für die vielen antworten! :thumb:

leider hat mir keine bei diesem problem geholfen... dafür aber bei einem anderen (x-b statt x*b)... wie kann ich die letzte antwort in delphi umsetzen?

Delphi-Quellcode:

{solve x*b=a mod 29}
{ x = a*b^27 mod 29}

{$apptype console}
var
  a,b,x,i: integer;
begin
  {Deine Werte, aber besser eine procedure}
  a := 3;   b := 4;
  x := a;
  for i:=1 to 27 do x := x*b mod 29;
  writeln(x:4, x*b mod 29:4, (x*b-a) mod 29: 4);
end.

Die Formel x = a*b^27 mod 29 hat allerdings nur didaktischen Wert, besser ist eine Berechnung von b^-1 mit dem erweiterten Euklidischen Algorithmus und speichern aller Inversen in einen Vektor inv: array[1..28] of integer.

Gruß Gammatester

[silentAMD]

Code:

Die Formel x = a*b^27 mod 29 hat allerdings nur didaktischen Wert, besser ist eine Berechnung von b^-1 mit dem erweiterten Euklidischen Algorithmus und speichern aller Inversen in einen Vektor inv: array[1..28] of integer.

würde ein byte array reichen?? das problem ist, dass ich dies mathematisch lösen muss...


ein weiteres problem:

die funktionen

- x = (a+b) mod 29 (kurz: x = a +29 b)
- x = (a*b) mod 29 (kurz: x = a *29 b)
- a = (x+b) mod 29 (kurz: x = a -29 b)
- a = (x*b) mod 29 (kurz: x = a /29 b)

funktionieren im einzelnen. etwas (ist verlangt) wie f(x) = a *29 x +29 b (x variabel, a und b natürliche zahlen) funktioniert zwar, aber wie ich auf die umkehrformel (um das x herauszufinden) komme ist mir nicht schlüssig... wie bekomme ich solch eine formel und wie lautet sie?