設
a
∈
D
∖
(
D
×
∪
{
0
}
)
{\displaystyle a\in {\textbf {D}}\backslash ({\textbf {D}}^{\times }\cup \{0\})}
。證明有一個不可分解數
p
i
{\displaystyle p_{i}}
符合
p
i
|
a
{\displaystyle p_{i}|a}
。
如果
a
{\displaystyle a}
係不可分解數,搞掂。
如果唔係,咁就有
a
1
,
b
1
∈
D
∖
(
D
×
∪
{
0
}
)
{\displaystyle a_{1},b_{1}\in {\textbf {D}}\backslash ({\textbf {D}}^{\times }\cup \{0\})}
符合
a
=
a
1
b
1
{\displaystyle a=a_{1}b_{1}}
,如果
a
1
,
b
1
{\displaystyle a_{1},b_{1}}
都係不可分數,搞掂。
如果都唔係,
⟨
a
⟩
⊊
⟨
a
1
⟩
{\displaystyle \langle a\rangle \subsetneq \langle a_{1}\rangle }
,
b
∉
D
×
{\displaystyle b\notin {\textbf {D}}^{\times }}
。
將以上嘅概念放去
a
1
∈
D
∖
(
D
×
∪
{
0
}
)
{\displaystyle a_{1}\in {\textbf {D}}\backslash ({\textbf {D}}^{\times }\cup \{0\})}
,因為
a
1
{\displaystyle a_{1}}
唔係不可分解數。
咁
a
1
=
a
2
b
2
{\displaystyle a_{1}=a_{2}b_{2}}
,
a
2
,
b
2
∈
D
∖
(
D
×
∪
{
0
}
)
{\displaystyle a_{2},b_{2}\in {\textbf {D}}\backslash ({\textbf {D}}^{\times }\cup \{0\})}
,如果
a
2
{\displaystyle a_{2}}
或者
b
2
{\displaystyle b_{2}}
都係不可分解數,搞掂。
繼續呢個步驟,就會有
p
i
{\displaystyle p_{i}}
係一個不可分解數,或者一條增長連鎖
⟨
a
⟩
⊊
⟨
a
1
⟩
⊊
⟨
a
2
⟩
⊊
⋯
{\displaystyle \langle a\rangle \subsetneq \langle a_{1}\rangle \subsetneq \langle a_{2}\rangle \subsetneq \cdots }
。
因為ACCPI,所以後者係無可能出現。
由上面呢段嘢,可以總結出任何
a
∈
D
∖
(
D
×
∪
{
0
}
)
{\displaystyle a\in {\textbf {D}}\backslash ({\textbf {D}}^{\times }\cup \{0\})}
唔係不可分解數,就都可以有一個不可分解數
p
1
{\displaystyle p_{1}}
符合
p
1
|
a
{\displaystyle p_{1}|a}
。
(即係對應一啲
b
1
∈
D
∖
(
D
×
∪
{
0
}
)
{\displaystyle b_{1}\in {\textbf {D}}\backslash ({\textbf {D}}^{\times }\cup \{0\})}
,
a
=
p
1
b
1
{\displaystyle a=p_{1}b_{1}}
)
如果
b
1
{\displaystyle b_{1}}
係不可分解數,搞掂。
如果唔係,
b
1
=
b
2
=
p
3
b
3
{\displaystyle b_{1}=b_{2}=p_{3}b_{3}}
同時ACCPI會令到呢個連續嘅行為停止。
總結得知一定有
n
{\displaystyle n}
咁多
b
n
{\displaystyle b_{n}}
嘅不可分解數,令到
a
=
p
1
p
2
b
2
=
p
1
p
2
⋯
p
n
b
n
{\displaystyle a=p_{1}p_{2}b_{2}=p_{1}p_{2}\cdots p_{n}b_{n}}
成立。
而呢個就係
a
{\displaystyle a}
嘅質數分解。
如果
a
=
p
1
p
2
⋯
p
m
=
q
1
q
2
⋯
q
m
{\displaystyle a=p_{1}p_{2}\cdots p_{m}=q_{1}q_{2}\cdots q_{m}}
都係
a
∈
D
∖
(
D
×
∪
{
0
}
)
{\displaystyle a\in {\textbf {D}}\backslash ({\textbf {D}}^{\times }\cup \{0\})}
嘅質數分解。
約到最簡,可以假設
n
≥
m
{\displaystyle n\geq m}
。
因為不可分解數
⟹
{\displaystyle \implies }
質數,
p
1
|
q
1
q
2
⋯
q
n
⟹
p
1
|
q
i
{\displaystyle p_{1}|q_{1}q_{2}\cdots q_{n}\implies p_{1}|q_{i}}
,
將佢排返好,可以叫
i
=
1
{\displaystyle i=1}
,
p
1
|
q
1
{\displaystyle p_{1}|q_{1}}
;但係
q
1
{\displaystyle q_{1}}
係不可分解數,所以對應一啲
u
1
∈
D
×
{\displaystyle u_{1}\in {\textbf {D}}^{\times }}
,
q
1
=
p
1
u
1
{\displaystyle q_{1}=p_{1}u_{1}}
所以
p
1
p
2
⋯
p
n
=
(
p
1
u
1
)
q
2
⋯
q
m
{\displaystyle p_{1}p_{2}\cdots p_{n}=(p_{1}u_{1})q_{2}\cdots q_{m}}
,
⟹
p
2
⋯
p
n
=
u
1
q
2
⋯
q
m
{\displaystyle \implies p_{2}\cdots p_{n}=u_{1}q_{2}\cdots q_{m}}
。
重覆以上步驟,將
p
2
,
p
3
⋯
p
n
{\displaystyle p_{2},p_{3}\cdots p_{n}}
處理,
⟹
{
q
i
=
u
i
p
i
i
=
1
⋯
n
,
u
i
∈
D
×
1
=
u
1
u
2
⋯
u
n
q
n
+
1
⋯
q
m
{\displaystyle \implies {\begin{cases}q_{i}=u_{i}p_{i}\quad i=1\cdots n,u_{i}\in {\textbf {D}}^{\times }\\1=u_{1}u_{2}\cdots u_{n}q_{n+1}\cdots q_{m}\end{cases}}}
。
因為每一個
q
i
{\displaystyle q_{i}}
都係不可分解數,加上佢哋唔係單元(Unit),所以
m
=
n
{\displaystyle m=n}
。