拡張ユークリッド互除法を用いた逆元計算について

Question

現在、拡張ユークリッド互除法を用いて逆元を計算する方法を学習しております。

法pにおけるaの逆元を求める式

aの逆元 ≡ −(p % a)^-1 × (p/a)　(mod. p)

上記の式で逆元が求まることは理解したのですが、
式をプログラミングに落とし込んだ際に、
「なぜpから「(p%a)^-1 × (p/a)」を引いてるのか」がわかりません。

// 法pにおけるaの逆元を求めるプログラム
// inv[i]は法pにおけるiの逆元を表す
inv[a] = p - inv[p%a] * (p/a) % p;
     //  ^
     //  なぜpから inv[p%a]*(p/a)%pを引いているのかがわからない

個人としては、式を素直にプログラムに落とし込むのであれば
以下で問題ないのではと考えております。

inv[a] = -inv[p%a] * (p/1) %p

「pから引いている理由」についてご教示いただければ幸甚でございます。
どうぞよろしくお願いいたします。
【参考にしたサイト】
https://drken1215.hatenablog.com/entry/2018/06/08/210000

Answer 1

カンですが負数の剰余には

-3 ÷ 5 = -1 あまり 2 or 0 あまり -3

ざっと2種類の解釈があります。

C99/C++11以降では-3%5は-3となります。
ただ、数学的には剰余が正の方が一般的（らしい）なので正規化を行っているのだと思います。

Comments

[Python-Beginner]

ご回答くださり、ありがとうございます。

「C++における余剰計算」については認識できておりませんでした。
ご回答くださった内容により、納得することができました。

ご教示くださり、ありがとうございました。