Modular Arithmetic--ការសិក្សាពីសំណល់

ដោយ$a\equiv b \pmod n$និង$b\equiv s \pmod n$ នោះមាន$a_0,b_0\in\mathbb{Z}$ ដែល$a=na_0+r,b=nb_0+s$។

1. យក$a$បូកនឹង$b$ យើងបាន $a+b=n(a_0+b_0)+(r+s)$
   ដែលសមមូលនឹង$a+b\equiv r+s \pmod n$។
2. យក$k$គុណនឹង$a$ យើងបាន $ka=n(ka_0)+(kr)$
   ដែលសមមូលនឹង$ka\equiv kr \pmod n$។
3. យក$a$គុណនឹង$b$ យើងបាន
   $ab=(na_0+r)(nb_0+s)=n(na_ob_0+a_0s+b_0b)+rs$
   ដែលសមមូលនឹង$ab\equiv rs \pmod n$។
4. ដោយ$a\equiv r \pmod n$នោះ$a\cdot a\equiv r\cdot r \pmod n$​ ឬ$a^2\equiv r^2 \pmod n$។ ដោយប្រើវិចារកំណើន យើងនឹងបាន $a^m\equiv r^m \pmod n$។

តាង $S:=\{as+bt:s,t\in \mathbb{Z}, as+bt>0 \}$។ នោះ $S$ ជាសំណុំរងមិនទទេរបស់$\mathbb{N}$ ព្រោះ $S$ ផ្ទុក $a$ ឬ $-a$ (យក $s=\pm 1, t=0$)។ តាមលក្ខណៈWell-orderingរបស់$\mathbb{N}$​ នាំឲ្យ $S$ មានធាតុតូចបំផុត តាងដោយ $d=ax+by$ ចំពោះ$x,y\in\mathbb{Z}$ណាមួ។
ដូច្នេះ យើងគ្រាន់តែបង្ហាញថា $d=\gcd(a,b)$ជាការស្រេច។

• ដំបូង យើងនឹងបង្ហាញថា $d$ ជាតួចែករួមនៃ$a$ និង $b$។

  • តាមវិធីចែកអឺគ្លីត យើងអាចសរសេរ $a=dq+r$ ដែល$q$ជាផលចែក និង$0\leq r<d$ជាសំណល់។
    បើ $r>0$ នោះ $r=a-dq=a-(ax+by)q=a(1-xq)+b(-yp)\in S$ ព្រោះវាមានទម្រង់$as+bt$។ តែដោយ $r< d$​ ការដែល $r>0$ ផ្ទុយពីការដែល$d$ជាធាតុតូចបំផុត។
    ដូចនេះត្រូវតែ $r=0$ ហើយនេះនាំឲ្យ $a=dr$។ មានន័យថា $d$ ជាតួចែកនៃ$a$។
  • ដូចគ្នាដែរ យើងអាចបង្ហាញថា $d$ ក៏ជាតួចែកនៃ$b$។​
  • ដូចនេះ $d$ជាតួចែករួមនៃ$a$ និង $b$.

• ច្រាសមកវិញ យើងនឹងបង្ហាញថា បើ$c>0$ ជាតួចែករួមផ្សេងទៀតនៃ$a$និង$b$ នោះ $c\leq d$ ដែលមានន័យថា $d$ជាតួចែករួមធំបំផុតនៃ$a$ និង $b$.
  បើ$c$ ជាតួចែករួមនៃ$a$និង$b$ នោះ $a=cu,b=cv$ ចំពោះ$u,v\in \mathbb{Z}$ណាមួយ។​ នាំឲ្យ
  $d=ax+by=cux+cvy=c(ux+vy)$
  មានន័យថា $c$ជាតួចែកនៃ$d$ នោះត្រូវតែ $c\leq d$។
  ដូចនេះ $d=\gcd(a,b)$ ដូចដែលចង់បាន។

Definition. គេថា $A\neq \varnothing$ ជា ក្រុមរង(subgroup) នៃ$\mathbb{Z}$ កាលណា

1. $0\in A$

2. $a\in A \Rightarrow -a\in A $

3. $a,b\in A \Rightarrow a+b\in A $

ចំពោះ $\alpha \in \mathbb{Z}$ យើងសរសេរ $\alpha \mathbb{Z}:=\{\alpha x: x\in \mathbb{Z}\}$ ហើយចំពោះ$a,b\in\mathbb{Z}$ យើងសរសេរ
$a\mathbb{Z}+b\mathbb{Z}=\{ax+by:x,y\in \mathbb{Z}\}$
តាមទ្រឹស្តីបទBézout Theorem នាំឲ្យ $a\mathbb{Z}+b\mathbb{Z}=d\mathbb{Z}$ ដែល$d=\gcd(a,b)$។

• ដំបូងយើងនឹងបង្ហាញថា $a \mathbb{Z}+b \mathbb{Z}$ ជាក្រុមរងនៃ$\mathbb{Z}$ ចំពោះគ្រប់$a,b \in \mathbb{Z}$។

1. $0\in a\mathbb{Z}+b\mathbb{Z}$ ព្រោះ $0=a\cdot 0+b\cdot b$
2. បើ$u\in a\mathbb{Z}+b\mathbb{Z}$ នោះ$u=ax+by, \quad (\exists x,y\in \mathbb{Z})$
   ដូចនេះ $-u=a(-x)+b(-y)\in a\mathbb{Z}+b\mathbb{Z} $
3. បើ$u,v\in a\mathbb{Z}+b\mathbb{Z}$ នោះ$u=ax_1+by_1,v=ax_2+by_2, \quad (\exists x_1,x_2,y_1,y_2\in \mathbb{Z})$។
   ដូចនេះ $u+v=a(x_1+x_2)+b(y_1+y_2)\in a\mathbb{Z}+b\mathbb{Z}$

• បន្ទាប់មកយើងនឹងបង្ហាញថា បើ$A$ជាក្រុមរងមិនទទេនៃ$\mathbb{Z}$ នោះវាត្រូវតែមានទម្រង់$A=k\mathbb{Z}$ ចំពោះ$k\mathbb{Z}$ណាមួយ។
  • តាង $A^+:=\{\ell\in A:\ell >0\}$
    តាម2. យើងអាចដឹងថាវាជាសំណុំរងមិនទទេនៃ$\mathbb{N}$. តាមលក្ខណៈWell-ordering នៃ$\mathbb{N}$ នាំឲ្យ $A^+$មានធាតុតូចបំផុត ដែលតាងដោយ$k$។
    ដោយចំពោះគ្រប់$u\in \mathbb{Z}$ យើងបាន $ku\in A$ (តាម3.) យើងទាញបាន $k\mathbb{Z}\subset A$។
  • ច្រាសមកវិញ យក$x\in A$។ តាមវិធីចែកអឺគ្លីត$x=kq+r$ ដែល$q$ជាផលចែក និង$0\leq r< k$ជាសំណល់។ នាំឲ្យ $r=x-kq\in A$ ព្រោះ $A$ ជាក្រុមរង​ ហើយ$x,-kq\in A$​ (តាម3.)។ ដូចនេះ $r=0$ ព្រោះបើ$r>0$ផ្ទុយពីការដែល$k$ជាធាតុតូចបំផុត។
    ដូចនេះ $x=kq\in k\mathbb{Z}$ ដែលនាំឲ្យ$A\subset k\mathbb{Z}$។
    ដូចនេះ $A=k\mathbb{Z}$.
• ដោយ $a\mathbb{Z}+b\mathbb{Z}$ ជាក្រុមរងនៃ$\mathbb{Z}$ នោះ $a\mathbb{Z}+b\mathbb{Z}=k\mathbb{Z}$ ចំពោះ$k\in \mathbb{Z}$ណាមួយ។
• ដូច្នេះ ចុងក្រោយយើងគ្រាន់តែបង្ហាញថា $k=\gcd(a,b)$ជាការស្រេច។
  ដោយ $a\mathbb{Z}+b\mathbb{Z}=k\mathbb{Z}$ នោះ $a=a\cdot 1+b\cdot 0=kx, \quad (\exists x\in \mathbb{Z})$.
  មានន័យថា $k$ជាតួចែកនៃ$a$។
  ដូចគ្នាដែរ ដោយ$b=a\cdot 0+b\cdot 1=ky, \quad (\exists y\in \mathbb{Z})$, នោះ $k$ក៏ជាតួចែកនៃ$b$ដែរ។
  សរុបមក $k$ជាតួចែករួមនៃ$a$និង$b$។
• ដើម្បីបង្ហាញថា$k$ជាតួចែករួមធំបំផុតនៃ$a$និង$b$ យក$c$ជាតួចែកផ្សេងទៀតនៃ $a$និង$b$។
  នោះ $a=cu,b=cv, \quad \exists u,v\in \mathbb{Z}$
  ដោយ $a\mathbb{Z}+b\mathbb{Z}=k\mathbb{Z}$ នោះ $as+bt=k\cdot 1\quad (\exists s,t\in \mathbb{Z})$។​ យើងបាន
  $k=as+bt=cus+cvt=c(us+vt)$.
  មានន័យថា $c$ជាតួចែកនៃ$k$។ នោះត្រូវតែ$c\leq k$។
  ដូចនេះ $k=\gcd(a,b)$

យើងនឹងស្រាយថា បើ$[a_1]_n=[a_2]_n,[b_1]_n=[b_2]_n$ នោះ $[a_1+b_1]_n=[a_2+b_2]_n,[a_1b_1]_n=[a_2b_2]_n$។
តាមសម្មតិកម្ម យើងបាន$a_1\equiv a_2\pmod n,b_1\equiv b_2\pmod n$។ តាមប្រមាណវិធីលើModulo

1. $a_1+b_1\equiv a_2+b_2\pmod n\Rightarrow [a_1+b_1]_n=[a_2+b_2]_n$
2. $a_1b_1\equiv a_2b_2\pmod n\Rightarrow [a_1b_1]_n=[a_2b_2]_n$

• បើ$\gcd(a,n)=1$ នោះតាមទ្រឹស្តីបទBézout មាន$x,y\in \mathbb{Z}$ ដែល$ax+ny=1$
  នាំឲ្យ $ax\equiv -ny+1\equiv 1\pmod n$
  ដែលសមមូលនឹង$ [a]_n\cdot [x]_n=[1]_n$។ មានន័យថា $[x]_n$ជាចម្រាសនៃ$[a]_n$។
  ដូចនេះ$[a]_n\in \mathbb{Z}_n^*$
• ច្រាសមកវិញ　បើ$[a]_n\in \mathbb{Z}_n^*$ នោះមាន$x\in\mathbb{Z}$ ដែល$ax\equiv 1\pmod n$។
  នាំឲ្យមាន$x,y\in \mathbb{Z}$ ដែល$ax+ny=1$។
  តាង$d=\gcd(a,b)$ នោះ$a=du,b=dv, (\exists u,v\in\mathbb{Z})$។​ នាំឲ្យ
  $1=ax+ny=dux+dvy=d(ux+vy)$
  យើងទាញបាន $d$ជាតួចែកនៃ$1$ នាំឲ្យ$d=1$។ ដូចនេះ $\gcd(a,n)=1$

• តាង $(a) := \{b\in Z_n^* : a^{-1}b ∈ E\}$។ យើងនឹងបង្ហាញថា $ \textcolor{blue}{Z_n^* = \bigcup_{a \in Z_n^*}(a)} $
  ចំពោះគ្រប់$ a \in Z_n^* $ ដោយ$E$ជាក្រុមរង $ 1 \in E $​ នោះ $a \in (a)$ ព្រោះ $a^{-1}\cdot a = 1 \in E$។​ នេះមានន័យថា $a \in \bigcup_{a \in Z_n^*}(a)$។ ដូចនេះ $Z_n^* \subset \bigcup_{a \in Z_n^*}(a)$។
  តែដោយ $(a) ⊂ Z_n^*$ នោះ$ \bigcup_{a \in Z_n^*}(a) \subset Z_n^*$។
  ដូច្នេះសរុបមក យើងបាន $Z_n^* = \cup_{a \in Z_n^*}(a)$

• បន្ទាប់មកយើងនឹងបង្ហាញថា $(a) = aE$ ដែល$aE:= \{ax : x ∈ E\}$ ដែលនេះមានន័យថា ចំនួនធាតុនៃ$(a)$ស្មើនឹងចំនួនធាតុនៃ$E$។
  បើ $x \in aE$ នោះមាន$ y \in E$ ដែល$x = ay$។ តែដោយ $a^{-1}x = a^{-1}(ay) = y \in E$ នោះ$x \in (a)$។ ដូចនេះ $aE \subset (a)$។
  ច្រាសមកវិញ បើ$x \in (a)$ នោះ $a^{-1}x = y$ ដែល$y \in E$។ នោះ$x = ay \in aE$។ យើងបាន $aE \subset (a)$។
  សរុបមក យើងបាន $(a) = aE$។
  ជាវិបាន យើងទាញបាន $|(a)| = |aE|=|E|$។

• ជាចុងបញ្ចប់ យើងនឹងបង្ហាញថា $(a), (b) $ជាសំណុំដាច់ពីគ្នា ពោលគឺ
  $(a) = (b)$ ឬ$(a) \cap (b) = \varnothing $
  ដែលសមមូលនឹងបង្ហាញថា បើ$(a) \cap (b) \neq \emptyset$ នោះ$(a) = (b)$។
  បើ $(a) \cap (b) \neq \emptyset$ នោះ $\exists x \in (a), (b)$ ។ មានន័យថា $a^{-1}x \in E, b^{-1}x \in E$។
  បើ $w \in (a)$ នោះ $a^{-1}w \in E$។​ នាំឲ្យ
  $b^{-1}w = (b^{-1}x)(x^{-1}a)(a^{-1}w) = \underbrace{(b^{-1}x)}_{\in E}\underbrace{(a^{-1}x)^{-1}}_{\in E}\underbrace{(a^{-1}w)}_{\in E} \in E$
  ដែលនាំឲ្យ $w \in (b)$។ យើងបាន $(a) \subset (b)$
  ស្រាយដូចគ្នា យើងនឹងបាន$(b) \subset (a)$។
  សរុបមក យើងបាន$(a) = (b)$ ដូចចង់បង្ហាញ។

ដូច្នេះ $Z_n^* = \bigcup_{a \in Z_n^*}(a)$ គឺប្រជុំនៃសំណុំដាច់គ្នា ហើយដោយ $|(a)| = |E|, (\forall a\in Z_n^*)$ យើងបាន$|Z_n^*| = k |E|$ ចំពោះ$k \in \mathbb{N}$ណាមួយ។
ដូចនេះ យើងទាញបានថា $|Z_n^*|$ចែកដាច់នឹង$|E|$។

• តាង$\langle a \rangle := \{[a^k]_n : k \in \mathbb{Z} \}$ ។
• ដោយ$\gcd(a, n) = 1$ តាមLemma នាំឲ្យ$[a]_n \in Z_n^*$ និង$|Z_n^*| = \varphi(n)$។
• $\langle a \rangle$ជាក្រុមរងនៃ$Z_n^*$ ព្រោះ
  • $1 = a^0\in \langle a \rangle$
  • $a^k \in \langle a \rangle \Rightarrow a^{-k} \in \langle a \rangle$
  • $a^{k_1},a^{k_2} \in \langle a \rangle \Rightarrow a^{k_1}a^{k_2}=a^{k_1+k_2} \in \langle a \rangle$
• តែដោយ$Z_n^*$ជាក្រុមមានធាតុរាប់អស់ នាំឲ្យ$\langle a \rangle$ដែលជាក្រុមរងរបស់វា ក៏មានធាតុរាប់អស់ដែរ។ នោះយើងទាញបានថា មាន$m \in \mathbb{N}$ដែល
  $\langle a \rangle := \{[1]_n, [a]_n, [a^2]_n, \dots, [a^{m}]_n \}$ ហើយ$ \quad [a^{m+1}]_n = [1]_n$
• តាមទ្រឹស្តីបទ Lagrange យើងដឹងថា $|\langle a \rangle| = m+1$ ជាតួចែកនៃ$|Z_n^*| = \varphi(n)$ មានន័យថា$\varphi(n) = (m+1)\ell$ ចំពោះ$\ell \in \mathbb{N}$ណាមួយ។ ដូចនេះ
  $a^{\varphi(n)} \equiv a^{(m+1)\ell} \equiv (a^{m+1})^\ell \equiv 1^\ell \equiv 1 \pmod{n}$

1. យើងនឹងបង្ហាញថា បើ$p$ជាចំនួនបឋម ហើយ$\alpha \in \mathbb{N}$ នោះ$\varphi(p^{\alpha})= p^{\alpha}-p^{\alpha-1}$។
   ដោយ$p$ជាចំនួនបឋម នោះ$\gcd(p^{\alpha},m)$អាចស្មើនឹង$1,p,p^2,\cdots p^{\alpha}$
   ហើយ$\gcd(p^{\alpha},m)>1$ លុះត្រាតែ$m$ជាពហុគុណនៃ$p$។ មានន័យថា
   $m\in\{p,2p,3p,\cdots p^{\alpha-1}p\}$ដែលមាន$p^{\alpha-1}$ករណី។
   ដូចនេះ ចំនួនដែលបឋមនឹង$n$ហើយតូចជាង$n$ មានចំនួន$\varphi(p^{\alpha})= p^{\alpha}-p^{\alpha-1}$។
2. យើងនឹងស្រាយបញ្ជាក់ multiplicativity នៃអនុគមន៍$\varphi$:
   បើ$\gcd(m,n)=1$ នោះ$\varphi(mn)=\varphi(m)\varphi(n)$

• ពិនិត្យអនុវត្តន៍
  \begin{align} f : \mathbb{Z} / mn\mathbb{Z} &\to \mathbb{Z} / m\mathbb{Z} \times \mathbb{Z} / n\mathbb{Z} \\ [x]_{mn} &\mapsto \left( [x]_m, [x]_n \right) \end{align}
• ដោយប្រើ Chinese remainder theorem យើងអាចបង្ហាញថា $f$ជាអនុវត្តន៍ bijective។
• ដោយrestrict អនុវត្តន៍$f$ លើដែនកំណត់$\mathbb{Z}_{mn}^*$ យើងអាចបង្ហាញថា $f(\mathbb{Z}_{mn}^*)=\mathbb{Z}_{m}^*\times \mathbb{Z}_{n}^* $
  ព្រោះបើ$x$បឋមរវាងគ្នានឹង$mn$ នោះ$x$ក៏បឋមរវាងគ្នានឹង$m$និង$n$ដែរ។
  ដូចនេះ អនុវត្តន៍$f : \mathbb{Z}_{mn}^* \to \mathbb{Z}_{m}^*\times \mathbb{Z}_{n}^*$ជាអនុវត្តន៍ bijective។
  ដូចនេះ $|\mathbb{Z}_{mn}^*|=|\mathbb{Z}_{m}^*\times \mathbb{Z}_{n}^*|$
• តែដោយ $|\mathbb{Z}_{mn}^*|=\varphi(mn)$ និង$|\mathbb{Z}_{m}^*\times \mathbb{Z}_{n}^*|=|\mathbb{Z}_{m}^*| \cdot|\mathbb{Z}_{n}^*|=\varphi(m)\varphi(n)$
  យើងបាន$\varphi(mn)=\varphi(m)\varphi(n)$ ដូចដែលយើងចង់បាន។
• ដោយប្រើលក្ខណៈMultiplicativeរបស់$\varphi$​ និងលទ្ធផលក្នុង 1. យើងនឹងអាចគណនា$\varphi(n)$ចំពោះ$n=\prod_{i=1}^m p_i^{\alpha_i}$ដូចរូបមន្តខាងលើ។

ប្រើទ្រឹស្តីបទ Euler ដែល$\varphi(p)=p-1$។

• ចំពោះចំនួនបឋម$p$ តាមទ្រឹស្តីបទ Bézout យើងដឹងថា$\mathbb{Z}_p^*=\{[1]_p,[2]_p,[3]_p,\cdots,[p-1]_p\}$
  មានន័យថា គ្រប់ធាតុនៃ$\mathbb{Z}_p^*$សុទ្ធតែមានចម្រាស ឬអាចនិយាយថាចំពោះគ្រប់$a\in\{1,2,3,\cdots,p-1\}$ មាន$b\in\{1,2,3,\cdots,p-1\}$ ដែល$a\cdot b\equiv 1\pmod p$។
• យើងនឹងបង្ហាញថា ចំនួន$a$ដែលមានចម្រាសស្មើនឹងខ្លួនឯង មានតែ$1,p-1$ប៉ុណ្ណោះ។ មានន័យថា បើ$a^2\equiv 1\pmod p$ នោះ$ a\equiv 1\pmod p$ ឬ$ a\equiv p-1\pmod p$។
  $a^2\equiv 1\pmod p\Leftrightarrow a^2-1\equiv 0\pmod p\Leftrightarrow (a-1)(a+1)\equiv 0\pmod p$
  ដោយ$p$ជាចំនួនបឋម យើងទាញបាន
  $ a-1\equiv 0\pmod p$ ឬ$ a+1\equiv 0\pmod p$
  សមមូលនឹង​$ a\equiv 1\pmod p$ ឬ$ a\equiv -1 \equiv p-1\pmod p$
• ដូច្នេះ យើងអាចចាប់គូ$(a,b)$ចេញពី$\{1,2,3,\cdots,p-1\}$ ដែល$a\cdot b\equiv 1\pmod p$បានលើកលែងតែ$1,p-1$។
  ដូចនេះ
  \begin{align} (p-1)!&\equiv 1\times 2\times 3\times\cdots \times (p-1)\\ &\equiv 1\times \underbrace{1\times \cdots \times 1}_{\frac{p-3}{2}\text{ terms of }1} \times (p-1)\\ &\equiv 1\cdot (p-1)\equiv -1\pmod p \end{align}

• ដំបូងយើងនឹងបង្ហាញថា បើ$x^2 \equiv -1 \pmod{p}$ មានចម្លើយ​ នោះ​$p\equiv 1\pmod 4$។
  ផ្ទុយពីការសន្និដ្ឋាន យើងឧបមាថា $p \equiv 3 \pmod{4}$។ នោះ$p = 4k+3, (\exists k \in \mathbb{N})$
  ដោយ $x^2 \equiv -1 \pmod{p}$ នោះ $x^4 \equiv 1 \pmod{p}$។ យើងឃើញថា
  $x^{p-1} \equiv x^{4k+2} = (x^4)^k x^2 \equiv 1^k \cdot (-1) \equiv -1 \pmod{p}$
  ដែលមិនអាចពិត ព្រោះផ្ទុយនឹងទ្រឹស្តីបទ Fermat។ ដូច្នេះការឧបមានេះមិនពិតទេ មានន័យថាគឺត្រូវតែ$p \equiv 1 \pmod{4}$។
• ច្រាសមកវិញ ឧបមាថា$p \equiv 1 \pmod{4}$។
  នោះ $p = 4m+1, (\exists​​ m \in \mathbb{N})$។
  តាមទ្រឹស្តីបទ Wilson
  $(p-1)! \equiv -1 \pmod{p}\quad\dots (*)$
  ដោយតំរៀបអង្គខាងឆ្វេងឡើងវិញដោយចាប់គូៗ ហើយដោយ$\dfrac{p-1}{2}=2m\in\mathbb{N}$ ការចាប់គូៗបែបនេះមិនធ្វើឲ្យសល់តួណាមួយទេ នោះយើងឃើញថា
  \begin{align} (p-1)! &\equiv 1 \cdot (p-1) \cdot 2 \cdot (p-2) \cdots (2m) \cdot (p-2m)\\ &\equiv 1 \cdot (-1) \cdot 2 \cdot (-2) \cdots (2m) \cdot (p-2m)\\ &\equiv (-1)^{2m} (1 \cdot 2 \cdots (2m))^2 \equiv ((2m)!)^2 \pmod{p}\quad\dots (**) \end{align}
  តាម$(*),(**)$ យើងបាន$((2m)!)^2 \equiv -1 \pmod{p}$។
  ដូច្នេះ $x \equiv (2m)! \equiv \left( \dfrac{p-1}{2} \right)!\pmod{p}$ ជាចម្លើយនៃ$x^2 \equiv -1 \pmod{p}$។

• បើសមីការ$ x^2\equiv a\pmod {p^n} $មានចម្លើយគ្រប់$n\geq 1$ យើងគ្រាន់តែយក$n=1$ នោះសមីការ​$ x^2\equiv a\pmod {p} $ក៏មានចម្លើយដែរ។
• ច្រាសមកវិញ ឧបមាថា$ x^2\equiv a\pmod {p} $មានចម្លើយ។ យើងនឹងស្រាយថា $ x^2\equiv a\pmod {p^n} $មានចម្លើយគ្រប់$n\geq 1$។
  យើងនឹងស្រាយតាមវាចារកំណើន។
  • បើ$n=1$ គ្មានអ្វីត្រូវស្រាយថា ព្រោះវាពិតតាមសម្មតិកម្ម។
  • ឧបមាថា​ វាពិតរហូតដល់$n=k\geq 1$ មានន័យថាសមីការ$ x^2\equiv a\pmod {p^k} $មានចម្លើយ។
  • យើងនឹងបង្ហាញថា សមីការ​$ x^2\equiv a\pmod {p^{k+1}} $ក៏មានចម្លើយដែរ។
    តាង$x_0$ជាចម្លើយមួយនៃ$ x^2\equiv a\pmod {p^k} $។​ នោះ$x_0^2=a+mp^k,(\exists m\in\mathbb{Z})$
    ដោយ$p$ជាចំនួនបឋមសេស នាំឲ្យ$\gcd(2x_0,p)=1$។ នោះតាមទ្រឹស្តីបទ Bézout
    មាន$\exists y_0,z_0\in\mathbb{Z}$ ដែល$ 2x_0y_0+pz_0=1 $
    តាង$x_1=x_0-my_0p^k$។ យើងឃើញថា
    \begin{align} x_1^2&=(x_0-my_0p^k)^2\\ &=x_0^2-2mx_0y_0p^k+m^2y_0^2p^{2k}\\ &=a+mp^k-2mx_0y_0p^k+m^2y_0^2p^{2k}\\ &=a+m(\underbrace{1-2x_0y_0}_{=pz_0})p^{k}+m^2y_0^2p^{2k}\\ &=a+mz_0p^{k+1}+m^2y_0^2p^{2k} \end{align}
    ដោយ$p^{k+1}\equiv 0\pmod {p^{k+1}},p^{2k}\equiv 0\pmod {p^{k+1}}$នាំឲ្យ$x_1^2\equiv a\pmod {p^{k+1}}$។
    ដូច្នេះ$x_1=x_0-my_0p^k$ជាចម្លើយនៃ$ x^2\equiv a\pmod {p^{k+1}} $។
    តាមវាចារកំណើន យើងបានបង្ហាញថា សមីការ$ x^2\equiv a\pmod {p^n} $មានចម្លើយគ្រប់$n\geq 1$។