Invers von 985 mod (φ60131)

  • Okay, ich habe eine Weile an diesem gearbeitet. Ich fand, dass φ (60131) 97294 ist

    ½(60131+60131(5)^.5) = 97294
     

    dann habe ich die GCD durchgearbeitet

    GCD(985,97294) = 1
    97294 = 985*98+764
    985=764*1+221
    764 = 221*3+101
    221 = 101*2+19
    101=19*5+6
    19= 6*3+1
    6 = 1*6     GCD = 1
     

    Jetzt bleibe ich beim Versuch Um die Umkehrung von 985 mod φ (60131) zu finden, ist diese Arbeit die ich habe

    19 – (6*3) = 1 --> 19 – (101 – (19*5))*3 = 1 19*15 - 284 = 1 --> (221 – (101*2))*15 – 284 = 1 -101*30+3031=1 --> -(764-(221*3))*30+3031 = 1 221*90-19889 --> (985 - 764)*90-19889=1 -764*90+68761=1 --> -(97294-(985*98))*90+68761=1 985*8820-8687699 = 1

    Ich hatte erwartet, dass 8687699 durch 97294 teilbar ist. Was ist schiefgegangen?

    06 August 2012
    Mintybacon
1 answer
  • Ich denke, Sie haben φ (60131) möglicherweise falsch berechnet.

    60131 hat zwei Primfaktoren: 157, 383 Deshalb: φ(60131) = (157-1) * (383-1) = 59592

    GCD(985,59592) = 1
    59592 =  60 * 985 + 492
      985 =   2 * 492 + 1
      492 = 492 * 1
     

    So bestimmen Sie die Inverse von 985 mod φ (60131):

    1 = 985 - 2 * 492 1 = 985 - 2 * (59592 - 60 * 985) 1 = 985 - 2 * 59592 + 120 * 985 1 = 121 * 985 - 2 * 59592

    Daher ist 121 das Inverse von 985 mod φ (60131).

    06 August 2012
    Iridium