# inverse of 985 mod(φ60131)

Alright Ive been working on this one for a while I found φ(60131) to be 97294

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


then I worked through the GCD

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


Now Im stuck trying to find the inverse of 985 mod φ(60131) this is the work I have

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


I was expecting 8687699 to be divisible by 97294 what went wrong?

-
Shouldn't this belong in math.stackexchange, though? I mean, the relation to crypto is hazy at best, this is more of a computation question than anything else. –  Thomas Aug 6 '12 at 13:22
@Thomas Since this algorithm is fundamental to the operation of RSA, crypto seems like a reasonable location. I believe it was originally tagged with "homework", so I assume this is some sort of assignment to demonstrate breaking of RSA by factoring the public key. –  Iridium Aug 6 '12 at 18:54
Thanks lridium I didnt think much before posting and I didnt even know that there was a crypto stackexchange I was searching for help before posting and saw a similar problem where I originally posted it –  Mintybacon Aug 6 '12 at 22:50

## migrated from stackoverflow.comAug 6 '12 at 11:40

This question came from our site for professional and enthusiast programmers.

I think you may have calculated φ(60131) incorrectly.

60131 has two prime factors: 157, 383 Therefore: φ(60131) = (157-1) * (383-1) = 59592

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


So to determine the inverse of 985 mod φ(60131):

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


Therefore 121 is the inverse of 985 mod φ(60131).

-