rendered paste body#!/usr/bin/env python#Author: Shriphani Palakodety#Mail: spalakod@purdue.edu#Mail: shriphani@shriphani.comdef gcd(a, b): if b == 0: return a else: return gcd(b, a % b)def gcdStep(a, b): return (a, b, a/b, a%b)def getModInv(a, b): '''Get x^-1 = a % b''' if a < b: (a,b)=(b,a) gcd_val = gcd(a, b) if gcd_val != 1: return "No Inverse Exists" else: values = [] while b>0: values.append(gcdStep(a,b)) (a,b)=(b, a%b) values.pop(0) values.pop(-1) sum = 0 for val in values: sum+=val[2] return sumprint getModInv(13, 42*58 )