Number Theory Review

\[ axiom:\\ \left.\begin{matrix} g|x\\ g|y\end{matrix}\right\}\Rightarrow \left\{\begin{matrix} g|x\pm y\\ g|xy \end{matrix}\right.\\ \left.\begin{matrix} g|x\\ h|x\\ gcd(g,h)=1 \end{matrix}\right\}\Rightarrow gh|x \]

\[ property:\\ x\equiv a(mod\ kp)\Rightarrow x\equiv a(mod\ p)\\ proof:\\ x\equiv a(mod\ kp)\Rightarrow \\ \exists k^{'}\ x=a+k^{'}kp\Rightarrow \\ x=a+(k^{'}k)p\Rightarrow \\ \exists \lambda =(k^{'}k)\ x=a+\lambda p\Rightarrow\\ x\equiv a(mod\ p) \]

\[ property:\\ x\ mod\ p= g(\frac{x}{g}\ mod\ \frac{p}{g})\ (g|x\ and\ g|p)\\ proof:\\ let\ y=x\ mod \ p,\ 0\le y<p\\ obviously\ x=y+kp\\ according\ to\ extended\ gcd\ algorithm,\ g|y\\ \therefore \frac{x}{g}=\frac{y}{g}+k\frac{p}{g}(0\le\frac{y}{g}<\frac{p}{g})\\ \therefore \frac{y}{g}=\frac{x}{g}mod\ \frac{p}{g}\\ \therefore y=g(\frac{x}{g}mod\ \frac{p}{g}) \]