拡張ユークリッドの互除法

pythonの再帰で実装したもの

import sys

def egcd(a, b):
    """return (g, x, y) such that a*x + b*y = g = gcd(a, b)"""
    if a == 0:
        return (b, 0, 1)
    else:
        g, x, y = egcd(b % a, a)
        return (g, y - (b // a) * x, x)

rustではタプルが使えるので、同じアルゴリズムでいけます。

Algorithm Implementation/Mathematics/Extended Euclidean algorithm - Wikibooks, open books for an open world

拡張ユークリッドの互除法を使って、
を異なる素数とし、


の式と、
で求めたpを使って、

が求められます。