Here’s fnPad code to calculate the modular inverse.

// calculate the modular inverse
a = 5; b = 93
i = modi(a,b); i ≈ 56
i*a%b == 1 ≈ true // show that i is the modular inverse
// modular inverse of a mod b
modi(a,b) = mode(egcd(a,b),b)
// modular inverse given extended GCD (GCD must be 1)
mode(e,b) = ( e[1] == 1 ) ? e[2]%b + ( ( e[2] < 0 ) ? b : 0 ) : NaN
// extended greatest common divisor
egcd(a,b) = ( b == 0 ) ? { a, 1, 1 } : dcge(egcd(b,a%b),a/b)
// unwind from GCD; recurrence relation makes e[1] = e[2]*a + e[3]*b
dcge(e,q) = { e[1], e[3], e[2]-e[3]*q }

posted @ 07:39 AM EST

Here’s a reference for the algorithm used in the previously posted fnPad code that calculates the modular inverse. It looks to me as though there’s a bug in the pseudocode wherein the first returned vector should be { 1, 1 }.

posted @ 07:53 PM EST

The table of data below, released by the Pan-Mass Challenge, shows how unusual that event is in contributing 99% of funds raised to the charity it benefits.

**Event** | **Raised** | **Participants** | **Contributed** |

Pan-Mass Challenge | $26,000,000 | 4,271 | 99% |

Nike Women’s Marathon | $12,000,000 | 15,000 | 70% |

MS 150, Texas | $8,360,000 | 13,000 | 76% |

5 Livestrong Rides in US | $7,500,000 | 10,000 | 75% |

posted @ 08:16 PM EST