合同式の四則演算

$ \forall a,b,c,d,q\in\Z;\begin{dcases}a\equiv b\pmod{q}\\ c\equiv d\pmod{q}\end{dcases}\implies \begin{dcases}a+c&\equiv b+d&\pmod{q}\\ac&\equiv bd&\pmod{q}\end{dcases}

$ \forall a,b,c,q\in\Z;\begin{dcases}ac\equiv bc\pmod{q}\\ c\bot q\end{dcases}\implies a\equiv b\pmod{q}

証明

加算

$ \begin{dcases}a\equiv b\pmod{q}\\ c\equiv d\pmod{q}\end{dcases}

$ \iff \exists k,l\in\Z \begin{dcases}a-b=kq\\ c-d=lq\end{dcases}

$ \implies \exists k,l\in\Z; (a+c)-(b+d)=(k+l)q

2式を足しただけ

$ \iff \exists k\in\Z; (a+c)-(b+d)=kq

$ \iff a+c\equiv b+d\pmod{q}

乗算

$ \begin{dcases}a\equiv b\pmod{q}\\ c\equiv d\pmod{q}\end{dcases}

$ \iff \exists k,l\in\Z \begin{dcases}a-b=kq\\ c-d=lq\end{dcases}

$ \iff \exists k,l\in\Z; \begin{dcases}(a-b)(c-d)&=klq&(a)\\a-b&=kq&(b)\\ c-d&=lq&(c)\end{dcases}

$ (a-b)(c-d)=ac+bd-ad-bc

$ =ac-bd+2bd-ad-bc

$ =ac-bd-d(a-b)-b(c-d)

$ \iff ac-bd=(a-b)(c-d)+d(a-b)+b(c-d)

$ \iff\exists k,l\in\Z; \begin{dcases}ac-bd-d(a-b)-b(c-d)&=klq\\a-b&=kq\\ c-d&=lq\end{dcases}

$ \implies\exists k,l\in\Z;ac-bd-dkq-blq=klq

$ \iff\exists k,l\in\Z;ac-bd=(dk+bl+kl)q

$ \implies \exists k\in\Z; ac-bd=kq

$ \iff ac\equiv bd\pmod{q}

除算

だいぶややこしくなりそう

$ \begin{dcases}ac\equiv bd\pmod{q}\\c\equiv d\pmod{q}\\ c\bot q\end{dcases}

$ \iff \exists k,l\in\Z \begin{dcases}ac-bd=kq\\c-d=lq\\\forall p\in\Z;(\exists m,n\in\Z;c=mp\land q=np)\implies |p|=1\end{dcases}

あー、まずこの補題を示さなきゃだめか

$ \forall a,b,q\in\Z;\begin{dcases}ab\equiv0\pmod{q}\\b\bot q\end{dcases}\implies a\equiv0\pmod{q}

$ \begin{dcases}\exists k,l,m\in\Z;a=km\land q=lm\\\exists n\in\Z;ab=nq\\\forall p\in\Z;(\exists s,t\in\Z;b=sp\land q=tp)\implies |p|=1\end{dcases}

これすぐに解けないや