[nooonuii]

$\phi(n)$ คือ จำนวนของจำนวนนับที่น้อยกว่า $n$ ซึ่ง หรม ของจำนวนนั้นกับ $n$ เป็น 1

เช่น $\phi(6)=2$ เพราะในบรรดาจำนวนนับ $1,2,3,4,5$ มีเพียง $1,5$ เท่านั้นที่มีสมบัติว่า $(1,6)=1=(5,6)$

euler theorem กล่าวว่า ถ้า $(a,n)=1$ แล้ว $a^{\phi(n)}\equiv 1\pmod{n}$

เช่น

$3^{\phi(10)}\equiv 1\pmod{10}$

จึงได้ว่า

$3^{4}\equiv 1\pmod{10}$

ถ้าอยากใช้ทฤษฎีบทนี้ให้คล่องก็ต้องรู้จักวิธีหา $\phi(n)$ ซึ่งมีสูตรอยู่ครับ